IJCNC 01

PERFORMANCE OF ALOHA-Q WITH ADAPTIVETRANSMISSION PROBABILITY

Katsumi Sakakibara

Department of Information and Communication Engineering,
Okayama Prefectural University, Soja, Japan

ABSTRACT

We propose incorporation of adaptive transmission probability to ALOHA-Q, which is a framed slotted ALOHA-based random access protocol ingeniously integrating Q-learning for slot selection in a frame. The transmission probability is also adaptively controlled based on Q-learning. Performance of the proposed protocol is confirmed by means of computer simulation. Numerical results show that the proposed protocol can mitigate performance degradation of ALOHA-Q under overloaded traffic condition and exhibits comparable performance to ALOHA-Q for moderate traffic condition.

KEYWORDS

Framed Slotted ALOHA, Q-Learning, ALOHA-Q, Throughput, Transmission Probability

1.INTRODUCTION

Recent spread of tiny Internet-of-Things (IoT) devices and Machine-to-Machine (M2M) devices facilitates the rapid increase in burst traffic [1]. An application range of such devices includes not only terrestrial communication networks and body area networks [2], [3] but also satellite communication networks [4], underwater sensor networks [5], and hybrid configurations of the above networks. In order to accommodate the ceaseless growth of communication demand within limited bandwidth, access control protocols play an important role.

Random access protocols originated from the well-known ALOHA protocol in 1970 [6]. ALOHA-based random access protocols have been favorably implemented due to their simplicity in numerous communication systems [1], [4], [7], [8],[9],[10]. In RFID systems [7], a dynamic FSA (Framed Slotted ALOHA) [11] is utilized for the anti-collision algorithm. In [8], [10], the use of ALOHA-Q [12], which is an ingenious integration of FSA and Q-learning, is proposed for underwater network design, and the performance is evaluated. In [9], the use of ALOHA-Q is considered in the scenario where immediate acknowledgements are unavailable. ALOHA-Q offers good performance, since Q-learning endeavors to achieve a TDMA-like convergence of slot assignment in a frame [8],[9], [10]. Within the framework of ALOHA-Q, most of the literatures assume that the frame length be equal to the number of possible active nodes [8], [9]. However, it is easy to conjecture that the performance of ALOHA-Q is degraded under overloaded traffic conditions, where the number of active nodes at the beginning of a frame exceeds the frame length in the slot.

In this paper, we propose incorporation of transmission probability to ALOHA-Q in order to mitigate overloaded traffic condition. The transmission probability is also adaptively controlled based on Q-learning. Performance of the proposed protocol is evaluated by means of exhaustive computer simulation in terms of throughput, packet collision probability and Jain’s fairness index [13].

The rest of the letter is organized as follows: Section II presents a system model and describes FSA. ALOHA-Q is briefly reviewed in Section III. In Section IV, we propose the incorporation of transmission probability with ALOHA-Q. Numerical results obtained by means of computer simulation are presented in Section V. Finally, Section VI concludes the present letter.

2.SYSTEM MODEL AND FRAMED SLOTTED ALOHA

Consider a random access network with 𝑁 single-buffer nodes contending for a common receiver through a shared channel. The time axis is divided into slots of unit length. A node with an empty buffer generates a new packet of unit length with probability 𝜆 at the beginning of each time slot. It follows from the single-buffer assumption that a node with an occupied buffer generates no new packets. Furthermore, 𝐿 consecutive slots construct a frame. We assume ideal slot- and frame-synchronizations in the network. A packet transmission results in success, if no other simultaneous packet transmissions occur. We ignore channel noise and fading. On the other hand, packet collision happens and all the packets in collision must be retransmitted in a properly selected slot afterward, so that we ignore the capture effect [14].

In FSA, a node with packet at the beginning of a frame; active node, transmits the packet in a slot randomly selected among L slots in frame. If packet transmission fails, the node randomly selects one slot in the next frame and retransmits the packet until packet transmission succeeds.

3.ALOHA-Q

As shown in [6], the frame length 𝐿in FSA should be dynamically adjusted according to the number of active nodes at the beginning of the frame, in order to maximize the throughput.However, it is complicated to obtain or approximate the number of such nodes in real-time.Instead, an introduction of an effective tool from a framework of reinforcement learning facilitates the performance improvement of FSA without adjusting the frame length. ALOHA-Q [8],[9],[10],[12] incorporates FSA with Q-learning. In ALOHA-Q, each node equips an 𝐿 – dimensional vector, which is referred to as a Q-table;

where 𝑞𝑡,ℓ is a real number; ℓ = 1, 2, ⋯ , 𝐿, 𝑡 is the frame number; 𝑡 = 1, 2, ⋯, and the initial condition is 𝑸1 = 𝟎. An active node transmits a packet in Slot 𝑖 with the maximum 𝑞𝑡,𝑖, where 𝑖 = arg maxℓ [𝑞𝑡,ℓ]. If there exist two or more such slot numbers, 𝑖is randomly selected among them. Then, the value of 𝑞𝑡,𝑖 is updated for the next frame depending on the outcome of the packet transmission, success or unsuccessful, as follows [8],[9],[10],[12];

where 𝛼is the learning rate, 0 ≤ 𝛼 ≤ 1, and 𝑟𝑡is the reward at Frame ;

It follows from (2) that the updated value 𝑞𝑡+1,𝑖 is an internally dividing point between 𝑞𝑡,𝑖and 𝑟𝑡 at ratio of 𝛼: (1 − 𝛼). Therefore, large 𝛼 may lead to drastic and unstable change of the value of 𝑞𝑡,𝑖. Note that the value of𝑞𝑡,ℓ is unchanged for Slot ℓ ≠ 𝑖 with no packet (re)transmission.

[Example 1] A simple example of ALOHA-Q is shown in Figure 1 for 𝑁 = 𝐿 = 3, 𝛼 = 0.5, 𝑅succ = 1.0 and 𝑅fail = −1.0. Suppose that at Frame 1, Nodes 1 and 2 have their own packet and Node 3 has no packet to transmit. Nodes 1 and 2 randomly select Slot 1 and 2 for packet transmission, respectively, since 𝑸1 = 𝟎. Both packet transmissions are successful, then the corresponding value is updated as 𝑞2,1 = 𝛼 = 0.1 at Node 1 and𝑞2,2 = 0.1 at Node 2. At Frame 2,Nodes 1 and 2 transmit their next packet in a slot with the maximum value in their Q-table. On the other hand, Node 3 randomly select a slot for packet transmission. Since two packets collide in Slot 1, Nodes 1 and 3 updates their Q-table as 𝑞3,1 = (1 − 𝛼)𝑞2,1 − 𝛼 = −0.01 at Node 1 and 𝑞3,1 = −𝛼 = −0.1 at Node 3. Successful Node 2 increases its 𝑞2,2 = 0.1 to 𝑞3,2 = (1 − 𝛼)𝑞2,2 +𝛼 = 0.19.

Figure 1. Example of ALOHA-Q for 𝑁 = 𝐿 = 3, 𝛼 = 0.5, 𝑅succ = 1.0and 𝑅fail = −1.0.

4.INTRODUCING ADAPTIVE TRANSMISSION PROBABILITY

It is known in [8], [10], [12] that ALOHA-Q can successfully manage slot assignment in a frame to each node when the number of nodes is equal to the frame length and each node is saturated, that is, for the case of 𝑁 = 𝐿 and 𝜆 = 1.0. However, inthe case that the number of active nodes is greater than the frame length and that a node is nearly saturated, packet collisions tend to occur in a number of slots in a frame, since an active node at the beginning of a frame inevitably transmits its packet, even if Q-learning is incorporated.
In order to avoid packet collision in such a case, we propose to introduce adaptive transmission probability 𝑝𝑡 to FSA and ALOHA-Q, where 𝑡 the frame number; 𝑡 = 1, 2, ⋯. In the proposed protocol, an active node transmits its packet with probability 𝑝𝑡 in the selected slot in Frame 𝑡. It implies that packet transmission is deferred to the next frame with probability 1 − 𝑝𝑡. The transmission probability 𝑝𝑡 is dynamically updated in a frame-by-frame manner, similarly to the update of the Q-table;

with the initial condition 𝑝1 = 1.0, where 𝛽 is the learning rate for transmission probability; 0 ≤ 𝛽 ≤ 1, and 𝑏𝑡 is the reward at Frame 𝑡, which is defined as

In order for (4) to be a valid transmission probability, it is necessary that 0 ≤ 𝐵succ, 𝐵fail, 𝐵wait ≤1.Similarly to (2), from (4) the updated value 𝑝𝑡+1 is an internally dividing point between 𝑝𝑡 and 𝑏𝑡 at ratio of 𝛽: (1 − 𝛽). Since 𝑝1 = 1.0 and 0 ≤ 𝛽 ≤ 1, an inequality

holds for any𝑡. Note that from (4), transmission probability 𝑝𝑡 at an active node which defers the packet transmission is also updated with reward 𝐵wait. This operation is introduced to avoid long-term deferral of packet transmission, particularly for small transmission probability 𝑝𝑡.Meanwhile, Q-table is kept unchanged when packet transmission at an active node is deferred, as shown in (2) and (3). Notice here that the protocol 𝛽 = 0.0 degenerates into its original one, FSA and ALOHA-Q without transmission probability, since 𝑝𝑡 = 1.0 for any𝑡.

[Example 2] A trace of transmission probability 𝑝𝑡 in the case of a concise example in Figure 1 is given in Table 1 for 𝛽 = 0.5. For example, unsuccessful packet transmission of Node 1 in Frame 2 decreases its transmission probability, from𝑝2 = 1.0 to 𝑝3 = (1 − 𝛽)𝑝2 − 𝛽𝐵fail = 0.55. Then,successful packet transmission of Node 1 in Frame 3 increases 𝑝𝑡as 𝑝4 = (1 − 𝛽)𝑝3 + 𝛽𝐵succ =0.775.

Table 1. Transmission probability 𝑝𝑡 in the case of Figure 1 for𝛽 = 0.5, 𝐵succ = 1.0 and 𝐵fail = 0.1

5.SIMULATION RESULTS

The effect of the transmission probability on the performance of FSA and ALOHA-Q is confirmed by means of exhaustive computer simulation. The simulation is programmed in Clanguage. The values of the parameters used are tabulated in Table 2.

Table 2. Simulation parameters

Here, it follows from (6) that 0.1 ≤ 𝑝𝑡 ≤ 1.0. We suppose a constant frame length of 𝐿 = 50 and two scenarios; the one is the case of excessive number of nodes 𝑁 = 100 (= 2𝐿), which may cause overloaded traffic condition, and the other is the case of𝑁 = 50 (= 𝐿).

Throughput and the average of packet transmission probability are shown in Figures 2 and 3, respectively.

Figure 2. Throughput for 𝐿 = 50 and (a) 𝑁 = 100 and (b) 𝑁 = 50.

Figure 3. Average of transmission probability for 𝐿 = 50 and (a) 𝑁 = 100 and (b) 𝑁 = 50.

From Figure 2(a) it is observed that for 𝑁 = 100, the introduction of adaptive transmission probability 𝑝𝑡 succeeds in improve throughput for both original cases of ALOHA-Q and FSA, which are equivalent to the case of 𝛽 = 0.0. Meanwhile, from Figure 2(b) no effect of the adaptive transmission probability can be found on the throughput of ALOHA-Q for 𝑁 = 50, which implies that Q-learning may accomplish ideal slot assignment to each node with or without transmission probability. By contrast, slight throughput degradation is caused in FSA for 𝑁 = 50.Figures 3(a) and 3(b) show the average of the transmission probability 𝑝𝑡 in ALOHA-Q and FSA for 𝑁 = 100 and 𝑁 = 50, respectively. It follows from Figure 3 that the transmission probability in average decreases except for the case of ALOHA-Q with adaptive transmission probability for𝑁 = 50, as the packet generation probability𝜆increases. Exceptionally, in ALOHA-Q with adaptive transmission probability for 𝑁 = 50 the average of packet transmission probability is almost kept constant 𝑝𝑡 for any 𝜆 . In the original ALOHA-Q and FSA, the transmission probability is constantly set to 𝑝𝑡 = 1.0 for any 𝑡. As shown in Figures 2(a) and 3(a), the adaptation of transmission probability with Q-learning serves to improve the throughput for the overloaded traffic condition; 𝑁 = 100.

Throughput of the original ALOHA-Q in Figure 2(a) is worse than that of the original FSA, particularly for around 10−3 < 𝜆 < 0.3. This deterioration is caused by the rapid increase inthe probability of packet collision, as shown in Figure 4(a). In contrast, as shown in Figure 4(b), ALOHA-Q with transmission probability can realize low packet collision probability, which coincides with high throughput of ALOHA-Q with or without transmission probability shown in Figure 2(b).

Figure 4. Packet collision probability for 𝐿 = 50 and (a) 𝑁 = 100 and (b) 𝑁 = 50.

In the original ALOHA-Q, the update of the Q-table through Q-learning may narrow the selection range of possible slots in a frame for packet (re)transmission. If a sufficient number of slots, compared to the number of active nodes at the beginning of a frame, exist in a frame, packet collision due to such narrowing can be avoidable. However, packet collision is more likely to happen, if there exist an excessive number of active nodes, compared to the frame length. The possibility that two or more active nodes have an identical slot number whose 𝑞𝑡,ℓ i is maximum in the Q-table increases. Consider the case of 𝜆 = 10−2 as an example. The distribution of the number of transmitted packets in slot is depicted in Figure 5.

Figure 5. Distribution of the number of transmitted packets in slot for 𝐿 = 50, 𝑁 = 100 and 𝜆 = 10−2 .

From Figure 5, it can be observed that idle slots of ALOHA-Q with 𝛽 = 0.0 are about 10%, successful slots, which is equivalent to throughput, is less than 10%, and packet collision with two packets happens with ratio of around 70%.

From the above observation, it appears that only a fraction of nodes succeeds in packet transmission and that the rest of nodes are likely to be included in packet collision or to defer packet transmission. In order to examine the fairness among nodes, in Figure 6 we show Jain’s fairness index [13] with respect to throughput. Jain’s fairness index is defined as

where 𝑆𝑛 is throughput of node 𝑛.

Figure 6. Fairness index with respect to throughput for 𝐿 = 50 and (a) 𝑁 = 100 and (b) 𝑁 = 50. From Figure 6(a) the fairness index of FSA with or without transmission probability is kept 1.0. However, the fairness index of ALOHA-Q falls down, which degradation can be mitigated to some extent by introducing transmission probability. In contrast, from Figure 6(b), Jain’s fairness index of nearly 1.0 can be maintained in the range of large packet generation probability for 𝑁 =50.

In consequence, from Figures 2-6 incorporation of adaptive transmission probability improves the performance of ALOHA-Q and FSA for the case of overloaded traffic condition and exhibits comparable performance to the original ALOHA-Q for the case of moderate traffic condition.

6.CONCLUSION

The author declares no conflict of interest.

REFERENCES

[1] E. Soltanmohammadi, K. Ghavami and M. Naraghi-Pour, “A survey of traffic issues n machine-to machine communications over LTE,”IEEE Internet Things J., Vol. 3, No. 6, pp. 865–884, Dec. 2016, doi: 10.1109/JIOT.2016.2533541.

[2] S. Bhandari and S. Moh, “A MAC protocol with dynamic allocation of time slots based on traffic priority in wireless body area networks,” Intl. J. Comput.Netw. & Commun., Vol. 11, No. 4, pp. 25–41, July 2019, doi: 10.5121/ijcnc.2019.11402.

[3] N. Azdad and M. Elboukhari, “A novel medium access control strategy for heterogeneous traffic inwireless body area networks,” Intl. J. Comput. Netw. & Commun., Vol. 16, No. 2, pp. 117–128, Mar. 2024, doi: 10.5121/ijcnc.2024.16208.

[4] T. Ferrer, S. Cespedes and A. Becerra, “Review and evaluation of MAC protocols of satellite IoT systems using nano satellites,” Sensors, Vol. 19, Issue 8, ID 1947, Apr. 2019, doi: 10.3390/s19081947.

[5] U. Draz, T. Ali, N. A. Zafar, A. S. Alwadie, M. Irfan, S. Yasin, A. Ali and M. A. K. Khattak,“Energy efficient watchman based flooding algorithm for IoT-enabled underwater wireless sensorand actor networks, ”ETRI J., Vol. 43, Issue 3, pp. 414–426, Apr. 2021, doi: 10.4218/etrij.2019-0591.

[6] N. Abramson, “The ALOHA system: another alternative for computer communications,” in Proc. AFIPS 1970, Houston, TX, pp. 281–285, Nov. 1970, doi: 10.1145/1478462.147850.

[7] Y. He and X. Wang, “An ALOHA-based improved anti-collision algorithm for RFID systems, ”IEEE Wireless Commun., Vol. 20, No. 5, pp. 152–158, Oct. 2013, doi: 10.1109/MWC.2013.6664486.

[8] S. H. Park, P. D. Mitchell and D. Grace, “Reinforcement learning based MAC protocol (UWALOHA-Q) for underwater acoustic sensor networks,” IEEE Access, Vol. 7, pp. 165531–165542, Nov. 2019, doi: 10.1109/ACCESS.2019.2953801.

[9] M.Zhang, L.de Alfaro and J.J.Garcia-Luna-Aceves, “Making slotted ALOHA efficient and fair using reinforcement learning,” Comput. Commun., Vol.181, pp.58–68, Jan. 2022, doi: 10.1016/j.comcom.2021.09.018

[10] A.Albijanic, S.Tomovic and I.Radusinovic, “Simulation analysis of the impact of underwater channel reliability on machine learning-optimized framed-Aloha MAC protocols,” in Proc. Intl. Conf. Inform. Tech. (IT 2024), Zabliak, Montenegro, Feb. 2024, doi: 10.1109/IT61232.2024.10475776.

[11] F. C. Schoute, “Dynamic frame length ALOHA,”IEEE Trans. Commun., Vol. COM-31, No. 4, pp. 565-–568, Apr. 1983, doi: 10.1109/TCOM.1983.1095854.

[12] Y. Chu, P. D. Mitchell and D. Grace, “ALOHA and Q-Learning based medium access control for wireless sensor networks,” in Proc. Intl. Symp.Wireless Commun. Syst. (ISWCS 2012), Paris, France, pp. 511–515, Aug. 2012, doi: 10.1109/ISWCS.2012.6328420.

[13] R. Jain, D. Chiu and W. Hawe, “A quantitative measure of fairness and discrimination for resource allocation in shared computer systems,” DEC Res. Rep., No. DEC-TR-301, Sep. 1984.

[14] C. T. Lau and C. Leung, “Capture models for mobile packet radio networks,” IEEE Trans. Commun., Vol. 40, No. 5, pp.917–925, May 1992, doi: 10.1109/26.141457.

AUTHOR

Dr. Katsumi Sakakibara received the B.E., M.E., and Ph.D. degrees in communication engineering from Osaka University, Suita, Japan, in 1985, 1987, and 1994, respectively. Since 1995, he has been with Okayama Prefectural University, Soja, Japan, where he is currently a Professor with the Department of Information and Communication Engineering. His research interests include algebraic coding theory, error-control protocols, random access protocols, and the analysis of communication systems. He is a member of the IEEE and the IEICE.