KR100903878B1 - Method for accessing to channel with RFID reader anti-collision in dense reader environment and reader thereof - Google Patents

Abstract

The present invention relates to a channel access method for preventing collision between readers in a dense reader environment and a reader for implementing the same.

According to the present invention, a reader selects a channel for communicating with a tag in a dense reader environment in which a plurality of readers of the channel number or more exist. At this time, when the selected channel is in use, the number of channels according to the number of readers in the dense reader environment is compared to dynamically calculate a hopping probability of different channels according to the predicted leader density. Channel hopping is performed according to the hopping probability. On the other hand, when the selected channel is idle or channel hopping is performed, random backoff is performed in consideration of the channel utilization rate according to the channel usage degree of each of the plurality of readers to access the obtained channel and communicate with the tag.

As such, since the optimal channel hopping probability and the size of the back off window are dynamically calculated in consideration of the density of the reader and the utilization rate of the channel, collision between the readers can be effectively reduced.

Radio Frequency Identification (RFID), Collision Avoidance, List Before Talk (LBT)

Description

Method for accessing channel to prevent collision between readers in dense reader environment and reader that implements it {Method for accessing to channel with RFID reader anti-collision in dense reader environment and reader

The present invention relates to a channel access method for preventing collision between readers in a dense reader environment and a reader for implementing the same. In particular, the present invention is a reader that occurs when an adjacent reader attempts to communicate with a tag using the same frequency at the same time in a dense reader environment in which a radio frequency identification (RFID) reader of the number of channels or more exists. The present invention relates to a method for preventing a collision between and a reader for implementing the same.

The present invention is derived from the research conducted as part of the IT growth engine technology development project of the Ministry of Information and Communication and the Ministry of Information and Communication Research and Development (Task Management No .: 2006-S-023-02, Task name: RFID system advancement technology development).

In Korea, 200KHz channel bandwidth is selected per channel in the frequency range of 5.5MHz from 908.5 to 915MHz, and LBT (Listen Before Talk, hereinafter referred to as 'LBT') and FH (Frequency Hopping) method in the US It is used in parallel.

Here, the LBT method is a method of first determining whether the selected frequency is being used by another reader and selecting another frequency channel when it is determined that the frequency channel is occupied.

This method is based on CSMA (Carrier Sensing Multiple Access), which first determines whether to use a channel. The CSMA method is a method of checking whether a channel is used by detecting a channel to be used when there is data to be transmitted by a station. That is, when it is determined that the channel to be used is idle, data is transmitted using the corresponding channel, and when it is determined that the channel is busy, the process of detecting the channel again after a predetermined time is repeated.

The CSMA method is divided into 'non-persistent', '1-persistent', and 'p-persistent' methods depending on the channel access method.

The 'non-persistent', '1-persistent', and 'p-persistent' methods are identical in that they detect the channel to use and, if it is determined that the channel is idle, transmit the data immediately using the channel. However, if it is determined that the channel is in use, there is a difference in how the channel is accessed.

'non-persistent' is a method of waiting for a random time after determining that the channel is in use and checking whether the channel is used again.

When the channel determines that the channel is in use, the '1-persistent' method continuously monitors the channel until the channel is idle, and immediately transmits data when the channel is idle. In this case, a collision occurs when two or more stations are monitoring the same channel.

The 'p-persistent' method is identical in that if the channel is determined to be in use, it will continue to monitor the channel until it is idle, but if the channel is idle, each station will have a probability of p (0≤p≤1). Determine whether to use the channel. However, if all stations cannot use the channel, it experiences a certain amount of delay and again decides whether or not to use the channel. In general, the unit time is the maximum propagation delay time of the stations monitoring the channel. The 'p-persistent' approach can greatly reduce the probability of collisions occurring when two or more stations are monitoring.

However, the RFID system using the LBT method in the domestic wireless facility technology standard does not define a specific method of whether to monitor the channel continuously or change the channel when determining that the channel is in use.

In addition, the method of continuously waiting until one channel is idle through LBT and then using the channel through competition depends on the ratio of stations selecting the same channel. In other words, when the stations select different channels evenly, the channel utilization efficiency is high, but when the ratio of selecting the same channel is high, the channel utilization efficiency is lowered.

Such a method is suitable for a centralized control method in which one controller determines whether to use a channel for each station, but has a disadvantage in that it is not suitable for a distributed control method in which stations select a channel.

In addition, when it is determined that the channel is in use through the LBT, the method of randomly selecting and hopping another channel cannot be said to be effective considering the overhead due to hopping.

In addition, random backoff is used to reduce the probability of collision between stations, where the performance depends on the size of the contention window. If the size of the contention window is large, the collision probability is reduced, but the overhead is large due to the empty slots, and in the opposite case, the collision probability is increased although the overhead of the empty slots is small. Therefore, there is a need for variable contention window size adjustment by the number of stations or the like.

The technical problem to be achieved by the present invention is to provide a channel access method and a reader implementing the same by dynamically changing the hopping probability of the channel and the size of the back-off window in accordance with the reader reader density of the channel in a dense reader environment will be.

The channel connection method which is a feature of the present invention for achieving the technical problem of the present invention,

A method of accessing a channel through which a reader communicates with a tag in a dense reader environment having a plurality of readers having a number of channels, the method comprising: determining whether the channel is idle by selecting a channel for communicating with the tag; ; When the channel is in use, performing channel hopping according to a hopping probability of another channel calculated according to a leader density, which is obtained by comparing the number of channels according to the number of readers in the dense reader environment; When the channel is idle or when channel hopping is performed, performing random backoff in consideration of a channel utilization rate according to a channel usage degree of each of the plurality of readers; And communicating with the tag by accessing a channel obtained through the random back off.

Reader which is a feature of the present invention for achieving the technical problem of the present invention,

A reader for accessing a channel for communicating with a tag in a dense reader environment having a plurality of readers having a number of channels, the reader comprising: a channel selector for selecting a channel for communicating with the tag; When the channel selected by the channel selector is in use, channel density is determined according to a hopping probability of other channels calculated according to leader density, where leader density is predicted by comparing the number of channels according to the number of readers in the dense reader environment. A channel operation control unit performing random backoff in consideration of a channel utilization rate of each channel usage degree of a reader of the dense reader environment when the channel is idle or when channel hopping is performed; And a communication unit which accesses a channel obtained through the random backoff and performs communication with the tag.

According to the present invention, in a dense reader environment, the channel hopping probability and the backoff window size are dynamically changed according to the channel density of the channel, so that even when the leader density is high, the empty channel is quickly searched to reduce latency and collision between the readers. It is possible to reduce the high throughput.

In addition, the order of hopping channels may be additionally determined in advance, thereby reducing overhead due to unnecessary hopping.

In addition, a method of using LBT, which is not clearly defined in the related art, is defined as a specific operation technique to provide an efficient reader collision prevention technique that can be applied to a dense reader environment.

DETAILED DESCRIPTION Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings so that those skilled in the art may easily implement the present invention. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the spirit or scope of the present invention. In the drawings, parts irrelevant to the description are omitted in order to clearly describe the present invention, and like reference numerals designate like parts throughout the specification.

Throughout the specification, when a part is said to "include" a certain component, it means that it can further include other components, without excluding other components unless specifically stated otherwise. In addition, the terms “… unit”, “module”, etc. described in the specification mean a unit that processes at least one function or operation, which may be implemented by hardware or software, or a combination of hardware and software.

Now, a channel access method for preventing collision between readers in a dense reader environment according to an embodiment of the present invention and a reader for implementing the same will be described in detail with reference to the accompanying drawings.

1 is a view for explaining a collision between readers in a dense reader environment according to an embodiment of the present invention.

As shown in FIG. 1, a collision of reader periods in a dense reader environment occurs when two or more readers 200 ₁ , 200 ₂ attempt to read the same tag 100 ₁ within an interference range.

Here, the dense reader environment refers to a case where a reader having a number of channels or more exists within a signal range in an area where an RFID signal exists.

In an embodiment of the present invention, a random backoff scheme is applied to a CSBT (Listen Before Talk, LBT) method based on Carrier Sensing Multiple Access (CSMA). Lower the probability of leader collisions occurring.

Here, the random back off method is a method for preventing a collision due to simultaneous access to a channel after channel sensing. After channel detection, a transmission is attempted after waiting for a randomly selected slot value within a contention window size. In other words, the station selecting the first slot preempts the channel. Stations that have failed in the race may have priority over other stations by using the reduced slot rank in the next race situation.

Next, a channel access method for reducing collision probability between readers in a dense reader environment as shown in FIG. 1 will be described in detail below.

2 is a block diagram showing the configuration of a reader according to an embodiment of the present invention.

As shown in FIG. 2, the readers 200 ₁ and 200 ₂ include a channel selector 220, a communication channel detector 240, a channel operation control unit 260, and a communication unit 280.

The channel selector 220 selects a channel to be used for communication between the readers 200 ₁ and 200 ₂ and the tag 100 ₁ . In this case, the channel selection method may be based on a random method and a sequence random method. In this case, when the channel is randomly selected, an inefficient problem of reconfirming the same channel being used may occur. Therefore, the sequence random method may be preferably used. The sequence random method is a method of sequentially searching for channels using an index sequence generated by generating an index sequence for all channels other than the current channel. This will search all channels only once. At this time, the order is determined randomly.

The communication channel detector 240 detects a frequency channel in communication between the adjacent readers 200 ₁ and 200 ₂ and the tag 100 ₁ . That is, the channel receives RSSI (Received Signal Strength Indication) of the channel.

The channel operation controller 260 determines whether the channel sensed by the communication channel detector 240 is idle, obtains an optimal probability of hopping to another channel according to the idle state, and dynamically sets the back-off window size. That is, if a channel is in use, the probability of hopping to another channel is calculated to determine whether to hop to another channel. When the channel is idle, the random backoff is calculated to occupy the channel through the random backoff.

The communication unit 280 transmits a signal to the tag 100 ₁ through a channel determined according to the hopping determination of the channel operation control unit 260 and the random backoff process.

Also a look through the 3 and 4 how to connect to the tag (Fig. _1, 100 1) and to the communication channel based on the configuration of FIG.

3 is a flowchart illustrating a channel access method of a reader according to an embodiment of the present invention, and FIG. 4 is a flowchart illustrating a channel hopping method of a reader according to an embodiment of the present invention.

As shown in Figure 3, the reader (Fig. 1, 200 _1, 200 ₂ in Fig. 2) selects a channel for communication with the tag (100 ₁ in Fig. 1) (S100). In this case, the channel selection may be in a predetermined order, that is, according to a sequence random scheme. In this case, if the channel utilization is high when searching for a channel, the same channel being used may not be selected even if the channel search occurs several times to find an empty channel.

In step S100, the selected channel is detected (S200) to determine whether the channel is used (S300).

At this time, if the channel is busy (busy) calculates the probability to hop to another channel (S400). Here, the hopping probability of the channel is to predict the leader density of the current environment and to hop randomly according to the predicted result when the channel is in use. Therefore, the characteristic of the reader density (number of readers / number of channels) of the channel is important in the probability calculation.

If the channel's reader density is less than or equal to '1', this environment is called sparse mode, and there is not much competition with other readers in the same channel. Therefore, there is a high probability of occupying a channel by back-off competition after LBT, and another channel is empty even if the channel occupancy fails. In this case, it is better to hop to another channel than to wait on the same channel.

On the other hand, if the reader density of the channel is more than '1', such an environment is called a dense mode, and there may be a lot of competition for channel occupancy with other readers. In the back-off competition after LBT, the success rate of channel occupancy is relatively low, and even if it hops to another channel, there is a low possibility that an empty channel exists. Therefore, it is better to set the hopping probability lower in this case, because waiting on the same channel may be advantageous than hopping to another channel.

As such, the hopping probability of the other channel is dynamically calculated according to the leader density of the channel. The detailed process of calculating the hopping probability is as shown in FIG. 4.

First, in order to measure the density of the leader environment, the success rate and the channel utilization in the back-off competition are predicted and used as parameters of probability calculation.

, Contention Loss Probability)을 정의한다.The first parameter is the probability that the reader will compete with other readers during the back off of the channel.

, Contention Loss Probability).

Equation 1 uses an exponential averaging method, which adds a weight to a recent value and adds it to a previous value.

는 경쟁에 의해 얻어지는 현재 값을 의미하며 경쟁에서 이기면 '0', 지게 되면 '1' 값을 가지게 된다. 결과적으로

는 리더 간의 경쟁에서 지게 될 확률을 나타낸다.This approach can be more adaptable to mobile environments, where the number of readers and the amount of data transfer vary from the simple arithmetic mean. In Equation 1, 'i' denotes the ID of the reader and 'n' denotes the number of calculations. Also,

Means the current value obtained by competition, and has a value of '0' if winning, and '1' if losing. As a result

Represents the probability of losing the competition between leaders.

, Utilization)을 정의한다.The second parameter monitors each reader's channel usage and calculates channel utilization (

, Utilization).

는 리더가 일정 시간(예를 들어, 5초) 간격으로 측정한 채널의 이용률이다. 리더기는 항상 자신이 속해있는 채널을 모니터링하여

를 얻어내며, 이를 이용하여

를 계산할 수 있다.

는 채널이 얼마만큼 사용되고 있는지를 나타내는 것으로 리더 환경의 밀도가 증가할수록 높은 값을 보이게 된다. Similarly, the exponential averaging method is used to adapt to the mobile environment.

Is the utilization of the channel as measured by the reader at regular intervals (eg 5 seconds). Readers always monitor their channels

To obtain the

Can be calculated.

Indicates how much the channel is being used. The higher the density of the reader environment, the higher the value.

, Hopping Probability)은 현재 채널이 사용중인 경우, 비어있는 채널을 찾기 위해 타 채널로 호핑하게 될 확률을 의미한다.Where the hopping probability (

Hopping Probability) refers to the probability of hopping to another channel to find an empty channel when the current channel is in use.

를 아래 수학식 3과 같이 정의한다.

Is defined as in Equation 3 below.

)은 두 파라미터 즉

와

가 클수록 작게 설정하는 것이 비어있는 채널을 호핑하기가 유리함은 S400 단계에 관한 설명에서 이미 설명한 바다. 또한, 두 파라미터 모두 채널의 밀도를 대변할 수 있다. 따라서,

와

가 증가함에 따라

는 감소하게 된다. Hopping probability (

) Are two parameters,

Wow

The larger the value is, the more advantageous it is to hopping an empty channel. In addition, both parameters can represent the density of the channel. therefore,

Wow

As increases

Will decrease.

Meanwhile, as described above, when the probability of hopping to another channel is calculated, it is determined whether channel hopping is performed according to the probability (S109).

If channel hopping is determined in step S109, the process returns to step S101 to try hopping to another channel.

If it is determined in step S109 not to perform channel hopping, the channel is continuously monitored and waited until the channel detected in step S103 is idle (S111).

If the channel is idle after waiting in step S111 or if the channel is not in use as a result determined in step S105, the back off window size is calculated (S700) to perform a random back off process (S800).

Each reader uses a back-off method to prevent two or more readers from connecting simultaneously and crashing. However, if the number of competing readers is not large, selecting and using an excessively large back-off window size may inefficiently waste that time. Therefore, the method of dynamically determining the backoff window size according to the utilization rate of the channel may be efficient. Before performing the backoff, the process of always calculating the backoff window is preceded, followed by the random backoff.

, Back-off Window Size)는 앞서 정의한 채널 이용률(

)를 이용하여 정해준다. 일단 다른 리더들과의 경쟁에서 실패한 스테이션은 다음 경쟁 상황에서 줄어든 만큼의 슬롯 순위를 사용함으로써 다른 스테이션에 비해 우선 순위를 가질 수 있다.Back off window size (

, Back-off Window Size) is the channel utilization (

Use) to determine. Once a station has failed in competition with other leaders, it can be prioritized over other stations by using fewer slots in the next race.

The back off window size can be calculated using Equation 4 below.

와

는 사전에 정의된 백 오프 윈도우의 최대값과 최소값을 의미 한다. 백 오프 윈도우는 항상 정수로 정의되므로 Round 운산을 수행한다.

Wow

Is the maximum and minimum values of the predefined back-off window. Since the back off window is always defined as an integer, it performs round operation.

If the random back off window size calculated in step S700 is smaller than the back off window sizes of other adjacent readers, the channel may be occupied.

In this case, if channel acquisition is not performed by determining whether to acquire the channel (S900), that is, when another adjacent reader first occupies the channel, the process returns to step S400.

When the channel is acquired, the corresponding channel is occupied (S1000) to communicate with the tag 100 ₁ .

As such, since the optimal channel hopping probability and the size of the back off window are dynamically calculated in consideration of the density of the reader and the utilization rate of the channel, collision between the readers can be effectively reduced.

5 and 6 are graphs for comparing a channel access method according to an embodiment of the present invention with a conventional LBT scheme.

5 and 6, in order to evaluate the performance of the present invention was compared with the performance of the basic LBT method that can be applied to multiple channels through simulation. Here, the basic LBT method is a basic algorithm that hops only after being occupied.

In the performance evaluation, it is assumed that there are 8 readers and 4 channels are available.

Performance evaluation is evaluated in two ways: one evaluates 'Throughput', which is the ratio of time spent by the reader to occupy the channel out of the total elapsed time. By measuring throughput to see how much data is actually being transmitted, you can see how efficiently the channel is being used. The other is the waiting time until the reader occupies the channel after the trigger is triggered. This indicates how long the user must wait to occupy and use the channel.

First, FIG. 5 compares 'Throughput' between a channel access method according to an embodiment of the present invention and a conventional LBT scheme. At this time, the ratio of time required for all readers to occupy the channel is defined as G (Offered load).

As shown in FIG. 5, the performance evaluation shows 'Throughput' when the number of readers is 4 (4 readers) and 8 (8 readers). As G increases, it increases constantly.

Simulation results show that the basic LBT basic throughput does not exceed 78% when the reader needs to use the channel. In the proposed algorithm, the throughput is 81%. That is, according to the proposed algorithm, the reader can obtain a high 'throughput' by efficiently searching for an empty channel.

Next, FIG. 6 compares a waiting time between a channel access method according to an embodiment of the present invention and a conventional LBT scheme. At this time, it shows distribution of waiting time when the number of readers is 8 (8 readers) and G is 0.8.

As shown in FIG. 6, when the reader needs to use the channel at an appropriate level, a basic LBT basic algorithm may have a waiting time of 15 seconds or more. On the other hand, in the proposed algorithm, all waiting time distributions are within 1.5 seconds. That is, according to the proposed algorithm, it can be seen that the waiting time is much smaller.

According to the above description, it is possible to define the probability of hopping to another channel and to dynamically change the size of the contention window to increase the data throughput and minimize the waiting time for the reader to occupy the channel.

Although the embodiments of the present invention have been described in detail, the scope of the present invention is not limited thereto, and various modifications and improvements of those skilled in the art using the basic concepts of the present invention defined in the following claims are also the rights of the present invention. It belongs to the range.

1 is a view for explaining a collision between the leaders in a dense reader environment according to an embodiment of the present invention.

2 is a block diagram showing the configuration of a reader according to an embodiment of the present invention.

3 is a flowchart illustrating a channel access method of a reader according to an embodiment of the present invention.

4 is a flowchart illustrating a channel hopping method of a reader according to an embodiment of the present invention.

5 is a graph comparing 'throughput' between a channel access method according to an embodiment of the present invention and a conventional LBT scheme.

6 is a graph comparing waiting time between a channel access method according to an embodiment of the present invention and a conventional LBT scheme.

Claims (10)

In a dense reader environment in which a plurality of readers having a number of channels or more exist, the method of connecting a reader to a channel for communicating with a tag, Determining, by the reader, a channel for communicating with the tag to determine whether the channel is idle; When the channel is in use, performing channel hopping according to a hopping probability of another channel calculated according to a leader density, which is obtained by comparing the number of channels according to the number of readers in the dense reader environment; When the channel is idle or when channel hopping is performed, performing random backoff in consideration of a channel utilization rate according to a channel usage degree of each of the plurality of readers; And Communicating with the tag by accessing a channel obtained through the random backoff Channel access method comprising a. The method of claim 1, Performing the channel hopping, Calculating the hopping probability using the probability of success in competition for channel occupation in the dense leader environment and the channel utilization rate; If the hopping probability exceeds a preset reference value, determining that the competition rate between readers in the same channel is low and performing hopping to another channel; And When the hopping probability is less than or equal to a predetermined reference value, determining that the competition rate between readers in the same channel is high and waiting in a channel selected by the reader Channel access method comprising a. The method of claim 2, Computing the hopping probability, Calculating a probability that the reader fails to occupy a channel in a back off competition with another reader; Calculating a channel utilization rate by monitoring a channel usage degree of each of the plurality of readers in the dense reader environment; Calculating a probability of hopping to another channel by using the calculated probability of failure and the channel utilization rate Channel access method comprising a. The method according to any one of claims 1 to 3, Performing the random back off, Calculating a size of a contention window for the backoff by performing a round operation based on a maximum value, a minimum value of the back off window, and the channel utilization rate; Performing a random back off using the size of the contention window for the back off; And Occupying a channel if the size of the contention window is relatively smaller than the size of the contention window of other adjacent readers; Channel access method comprising a. The method of claim 4, wherein The determining step, And generating an index sequence for the channels of the dense reader environment and selecting the channels in order using the index sequence. In a reader that connects to a channel for communicating with a tag in a dense reader environment in which a plurality of readers of channels or more exist, A channel selector for selecting a channel for communicating with the tag; When the channel selected by the channel selector is in use, channel density is determined according to a hopping probability of other channels calculated according to leader density, where leader density is predicted by comparing the number of channels according to the number of readers in the dense reader environment. A channel operation control unit performing random backoff in consideration of a channel utilization rate of each channel usage degree of a reader of the dense reader environment when the channel is idle or when channel hopping is performed; And A communication unit for communicating with the tag by accessing the channel obtained through the random back off Reader including. The method of claim 6, The channel operation control unit, When the probability of success in competition for channel occupancy in the dense reader environment and the hopping probability calculated using the channel utilization rate exceed a predetermined threshold, the competition rate between readers in the same channel is low and hopping to another channel is performed. And when the hopping probability is equal to or less than a predetermined reference value, determining that the competition rate between readers in the same channel is high and waiting for a channel selected by the channel selector. The method of claim 7, wherein The channel operation control unit, A reader for calculating the probability of hopping to another channel by using the probability of failing to occupy the channel in the back-off competition between readers and the channel utilization calculated by monitoring the channel usage of each reader. The method of claim 6, The channel operation control unit, Random backoff is performed by using a contention window size for the backoff calculated by performing a round operation based on a maximum value, a minimum value of the backoff window, and the channel utilization rate, and the other content of the contention window is adjacent to the other. And the channel selector occupies the selected channel if the reader is relatively smaller than the size of the contention window. The method according to any one of claims 6 to 9, The channel selector, And generating an index sequence for a plurality of channels in the dense reader environment and selecting channels sequentially using the index sequence.

Images