On the Capacity of Multihop Slotted ALOHA Networks with Regular Structure

In this paper we investigate the capacity of networks with a regular structure operating under the slotted ALOHA access protocol. We first consider circular (loop) and linear (bus) networks and then proceed to two-dimensional networks. For one-dimensional networks we find that the capacity is basically independent of the network average degree and is almost constant with respect to network size. For two-dimensional networks we find that the capacity grows in proportion to the square root of the number of nodes in the network provided that the average degree is kept small. Furthermore, we find that reducing the average degree (with certain connectivity restrictions) allows a higher throughput to be achieved. We also investigate some of the peculiarities of routing in these networks.     

On the Capacity of Slotted ALOHA Networks and Some Design Problems

Packet switching over broadcast channels with random access schemes is of current interest for local distribution system and for satellite channels. This mode of operation is useful when the communicating devices are mobile and when the ratio of the peak to average data rate requirement of each device is high. Such systems have been analyzed for the case in which all communicating devices are within an effective transmission range of each other; either directly or through the satellite. In this paper, we address broadcast networks in which originating devices cannot directly reach the destination receiver. Thus, devices are introduced which receive these packets and repeat them to the destination. The capacity (maximum throughput) of such systems is determined, and design problems related to the number of repeating devices and the usefulness of directional antennas are resolved.     

The Spatial Capacity of a Slotted ALOHA Multihop Packet Radio Network with Capture

In this paper we determine throughput equations for a packet radio network where terminals are randomly distributed on the plane, are able to capture transmitted signals, and use slotted ALOHA to access the channel. We find that the throughput of the network is a strictly increasing function of the receiver's ability to capture signals, and depends on the transmission range of the terminals and their probability of transmitting packets. Under ideal circumstances, we show the expected fraction of terminals in the network that are engaged in successful traffic in any slot does not exceed 21 percent.     

Optimal Retransmission Control of Slotted ALOHA Systems

Multiple access methods constitute an important subject in the design of distributed computer communication systems. A technique which has attracted considerable attention is the slotted ALOHA random access scheme. In this paper, based on some analytical properties of the slotted ALOHA system [9], we establish the optimality property of the multiple control limit policy among the class of multiple-action policies. The previously reported control limit policy [6] is just a special case. We then derive the optimal retransmission control (ORC) policy which is optimal among the whole class of stationary policies. The superiority of the ORC policy is also illustrated by numerical examples. The performance of the ORC policy for various potential input traffic intensity is presented.     

Analysis of Mobile Radio Slotted ALOHA Networks

Given a mobile terminal transmitting a message to some receiver, the level at the receiver will be affected by path loss and by fading phenomena. Transmissions from different terminals will suffer different attenuations on their respective ways to the receiver and will therefore yield different levels at the receiver. Thanks to the capture effect, the receiver will now be able to read the message with the strongest signal, provided that it is sufficiently stronger than its contenders. In a mobile radio ALOHA network this means that a packet collision need not necessarily destroy all packets involved. A Markov model is developed for slotted ALOHA networks with capture and it is shown that the throughput in such a network can be markedly greater than the famous1/e. Perhaps even more important is the result that such networks are very stable under overload.     

Slotted ALOHA for high-capacity voice cellular communications

Slotted ALOHA is proposed as a multiple access scheme for high capacity voice cellular communications in mobile radio environment. The performance of such a system, in the presence of fading and shadowing, is evaluated for both mobile-to-base and base-to-mobile links, in terms of number of supported conversations per cell, under some constraints on maximum tolerable delay. The numerical results show that a system of this sort can compete with other multiaccess schemes currently considered, such as TDMA, FDMA, and even CDMA. A heuristic stability analysis is also presented, showing that the proposed system does not suffer from instability problems     

On the Stability of Slotted ALOHA Systems

In this correspondence we prove the following properties of the stability of the finite population model of slotted ALOHA systems. 1) The input-output packet flow balance principle [1] and the concept of expected drift [2] used for the stability analysis of the slotted ALOHA system are mathemtaically equivalent. 2) The slotted ALOHA system can only have either one stable equilibrium point or three equilibrium points, with the first one and the third one stable and the second one unstable. 3) If the retransmission probability (which is assumed to be greater than the probability of new packet generation) is less than or equal to2/N, whereNis the total number of active users in the system, then the system has only one stable equilibrium point.     

Revisiting Slotted ALOHA: Density Adaptation in FANETs

Unmanned aerial vehicles have been widely used in many areas of life. They communicate with each other or infrastructure to provide ubiquitous coverage or assist cellular and sensor networks. They construct flying ad hoc networks. One of the most significant problems in such networks is communication among them over a shared medium. Using random channel access techniques is a useful solution. Another important problem is that the variations in the density of these networks impact the quality of service and introduce many challenges. This paper presents a novel density-aware technique for flying ad hoc networks. We propose Density-aware Slotted ALOHA Protocol that utilizes slotted ALOHA with a dynamic random access probability determined using network density in a distributed fashion. Compared to the literature, this paper concentrates on proposing a three-dimensional, easily traceable model and stabilize the channel utilization performance of slotted ALOHA with an optimized channel access probability to its maximum theoretical level, 1/e, where e is the Euler’s number. Monte-Carlo simulation results validate the proposed approach leveraging aggregate interference density estimator under the simple path-loss model. We compare our protocol with two existing protocols, which are Slotted ALOHA and Stabilized Slotted ALOHA. Comparison results show that the proposed protocol has 36.78% channel utilization performance; on the other hand, the other protocols have 24.74% and 30.32% channel utilization performances, respectively. Considering the stable results and accuracy, this model is practicable in highly dynamic networks even if the network is sparse or dense under higher mobility and reasonable non-uniform deployments.

     

On the Capacity of Single-Hop Slotted ALOHA Networks for Various Traffic Matrices and Transmission Strategies

In this paper we formulate a general model of the capacity of single-hop slotted ALOHA networks. We find that the capacity can be expressed as a function of the nodal degree (i.e., number of nodes within range of a transmitter). We than evaluate this model for various traffic matrices. In order to satisfy the requirements of a given traffic matrix, the transmission power is selected accordingly and this determines the degree of the nodes and, hence, the network performance. Finally we compare our results to simulation studies.     

改进动态帧时隙ALOHA算法

ALOHA型算法是一种防碰撞算法,适用于标签数目较少的情况。当标签数目逐渐增大时,通常需要指数倍增长的时隙数才能识别出这些标签。文中提出了一种改进的动态帧时隙ALOHA算法,它首先估计未被识别的标签数,然后调整相应帧长,从而获得最佳系统效率。仿真结果显示,当标签数为500时,文中所提出算法较传统算法的系统时延减少为原来的1／2。     

An Optimum Retransmission Cut-Off Scheme for Slotted ALOHA

The retransmission cut-off is not needed for a stable operation of slottedALOHA if the new packet generation rate is below a critical limit. Thethroughput never reaches its maximum value if the new packet generation rateis less than this critical limit irrespective of the number of transmissions.The maximum throughput is attained by adjusting the number of transmissions,pertaining to the new packet generation rate exceeding the critical limit.A complete analysis for the new packet generation rate with the properadjustment of the number of transmissions that maximize the channel throughputin a Rayleigh fading channel is executed. A stable operating region in termsof the packet rejection probability and the corresponding number oftransmissions is devised.     

Slotted ALOHA multihop packet radio networks with directional antennas

The use of directional antennas in multihop packet radio networks using slotted ALOHA access is considered. Tractable approximations to the network performance in terms of expected forward progress are derived. Results show that packet collisions can be strongly reduced already with moderate gain antennas to allow for a substantial increase in network performance.<>     

改进型帧时隙ALOHA防碰撞算法研究

为进一步提高RFID系统中电子标签防碰撞算法的识别效率,对帧时隙ALOHA防碰撞算法的性能进行分析,提出一种结合精确标签估计和二进制搜索的改进型帧时隙ALOHA算法.将识别过程分为标签估计和标签识别两个阶段,在标签估计算法中引入碰撞概率上、下限参数,并精确估计标签数量对初始帧时隙大小进行优化;在标签识别阶段,利用二进制搜索算法对时隙内的碰撞标签进行快速识别.通过对识别过程进行仿真结果表明:改进的算法改善了防碰撞性能,提高了RFID系统的标签识别效率.     

Probabilistic Dynamic Framed Slotted ALOHA for RFID Tag Identification

In this paper, we study radio frequency identification tag identification problems using framed slotted ALOHA protocol. Each tag will be assumed to participate in the contention with a certain probability. Then, the frame size and the probability will be dynamically controlled by the reader in every reading round so that all the tags can be detected in a short period of time. Moreover, we propose a practical way of controlling the probability in terms of transmit power control, assuming Additive White Gaussian Noise channel or flat Rayleigh fading channel. Computer simulation results demonstrate the effectiveness of the proposed method.     

基于分组动态帧时隙ALOHA防碰撞算法研究

为解决射频识别系统中多标签防碰撞问题,在现有ALOHA算法的基础上提出了一种改进的分组动态帧时隙ALOHA算法。当大量标签同时进入阅读器识别范围内时,算法通过设置一个阈值把要响应的标签分成两组,符合条件的一组去响应阅读器,不符合条件的暂时不响应,该算法通过分组限制响应标签数量达到较高的识别效率。仿真结果表明,该算法在标签数大于256甚至更多时识别效率也能维持在相对较高的数值。     

基于碰撞预检测的分组动态帧时隙ALOHA防碰撞算法

本文在分析传统 ALOHA 算法的基础上,提出了一种基于碰撞预检测的分组动态帧时隙 ALOHA 防碰撞算法。该算法通过分组限制响应的标签数量,并且在组内预先发送一个短暂的碰撞检测帧去检测帧内的情况,达到在阅读器与标签之间建立一个完全无碰撞信道的目的。仿真结果表明,当标签数量较大时,该算法能有效减少总数据传输量,提高识别效率。     

Comments on "Optimal Retransmission Control of Slotted ALOHA Systems"

A controlled Markov model of the slotted ALOHA system in which the control parameter is the retransmission probability and a set of controls is the interval [0, 1] is considered. Numerical results are presented which show that the policy which maximizes the system's expected packet flow per time slot is not optimal. It is shown that, although it is not optimal, this policy can be considerably better than the optimal two-action control-limit policy.     

Performance Analysis of Slotted Multichannel ALOHA Systems with Capture in Microcellular Environments

ＰｅｒｆｏｒｍａｎｃｅＡｎａｌｙｓｉｓｏｆＳｌｏｔｔｅｄＭｕｌｔｉｃｈａｎｎｅｌＡＬＯＨＡＳｙｓｔｅｍｓｗｉｔｈＣａｐｔｕｒｅｉｎＭｉｃｒｏｃｅｌｌｕｌａｒＥｎｖｉｒｏｎｍｅｎｔｓＸｉａｏｘｉｎＱｉｕ；ＶｉｃｔｏｒＯ．Ｋ．Ｌｉ（Ｕｎｉｖｅｒｓｉｔｙｏ...     

Optimal Dynamic Framed Slotted ALOHA Based Anti-collision Algorithm for RFID Systems

In Radio Frequency IDentification (RFID) system, one of the most important issues that affect the data integrity is the collision resolution between the tags when these tags transmit their data to reader. In majority of tag anti-collision algorithm, Dynamic Framed Slotted Aloha (DFSA) has been employed as a popular collision resolution algorithm to share the medium when multiple tags respond to the reader’s signal command. According to previous works, the performance of DFSA algorithm is optimal when the frame size equals to the number of un-identified tags inside the interrogation zone. However, based on our research results, when the frame size equals to number of tags, collision occurs frequently, and this severely affects the system performance because it causes power consumption and longer tag reading time. Since the proper choice of the frame size has a great influence on overall system performance, in this paper we develop an analytical model to study the system throughput of DFSA based RFID systems, and then we use this model to search for an optimal frame size that maximizes the system throughput based on current number of un-identified tags. In addition to theoretical analysis, simulations are conducted to evaluate its performance. Comparing with the traditional DFSA anti-collision algorithm, the simulation results show that the proposed scheme reaches better performance with respect to the tag collision probability and tag reading time.