DOC

A New Dynamic Frame Slotted ALOHA Anti-Collision Algorithm Based On Grouping

By Alexander Hughes,2014-05-09 09:23
6 views 0
A New Dynamic Frame Slotted ALOHA Anti-Collision Algorithm Based On Grouping

    A New Dynamic Frame Slotted ALOHA Anti-

    Collision Algorithm Based On Grouping

    Yanhui Chen Riqing

    School of Electronic and Optical Engineering School of Electronic and Optical Engineering

    Nanjing University of Science and Technology Nanjing University of Science and Technology

    Nanjing, China Nanjing, China

    yanhui0107@163.com riqing.chen@gmail.com

    AbstractFor the problem of low system throughput (about reader. So we can divide the tags among the reader according 36.8%) of ordinary Dynamic Frame Slotted ALOHA algorithm, Grouping schematic diagram is shown below. to the distance.the article proposes a new dynamic frame slotted ALOHA

    (NDFSA) algorithm based on grouping. The algorithm firstly

    divides the whole tags into several groups according to the d2distance. Then for each group, the NDFSA algorithm with a d1random number is applied. Two unrelated quantities are used to dassure one tag. The simulation shows that the new algorithm has

    improved the throughput of the system by 50%.

    Keywords- RFID, anti-collision, grouping, random number

    Figure1 Grouping of tags I. FORWORD The electromagnetic field around the reader is divided into The RFID system consists of RFID tags, readers and data different areas. By adjusting the transmit power of the reader processing system. Antenna which exist in the electronic tag and the transmitting antenna gain of the reader, we can make and reader, are used to complete the transmission of data, as the effective distance of the reader d. Then first identify the well as energy. If the tag is within the read range of a reader, it tags in the range of distance d. After that turn them into silent will answer the reader. The reader reads the data, and then state-no longer respond to the commands of the reader. Then gives the data to the data processing system. change the effective distance of the reader, make it d1. And

    then identify the tags within this range. In the end, make the There are many kinds of anti-collision technology in the distance expanded to d2. Then identify the tags within this radio frequency identification system. Considered the forms of range. The recognition algorithm of each group will be communication, power, system complexity and cost factors, introduced below. TDMA is a more common solution. TDMA method can be

    divided into two kinds, one kind is ALOHA algorithm based on

    B. The principle of the new algorithm probability, the other kind is the Binary tree-based algorithm.

    Here we introduce a new type of Dynamic Frame Slotted In the normal dynamic frame slotted ALOHA algorithm, ALOHA Algorithm based on grouping (NDFSA). there is a time slot counter in every tag. Inside is a number of

    time slots which the tag randomly selected. When the slot

    number is the current time slot number, the tag will respond to II. THE INTRODUCTION OF THE NEW ALGORITHM

    the reader and transfer data to the reader. But the new

    algorithm requires the tag to add a random number. The A. The principle of grouping

    random number is 16-bit binary number. And only a 1, the According to the relevant principles of physics, the remaining bits are 0. The tag randomly selected time slot effective distance R between the tag and the reader is given by: number and the added random number are generated by the

    random number generator of the tag at different times. It means ,,,PG 4R2that they are unrelated to each other. The specific 16Sback (1)implementation steps of the new algorithm are as follows: P represents the transmit power of the reader, G represents First, the reader will send a command which contains the transmitting antenna gain of the reader, R represents the the initial frame length to all tags in the range of effective distance between the tag and the reader, represents effective distance; the tags randomly select a slot the Radar cross section of the tag, S represents the power backnumber. And load it within the time slot counter. In density back to the reader. By adjusting the transmit power of addition we assume that the random number inside the the reader-P and the transmitting antenna gain of the reader-G tag is already generated. can change the effective distance between the tag and the

    THE PERFORMANCE ANALYSIS OF THE NEW ALGORITHM III. The reader will send the command of REQUEST

    RANDNUM to request the tags to send their random In the normal dynamic frame slotted ALOHA algorithm numbers. Then the tag will determine whether the (DFSA), we assume that the total number of tags is N, and the current time slot number is the same as the number of frame length is L. The probability for each tag to choose one time slots in the internal slot counter or not. If yes, the slot among L slots is the same (1/L). So the probability of t tags tag will transmit its random number to the reader. If no, choose one slot is: it will wait until the next slot. At this time, there will tN-tbe two cases as follows: 11(:(:tP(Xt)C-??1;;;;NLL,~,~ (2) Case1: Only one tag transfers its random number to

    the reader. Then the reader will send the command of So the number of slots which have t tags in a frame is: REQUESTID (RANDNUM) which contains the

    random number to the tag. The tag will determine tN-t11(:(:tH(t)LC-1whether the random number is the same as its own (3) N;;;;LL,~,~random number. If yes, it will transfer its ID to the

    reader. If no, it will wait until the next frame. When t=0, it is a free slot. When t=1, it is a success slot. Case2: There are two or more than two tags Otherwise, it is a collision slot. Their expected values are: transferring their random numbers to the reader. For 00N-N111example, there are three tags. Their random numbers (:(:(:0IH()LC-L-???011 (4) ;;;;;;NLLL,~,~,~are 00010000000000001000000000000000

    0000000000010000. Then the random number which 111N-N111(:(:(:1the reader receives will be x00x0000000x0000. The SH()LC-N- (5) ???111;;;;;;NLLL,~,~,~reader will divide it into three numbers:

    00010000000000001000000000000000CLIS?;; (6)0000000000010000. Afterwards, the reader will send In the dynamic frame slotted ALOHA algorithm, system three commands REQUESTID (RANDNUM)

    throughput is the utilization of slots. That is the percentage of respectively to the current time slot tags. The

    success slots number. After analysis, we can know that when RANDNUM are the three random numbers

    N=L, the system throughput can reach maximization. At this respectively. After the tag receives the command, the

    time, collision slots number is: tag will determine whether the RANDNUM number is

    the same as its own random number or not. If yes, the 11NN1tag will transmit its ID to the reader. If no, it will wait CNN()N()?;;;; (7) 11NNuntil the next command.

    So the probability of 2 tags choose one slot is: After the reader receives the ID, it will determine 22N-whether collision happens or not. If yes, the reader will 11(:(:2P(X)C-??21;;;;Nidentify the collision tags (we will introduce next). If NN,~,~ (8) no, the reader will identify the tag correctly. The flow

    chart is as follows: The probability of 3 tags choose one slot is:

    33N-START11(:(:3P(X)C-??31;;;;NNNWhether collide ,~,~ (9) Initialization of NohappenstagsWe assume that there are 128 tags, and the frame length is Yes128. From the 7th expression, we can get collision slots Reader request number C, and it is 34.From the 8th expression, we can get that tags to send Reader divide random numbersthe slots number which 2 tags choose one slot is 24, and it is random number

    70.59% of all the collision slots. From the 9th expression, we Nocan get that the slots number which 3 tags choose one slot is 8, Whether current Reader send REQUESTID(RANDNUM)time slot is the same and it is 23.53% of all the collision slots. The others are only as own time slot5.88%. This shows that most collision happens when two or YesWhether RANDNUM three tags choose one slot to transfer data. And the probability Tags send Nois the same as own of 4 tags or more than 4 tags choose one slot is very small. random numbersnumberYesThe new algorithm above-mentioned reduces the collision Tags send IDprobability greatly by means of tags choosing random numbers.

    We can also assume that the total number of tags is N, and the YesWhether collide happensframe length is L. As the random number is 16-bit binary

    number. And only a 1, the remaining bits are 0. The probality Identify Nocollision tagsof choose 1 random number is 1/16. So the probality of 2 tags Identify tag choose the same slot and the same random number is: correctly

    222N-111(:(:(:2 PC-1;;;;;;1N0.55LL16,~,~,~ (10)0.5Likewise,the of k (k>1)tags choose the same slot and the 0.45same random number is:

    0.4kN-kk111(:(:(:k吞吐率 PC-10.35;;;;;;kNLL16,~,~,~ (11)分组前NDFSA0.3分组后NDFSAWhen L=128, N=100, we get that P<0.001, P<0.00001.In 1k0.25other words, the new algorithm confirm one tag through two 0.2unrelated variables. By comparison with one variable confirms 0100200300400500600700标签数 one tag, it can reduce the collision probality, and improve the

    system efficiency. Figure 4 the throughput comparison chart between grouping

    and no grouping Through analysis above, we can know the new algorithm

    can reduce the collision probality greatly. And the probality of From figure 3, we can know that the throughput of NDFSA 2 tags collide is the largest. When collide happens, the reader up to about 0.55. But the other algorithms only up to about will send a command which the frame length is 2 or 4 to 0.368. From figure 4, we can know that ungrouped NDFSA identify tags. algorithm throughput are declining with the increase of the

    number of tags (Less than 0.5, about 0.45). While the grouped In the normal dynamic frame slotted ALOHA algorithm, NDFSA algorithm throughput can still be maintained at a there are usually 4 methods as below to estimate the number of higher level. The above grouping method is under the condition remaining tags. (CCCare free slot numbersuccess 012 that tags are uniformly distributed. But in fact, tags are not slot number and collision slot number respectively.) uniformly distributed. Next we will assume that tags are

    NC2 .( DFSA1) randomly distributed. Figure 5 is the throughput comparison left2chart between uniformly distributed and randomly distributed .(DFSA2) N.C239tags in NDFSA algorithm. left2

    '(:CC(:00;;;;'0.55 .N can meet ,C C NN-CC-C01left111min;;;;N';;;;0.5CC,~22,~0.45Care the expected values of CCC.(DFSA3) 2012

    0.41NN吞吐率NN-C .N can meet C-(-)()?;111left1ratio0.35LL-1, 标签均匀分布0.3标签随机分布C=C/L. (DFSA4)ratio20.25Next we will use MATLAB software to simulate the 0.2system performance. Figure 3 is the throughput comparison 0100200300400500600700标签数chart between different DFSA algorithms and NDFSANew

    Dynamic Frame Slotted ALOHAalgorithm.The Initial frame Figure 5 the throughput comparison chart between length is 128. Figure 4 is the throughput comparison chart uniformly and randomly distributed tags in NDFSA algorithm between grouping and no grouping.(We assume that tags are From figure 5, we can know that compared with uniformly 0.55uniformly distributed.) distributed, when tags are randomly distributed, the system 0.5performance is worse. With the increase of the number of tags,

    0.45the throughput is less than 0.5,about 0.47. But when tags are

    uniformly distributed, the system throughput is above 0.5. This 0.4shows that the above algorithm is more suitable for the 0.35occasion that the tags are uniformly distributed around the

    reader. 0.3吞吐率

    0.25DFSA1DFSA2IV. CONCLUSION DFSA30.2DFSA4This paper presents a new dynamic frame slot algorithm NDFSAwith a random number, and run a simulation using MATLAB 0100200300400500600700标签数simulation software. Simulation results show that the algorithm

    is effective to improve the system performance. Compared Figure 3 the throughput comparison chart between different with normal DFSA algorithms, the throughput of the system DFSA algorithms and NDFSA algorithm

[3] I. S. Jacobs and C. P. Bean, “Fine particles, thin films and exchange are increased by 50%. The algorithm is especially suitable for anisotropy,” in Magnetism, vol. III, G. T. Rado and H. Suhl, Eds. New uniformly distributed tags and a lot of tags. When increasing York: Academic, 1963, pp. 271350. the number of tags, the system can also maintain a higher [4] K. Elissa, “Title of paper if known,” unpublished. throughput. [5] R. Nicole, “Title of paper with only first word capitalized,” J. Name Stand. Abbrev., in press.

[6] Y. Yorozu, M. Hirano, K. Oka, and Y. Tagawa, “Electron spectroscopy studies on magneto-optical media and plastic substrate interface,” IEEE [1] G. Eason, B. Noble, and I. N. Sneddon, “On certain integrals of Transl. J. Magn. Japan, vol. 2, pp. 740741, August 1987 [Digests 9th Lipschitz-Hankel type involving products of Bessel functions,” Phil. Annual Conf. Magnetics Japan, p. 301, 1982]. Trans. Roy. Soc. London, vol. A247, pp. 52955the1, April 1955. [7] M. Young, The Technical Writer's Handbook. Mill Valley, CA: (references) University Science, 1989. [2] J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.6873.

Report this document

For any questions or suggestions please email
cust-service@docsford.com