KR102675807B1 - Methods for controlling retransmission of packet and appratuses thereof - Google Patents

Abstract

The present embodiments can provide a method and apparatus for controlling packet retransmission. In particular, it is possible to provide a method and device for controlling packet retransmission that adaptively adjusts the backoff time for packet transmission by estimating the network load. Specifically, a packet that adaptively adjusts the backoff time for packet retransmission by calculating the backoff parameter that maximizes throughput by estimating the number of backlogged terminals to which the access point wants to transmit packets. A method and device for controlling retransmission can be provided.

Description

Method and apparatus for controlling packet retransmission {METHODS FOR CONTROLLING RETRANSMISSION OF PACKET AND APPRATUSES THEREOF}

The present embodiments relate to a method and apparatus for controlling packet retransmission.

Recently, the Internet has evolved from a human-centered network where humans create and consume information to an Internet of Things (IoT) network that exchanges and processes information between distributed components such as objects. To implement the Internet of Things network, there are commercial networks such as Long Range (LoRa) and Sigfox, which are low-power wide area wireless communication networks (LPWAN) that operate in unlicensed bands, and these are wireless channel access methods in the media access control layer. ALOHA Protocol is used.

Specifically, in LoRa networks, devices adopt the Pure ALOHA method for packet transmission. And the Pure ALOHA method is a multiple access control protocol in which devices on the network do not synchronize with each other and do not receive a communication channel before transmitting packets. Therefore, while each device is sending packets through the same channel, transmission failure may occur due to packet transmission collision. At this time, when devices retransmit packets, if they simply retransmit randomly between 1 and 3 seconds, the larger the number of devices that want to transmit packets to the network, i.e. the backlog size, the more severe network congestion occurs. Problems that may result may occur.

Therefore, there is a need for a packet retransmission control method and device that can improve communication network efficiency in unlicensed bands for the Internet of Things by minimizing packet transmission collisions between devices.

Against this background, the present embodiments provide a method and apparatus for controlling packet retransmission that estimates network load and adaptively adjusts the backoff time for packet transmission.

In one aspect, the present embodiments are a method for an access point (AP) to control packet retransmission of a terminal, and a back to transmit packets based on an idle period in which packets are not received at specific times. A terminal number estimation step for estimating the number of backlogged terminals, a parameter calculation step for calculating a backoff parameter that maximizes throughput based on the estimated number of backlogged terminals, and the number of backlogged terminals. and a transmission step of transmitting at least one of the backoff parameters to the backlogged terminal.

In another aspect, the present embodiments relate to a method in which a terminal performs packet retransmission, the number of backlogged terminals and the backlogged number estimated based on an idle period in which packets are not received at a specific point in time. A packet comprising a receiving step of receiving at least one of the backoff parameters calculated based on the number of terminals, and a packet transmission step of setting a backoff time based on the backoff parameter and transmitting a packet based on the backoff time. A retransmission method can be provided.

In another aspect, the present embodiments provide an access point that controls packet retransmission of a terminal, a backlogged terminal that wants to transmit packets based on an idle period in which packets are not received at specific times. A control unit that estimates the number and calculates a backoff parameter that maximizes throughput based on the estimated number of backlogged terminals, and at least one of the number of backlogged terminals and the backoff parameter is assigned to the backlogged terminal. An access point including a transmission unit that transmits data may be provided.

According to the present embodiments, a method and apparatus for controlling packet retransmission that estimates network load and adaptively adjusts the backoff time for packet transmission can be provided.

Figure 1 is a diagram showing the overall configuration of a wireless network to which this embodiment can be applied.
Figure 2 is a diagram for explaining an operation of an access point controlling packet retransmission of a terminal according to this embodiment.
Figure 3 is a diagram for explaining an operation in which a terminal performs packet retransmission according to this embodiment.
Figure 4 is a diagram for explaining the configuration of an access point according to this embodiment.
Figure 5 is a diagram for explaining the operation of estimating the number of backlogged terminals according to this embodiment.
Figure 6 is a diagram for explaining an algorithm for estimating the number of backlogged terminals according to this embodiment.
Figure 7 is a diagram for explaining performance according to this embodiment.

Hereinafter, some embodiments of the present disclosure will be described in detail with reference to illustrative drawings. In adding reference numerals to components in each drawing, identical components may have the same reference numerals as much as possible even if they are shown in different drawings. Additionally, in describing the present embodiments, if it is determined that a detailed description of a related known configuration or function may obscure the gist of the present technical idea, the detailed description may be omitted. When “comprises,” “has,” “consists of,” etc. mentioned in the specification are used, other parts may be added unless “only” is used. When a component is expressed in the singular, it can also include the plural, unless specifically stated otherwise.

Additionally, in describing the components of the present disclosure, terms such as first, second, A, B, (a), and (b) may be used. These terms are only used to distinguish the component from other components, and the nature, sequence, order, or number of the components are not limited by the term.

In the description of the positional relationship of components, when two or more components are described as being “connected,” “coupled,” or “connected,” the two or more components are directly “connected,” “coupled,” or “connected.” However, it should be understood that two or more components and other components may be further “interposed” and “connected,” “combined,” or “connected.” Here, other components may be included in one or more of two or more components that are “connected,” “coupled,” or “connected” to each other.

In the explanation of temporal flow relationships related to components, operation methods, production methods, etc., for example, temporal precedence relationships such as “after”, “after”, “after”, “before”, etc. Or, when a sequential relationship is described, non-continuous cases may be included unless “immediately” or “directly” is used.

On the other hand, when a numerical value or corresponding information (e.g. level, etc.) for a component is mentioned, even if there is no separate explicit description, the numerical value or corresponding information is related to various factors (e.g. process factors, internal or external shocks, It can be interpreted as including the error range that may occur due to noise, etc.).

Figure 1 is a diagram showing the overall configuration of a wireless network to which this embodiment can be applied.

Referring to Figure 1, the overall configuration of a wireless network using the Pure ALOHA protocol can be described. As an example, a wireless network using the Pure ALOHA protocol may first have an access point (AP) 110. And, the access point 110 can be connected to a plurality of terminals. And, each terminal 120, 130, 140, and 150 can transmit a packet to the access point 110. At this time, if a plurality of terminals attempt to transmit packets to the access point 110 at the same time, a collision may occur as the frame of a packet transmitted from one terminal overlaps with the frame of a packet transmitted from another terminal. If a collision occurs while each terminal 120, 130, 140, and 150 transmits a packet to the access point 110, the packet can be retransmitted using a Delayed First Transmission (DFT) method. When using the DFT method, a backlogged terminal, that is, a terminal that has packets to retransmit, may attempt to retransmit packets at random backoff time intervals when it recognizes a collision or transmission failure. For example, each terminal 120, 130, 140, and 150 receives a backoff parameter transmitted by the access point 110, and receives a backoff parameter from an exponential distribution function whose average is the reciprocal of the backoff parameter. Off time can be set. The exponential distribution can be used to represent a continuous probability distribution for the waiting time for an event to occur, that is, a probability distribution for the time elapsed between events. Additionally, the backoff parameter transmitted by the access point 110 to the terminal may be updated at a specific point in time. In particular, it can be updated based on the status of the channel through which communication occurs between the terminal and the access point 110 and the estimated number of backlogged terminals. The access point 110 according to this embodiment calculates a backoff parameter for transmitting to the terminal based on an estimate of the number of backlogged terminals, thereby providing detailed information on how the access point 110 controls packet retransmission of the terminal. The contents will be described later with reference to FIGS. 2 to 7.

Figure 2 is a diagram for explaining an operation of an access point controlling packet retransmission of a terminal according to this embodiment.

Referring to FIG. 2, the method by which an access point (AP) controls packet retransmission of a terminal according to this embodiment includes a terminal number estimation step of estimating the number of backlogged terminals that want to transmit packets. may include (S210). For example, an access point that controls packet retransmission of terminals may estimate the number of backlogged terminals that want to transmit packets based on an idle period in which packets are not received at a specific point in time. At this time, the specific point in time may be the point at which the success or collision period ends in a section that includes one idle period and a success or collision period for the transmission of packets that occur after the idle period. For example, an access point that controls packet retransmission of a terminal defines a period from when the channel through which communication occurs with the terminal enters an idle period until a specific terminal succeeds in transmitting a packet or a collision occurs between terminals. It can be set to a section of . Here, the point at which one section ends can be defined as an epoch. In other words, the access point determines the success or end of the collision period for the transmission of packets generated in each section over time as a specific point in time. You can set it and estimate the number of backlogged terminals at a specific point in time.

As another example, an access point that controls packet retransmission of a terminal can estimate the average number of backlogged terminals according to an idle period using Bayesian estimation. And, the access point can estimate the number of backlogged terminals based on the estimated average number of backlogged terminals. For example, an access point that controls packet retransmission of a terminal may perform Bayesian estimation by assuming that the number of backlogged terminals is a Poisson distribution with mean α as the prior distribution. The access point can estimate the average number of backlogged terminals by calculating a conditional probability distribution in which the number of backlogged terminals is m when the idle period during which packets are not received is t. Additionally, the access point can estimate and update the number of backlogged terminals at a specific point in time using the estimated average number of backlogged terminals. Here, the estimated number of backlogged terminals (α) can be distinguished from the number (m) of backlogged terminals in the actual system. For example, the access point that controls the packet retransmission of the terminal determines the backlog based on the number of new backlogged terminals and the average number of backlogged terminals at a specific point in time, depending on whether the transmission of the packet is successful or collisions. The number of terminals can be estimated. If the transmission of the packet is successful, the access point can estimate the number of backlogged terminals by adding the number of new backlogged terminals to the average number of backlogged terminals and excluding one terminal that succeeded in transmitting the packet. . On the other hand, if the transmission of a packet is a collision, the access point can estimate the number of backlogged terminals by multiplying the number of new backlogged terminals by the current collision period and adding it to the average number of backlogged terminals. . Details regarding the method for estimating the number of backlogged terminals will be described later with reference to FIGS. 5 and 6.

The method by which the access point controls packet retransmission of the terminal according to this embodiment may include a parameter calculation step of calculating a backoff parameter transmitted to the terminal (S210). As an example, an access point that controls packet retransmission of a terminal may calculate a backoff parameter that maximizes throughput based on the estimated number of backlogged terminals. For example, the access point can multiply the number of backlogged terminals estimated at a specific point in time by N and calculate the reciprocal of the number as the backoff parameter. Here, N may be a real number greater than or equal to 0. For a specific example, the access point can calculate the backoff parameter by doubling the number of backlogged terminals estimated at a specific point in time and taking the reciprocal of the number. However, 2 is an example of a real number greater than or equal to 0 and is not limited thereto.

The method by which the access point controls packet retransmission of the terminal according to this embodiment may include a transmission step of transmitting a backoff parameter to the backlogged terminal (S220). For example, the access point may transmit at least one of the number of backlogged terminals and a backoff parameter to the backlogged terminal. The transmitted backoff parameter can be used to set a backoff time corresponding to the interval at which the terminal retransmits packets in real time.

Figure 3 is a diagram for explaining an operation in which a terminal performs packet retransmission according to this embodiment.

Referring to FIG. 3, the method for a terminal to perform packet retransmission according to this embodiment may include a reception step of receiving at least one of the number of backlogged terminals and a backoff parameter (S310). As an example, a terminal performing packet retransmission is a backlogged terminal calculated based on the number of backlogged terminals and the number of backlogged terminals estimated based on an idle period in which packets are not received at a specific point in time. At least one of the off parameters can be received. Here, the specific point in time may be the point at which the success or collision period ends in a section that includes one idle period and a success or collision period for the transmission of packets that occur after the idle period. For example, a terminal performing packet retransmission may receive the estimated number of backlogged terminals at the end of a collision period or successful transmission of packets generated in each section over time. Specifically, the number of backlogged terminals received is estimated by estimating the average number of backlogged terminals according to the idle period using Bayesian Estimation, and estimated based on the estimated average number of backlogged terminals. You can. Additionally, the number of backlogged terminals can be estimated based on the number of new backlogged terminals and the average number of backlogged terminals at each specific time depending on whether packet transmission is successful or collisions occur. For another example, a terminal performing packet retransmission may receive a backoff parameter calculated at each termination point. Specifically, the received backoff parameter can be calculated as a value obtained by multiplying the number of backlogged terminals estimated at each specific point in time by N and taking the reciprocal thereof.

The method in which the terminal performs packet retransmission according to this embodiment may include a packet transmission step of transmitting a packet based on the backoff time (S320). As an example, a terminal performing packet retransmission may set a backoff time based on a received backoff parameter and transmit packets based on the set backoff time. For example, a terminal performing packet retransmission can set the backoff time from an exponential distribution function that averages the reciprocal of the received backoff parameter. Additionally, the terminal performing packet retransmission can maximize throughput by retransmitting packets at intervals corresponding to the backoff time set in real time.

Figure 4 is a diagram for explaining the configuration of an access point according to this embodiment.

Referring to FIG. 4, the access point 110, which controls packet retransmission of the terminal according to this embodiment, is a backlogged device that wants to transmit packets based on an idle period in which packets are not received at specific times. ) A control unit 410 that estimates the number of terminals and calculates a backoff parameter that maximizes throughput based on the estimated number of backlogged terminals and at least one of the number of backlogged terminals and a backoff parameter It may include a transmission unit 420 that transmits to the backlogged terminal.

As an example, the control unit 410 may estimate the number of backlogged terminals that wish to transmit packets. For example, the control unit 410 may estimate the number of backlogged terminals that want to transmit packets based on an idle period in which packets are not received at a specific point in time. Specifically, the control unit 410 estimates the number of backlogged terminals at each point when the success or collision period ends in a section that includes one idle period and a success or conflict period for the transmission of packets that occur after the idle period. You can.

Additionally, for example, the control unit 410 estimates the average number of backlogged terminals according to the idle period using Bayesian estimation, and determines the number of backlogged terminals based on the estimated average number of backlogged terminals. It can be estimated. Specifically, the control unit 410 estimates the number of backlogged terminals based on the number of new backlogged terminals and the average number of backlogged terminals at a specific point in time depending on whether packet transmission is successful or collides. You can.

As another example, the control unit 410 may calculate a backoff parameter that maximizes throughput based on the estimated number of backlogged terminals. Specifically, the control unit 410 may multiply the number of backlogged terminals estimated at a specific point in time by N and calculate the reciprocal value as the backoff parameter. Here, N may be a real number greater than or equal to 0.

As an example, the transmitter 420 may transmit at least one of the number of backlogged terminals and a backoff parameter to the backlogged terminal. For example, the transmitter 420 may transmit at least one of the number of backlogged terminals and a backoff parameter to the backlogged terminal. The transmitted backoff parameter can be used to set a backoff time corresponding to the interval at which the terminal retransmits packets in real time.

In addition to this, the control unit 410 performs an operation of estimating the number of backlogged terminals based on the idle period required to perform the present disclosure described above and calculating a backoff parameter based on the number of backlogged terminals. The overall operation of the access point 110 can be controlled according to operation control.

Additionally, the transmission unit 420 may be used to transmit signals, messages, or data necessary to perform the present disclosure described above.

Hereinafter, a specific operation in which an access point estimates the number of backlogged terminals and calculates a backoff parameter in order to control packet retransmission of terminals will be described in more detail with reference to the drawings. Additionally, an access point (AP) may be a base station, and a terminal may be a device or user that wants to transmit packets. However, this is an example for explanation only, and the access point (AP) is not limited to this as long as it is a device that can apply a random access method and is capable of wireless communication.

In a wireless communication system, an access point (AP) is located in the center of the cell, and time can be divided into individual slots corresponding to one packet transmission. Packets transmitted from each terminal to the access point may be received randomly. Therefore, the backlog size, which is the number of active users in the system, may change over time because packets from the terminal are received randomly. Specific details will be described later with reference to FIGS. 5 and 6. However, in this specification, it is assumed that the access point can provide feedback information. The feedback information may be information about the start and end of the success period, idle period, and conflict period provided at the end of each slot.

Figure 5 is a diagram for explaining the operation of estimating the number of backlogged terminals according to this embodiment.

Referring to FIG. 5, a control method for calculating a backoff parameter that maximizes throughput based on the number of backlogged terminals in an ALOHA system without slots according to this embodiment can be described. This may be referred to as an online adaptive backoff algorithm. For example, a plurality of terminals may be randomly scattered under the service area of one access point (AP). Each terminal can generate packets according to a Poisson process with an average speed λ and hold only one packet. Here, the length of the packet may be constant. Additionally, a terminal that has packets to transmit may be referred to as a backlogged terminal. For a specific example, in an ALOHA system without slots, a backlogged terminal can first generate a random variable according to an exponential distribution with an average of 1/β (seconds). τ _i may be a random variable drawn by device i. That is, if the terminal fails to (re)transmit at time t, the terminal can transmit the packet to the access point (AP) at time t+τ _i . For another example, a backlogged terminal may select a random variable from a uniform distribution for the [0, U] interval. At this time, while the terminal considers time division duplexing (TDD) to switch from transmission mode to reception mode immediately after transmitting the packet, the access point (AP) receives the reception packet and then goes from reception to transmission through the downlink. It can work as When random access (RA) fails, the terminal can generate a new random variable by repeating ERB (exponential random backoff) or URB (uniform random backoff) until random access succeeds.

In addition, according to this embodiment, throughput and random access (RA) delay distribution in the slotless ALOHA system can be explained. 5 may be a timing diagram of a slotless ALOHA system. Here, t' _k and t _k for t _k ∈R may be the start and end time epochs of events such as success or crash, respectively. I and C may be the length of the idle and crash periods respectively. Additionally, X _tk may be the number of backlogged terminals at time epoch t _k . Over time, the number of backlogged terminals X _tk may change as shown in Equation 1.

Here, II(S) can be set to 1 if transmission is successful, and 0 otherwise. may be a new backlogged terminal that newly joined during t _k -t _k-1 .

As an example, to estimate the number of backlogged terminals, an approximation model can be created as a generalized M/M/1 queuing system with a population size of N. In the approximation model, when there are i backlogged terminals, the packet arrival rate (average input rate) to the system can be expressed as Equation 2.

On the other hand, two conditions can be met for one packet to be transmitted successfully. The first condition may be that previous transmissions do not overlap with the tagged packet transmission. For example, when terminal i generates a random variable according to an exponential distribution with the same mean 1/β (seconds) for all, the probability density function (PDF) of the first packet transmission time has a mean of 1. / (iβ), that is, it may be iβe ^-iβt . Then, the first condition can occur with probability e ^-iβ . The second condition may be that i-1 backlogged terminals do not (re)transmit during the transmission time of the first packet. For example, when retransmissions of i-1 remaining backlogged terminals are generated by a Poisson process with mean (i-1)β, retransmissions can occur with probability e ^-(i-1)β. . The (average) output speed of a system with i (X _tk = i) number of backlogged terminals is μ _i , and can be expressed as Equation 3.

Additionally, the steady-state probability of having i backlogged terminals in this system may be π _i . The balance equation in each state can be expressed as Equation 4.

Equation 4 can be expressed as Equation 5 for k={1,2,...,N}.

here, If , π _o can be expressed as Equation 6.

If π _i is calculated, the system throughput τ can be expressed as Equation 7.

As another example, in order to obtain a random access (RA) delay distribution, the Laplace-Stieltjes transform (LST) of an exponential random variable with a mean of 1/β can be considered. This can be expressed as Equation 8.

When P _s is the success probability of random access, it can be expressed as Equation 9.

For example, as ERB (exponential random backoff) is repeated with probability 1-p _s whenever random access fails, the LST of the random access delay distribution can be expressed as Equation 10.

By connecting Equation 8 and Equation 10, Equation 11 can be obtained.

Here, by taking the inverse LST of Equation 11, the cumulative distribution function (CDF) of the random access delay distribution can be calculated as Equation 12.

For another example, in the case of uniform random backoff (URB), the random access delay at the kth retransmission epoch may be the sum of continuous random variables k extracted from the [0, U] interval. The LST of the uniform random variable for the [0, U] interval can be expressed as Equation 13.

Here, by taking the inverse LST of Equation 13, the cumulative distribution function of the random access delay distribution can be calculated. In the unit interval [0, 1], the CDF and PDF for the sum of n Independent and Identically Distributed (i.i.d.) may be the Irwin-Hall distribution. CDF and PDF can be expressed as Equation 14 and Equation 15, respectively.

Here, s _i (t) can be expressed as Equation 16 as a unit step function.

To calculate the random access delay distribution for uniform random backoff (URB), each of X and Y may be a continuous uniform random variable in the unit interval and [0, U] interval. And, the CDF for the sum of Y can be obtained by linearly transforming one random variable into another random variable. That is, Pr[Y ≤ y] Pr[UX ≤ y] Pr[X ≤ y/U]. Therefore, the CDF and PDF of the random access delay distribution can be expressed as Equation 17 and Equation 18, respectively, when applied to URB.

Here, the average of the exponential random variable and the uniform random variable may be 1/μ and U/2, respectively. Therefore, in Equation 17 and Equation 18, Equation 9, where P _s is μ2/U, can be used.

Additionally, in the slotless ALOHA system according to this embodiment, the operating region is divided into an unsaturated stable region, a bistable region, and a saturated region, and the unsaturated stable region may be an ideal operating region. Here, the operating area can be divided by the new packet arrival rate λ, the retransmission rate μ, and the number of terminals N. Catastrophe theory can be used to characterize the operating region. For example, when F is a potential function of the system, F: R ^k Х R ⁿ → R, and each k and n may be a control variable and a system state variable. Specifically, when k is 2 and n is 1, the system state is x ∈ [0, 1], and the number of backlogged terminals can be normalized by the total number of terminals N. Therefore, Nx may be the number of backlogged terminals. A random access system can exist if F(x) holds for x ∈ [0, 1] as shown in Equation 19.

Here, when k≥3, It can be. If a random access system exists, the catastrophe manifold (Θ) can be a three-dimensional surface defined by Θ = {(x,λ,β)|F(x)= 0}. Additionally, Θ _B is a folding line composed of points, which may be a line along which the surface of the manifold is folded. Θ _B is It can be defined as:

Additionally, Θ _B can be characterized into three parts as Equation 20, Equation 21, and Equation 21

The bifurcation sets Θ+ and Θ- can be obtained by projecting the three-dimensional manifolds (tangents) Θ+ and Θ-, respectively, into the control space (λ, β). The potential function can be expressed as Equation 23.

Here, E[S] is the average outflow rate and can be expressed as Equation 24.

Here, G is the traffic load of m backlogged terminals and may be G=βm. As before, if x is the normalized system state and x = m/N, then G = βxN. Additionally, in Equation 23, E[A] can be expressed as Equation 25.

Therefore, Equation 23 can also be expressed as Equation 26.

For example, λ in Equation 20 and Equation 21 can be expressed as Equation 27.

λ in Equation 20 and Equation 21 is Since it must be satisfied, it can be expressed as Equation 28.

In other words, if we rewrite equation 28 for λ, we can get equation 27.

For another example, when x± is the normalized state corresponding to Θ+ and Θ- in Equation 20 and Equation 21, respectively, x± can be expressed as in Equation 29.

Here, G± can be expressed as Equation 30.

By substituting equation 27 into equation 26, equation 31 can be obtained.

Here, if F(G) = 0, Equation 30 can be obtained. However, in Equation 30, G± may be a real number for β > 2/N.

For another example, Θ ₀ in Equation 22 can be expressed as a cusp point as in Equation 32.

In equation 22 Then, equation 33 can be obtained.

Therefore, x = 1/(βN). Additionally, the vertex may be the point when x ₊ = x _- or G ₊ = G _- .

Additionally, according to this embodiment, the backoff rate can be controlled to remove or avoid pairing in an ALOHA system without a slot. For example, bistability may not appear if throughput is maximized by estimating the number of backlogged terminals over time. Throughput E[S] is You can maximize it using . This can be expressed as Equation 34.

Here, xN is a value that changes with time and may be X _tk . Applying Equation 34, E[S] = e ^-2 can be obtained, which can mean the maximum throughput of the pure-ALOHA system. Additionally, by substituting Equation 34 into Equation 26, it can be expressed as Equation 35.

Equation 35 can be a linear function of x with F(0) = 0.5e ^-1 -Nλ and F(1) = 0.5e ^-1 . If F(0) < 0, we can have a single solution.

Additionally, the higher-order derivative of F(x) for k ≥ 3 can be expressed as Equation 36.

Here, c _k is k 3, 4, . . . And when c ₂ = 1, it can be expressed as c _k = 2c _k-1 + 2 ^k-3 .

Figure 6 is a diagram for explaining an algorithm for estimating the number of backlogged terminals according to this embodiment.

Referring to FIG. 6, a method in which an access point (AP) calculates a backoff parameter over time and controls packet retransmission in real time according to this embodiment can be explained. Here, the backoff parameter (β) is a value calculated based on the number (i) of backlogged terminals and may mean the backoff speed. As an example, if the access point (AP) transmits with β = 1/(2i) at the end of the success or collision period, a backlogged terminal that has not yet scheduled a retransmission or needs to reschedule will receive an average of 1 just transmitted. The backoff time (backoff interval) can be calculated from the exponential random variable of /β. In other words, the method by which an access point (AP) controls packet retransmission of a terminal can estimate the number of backlogged terminals ₍ . That is, it may be f ^-1 (I). However, X _tk =i may not be accurate. Therefore, the average number of backlogged terminals E[X _tk ] can be estimated so that the access point (AP) can transmit β = 1/(2E[X _tk ]).

For example, an idle period may begin at the end of a success or conflict period. In particular, the time when the access point (AP) transmits the backoff parameter (β) may be when the success or collision period ends. Specifically, the time at which the success or conflict period ends may be a time corresponding to t _k-1 , t _k , or t _k+1 in FIG. 5. On the other hand, the idle period can end at the start of a success or conflict period. Specifically, the time at which the idle period ends may be a time corresponding to t'k _-1 , _t'k , or t'k ₊₁ in FIG. 5. Accordingly, the idle period may be the period from the end of a previous success or conflict period to the beginning of the current success or conflict period. That is, the idle period can be calculated from the third row of the algorithm disclosed in Figure 6.

For another example, when the backoff time of terminal j is τ _j , the first retransmission time epoch performed by i backlogged terminals may be the minimum value of the i index random variable. The idle period (I) can be expressed as Equation 37.

Here, when the number of backlogged terminals is X, the complementary conditional cumulative distribution function (CDF) of the idle period (I) can be expressed as Equation 38.

Here, the probability density function (PDF) of the idle period (I) can be obtained as shown in Equation 39.

This may be an exponential distribution with mean 1/(iβ). Additionally, by observing the idle period (I), E[X|I = t] can be obtained by Equation 40.

Here, f _I (t) may be an unconditional probability density function.

As another example, it can be assumed that the number of backlogged terminals is a Poisson process with average α. At this time, the number of backlogged terminals can be expressed as Equation 41.

Accordingly, when there are m backlogged terminals in the system, the probability that the idle period is t can be expressed as Equation 42.

Additionally, in Equation 40, f _I (t) can be expressed as Equation 43.

Here, by substituting Equation 42, Equation 44 can be obtained.

Equation 45 can be finally obtained from Equation 43 and Equation 44.

Therefore, when a long idle period is observed, it can be seen that the average number of backlogged terminals α decreases exponentially. However, the number 1 added to Equation 45 may mean that there is one or more backlogged terminals at the end of the idle period.

For example, the number of backlogged terminals can be estimated from lines 6 and 8 of the algorithm disclosed in Figure 6. That is, the number of backlogged terminals can be estimated depending on whether packet transmission is successful or collisions occur. Specifically, if the packet transmission is successful, the number of backlogged terminals can be subtracted by 1 to exclude one terminal that successfully transmitted from Equation 45. Then, the number of new backlogged terminals can be multiplied by the packet transmission time in Equation 45. Here, the packet transmission time may be 1 by normalization. On the other hand, if the transmission of the packet is a collision, instead of subtracting 1 from Equation 45, the number of new backlogged terminals proportional to the length of the current collision period C can be assumed and added.

Here, the number of new backlogged terminals can be estimated from row 4 of the algorithm disclosed in Figure 6. Specifically, the number of new backlogged terminals can be estimated by applying ±(S)=1 if packet transmission is successful. On the other hand, if packet transmission is a collision, it can be estimated by applying ±(S)=0.

For example, an access point (AP) may calculate a backoff parameter based on the estimated number of backlogged terminals and transmit it to the backlogged terminal. Here, the transmission time is when the success or conflict period ends and may be a specific time corresponding to t _k in FIG. 5.

Figure 7 is a diagram for explaining performance according to this embodiment.

Referring to FIG. 7, the performance of the method for controlling packet retransmission according to this embodiment can be explained. As an example, the delay performance diagram 710 may represent an average compared to three different algorithms when N=100. For example, it can be seen that the method for controlling packet retransmission according to this embodiment is very close to the average of the EBI algorithm in terms of the average random access delay. Specifically, EBI can be controlled using size information X _tk of the backlogged terminal. In other words, EBI can control packet retransmission by setting the backoff interval to 1/(2X _tk ). In addition, PF does not consider estimation of the arrival of a new packet, and has the characteristic of not considering a single successfully transmitted packet even when successful. In addition, BEB is suitable for low traffic loads corresponding to Nλ < 0.18, but has the worst characteristics in terms of delay violation. Therefore, if the method for controlling packet retransmission, the PF-based algorithm, and the EBI algorithm according to this embodiment are used, a sharp increase in D may not occur as the traffic load increases. In other words, it can be expected that bistability may be eliminated as the system transitions from an unsaturated stable state to a saturated state.

Additionally, as an example, the diagram 720 regarding estimation performance may represent X _tk estimated over time when N = 100. For example, it can be confirmed that the method for controlling packet retransmission according to this embodiment can estimate the number of backlogged terminals based on the arrival rate over time. Specifically, the arrival of new packets may vary over time. The packet arrival rate λ for each terminal increases by 0.0005 every 10 ⁴ seconds, and the traffic load may be 0.05. Additionally, when the packet arrival rate λ reaches 0.003, it can again decrease by 0.0005 every 10 ⁴ seconds. Here, the solid line may represent the actual number of backlogged terminals, and the dotted line may represent the estimated number of actual backlogged terminals.

As described above, according to the present disclosure, a method and apparatus for controlling packet retransmission can be provided. In particular, it is possible to provide a method and device for controlling packet retransmission that adaptively adjusts the backoff time for packet transmission by estimating the network load. Specifically, a packet that adaptively adjusts the backoff time for packet retransmission by calculating the backoff parameter that maximizes throughput by estimating the number of backlogged terminals to which the access point wants to transmit packets. A method and device for controlling retransmission can be provided.

The above-described embodiments can be implemented through various means. For example, the present embodiments may be implemented by hardware, firmware, software, or a combination thereof.

In the case of hardware implementation, the method according to the present embodiments uses one or more ASICs (Application Specific Integrated Circuits), DSPs (Digital Signal Processors), DSPDs (Digital Signal Processing Devices), PLDs (Programmable Logic Devices), and FPGAs. (Field Programmable Gate Arrays), processors, controllers, microcontrollers, or microprocessors.

In the case of implementation by firmware or software, the method according to the present embodiments may be implemented in the form of a device, procedure, or function that performs the functions or operations described above. Software code can be stored in a memory unit and run by a processor. The memory unit is located inside or outside the processor and can exchange data with the processor through various known means.

Additionally, terms such as "system," "processor," "controller," "component," "module," "interface," "model," or "unit" described above generally refer to computer-related entities hardware, hardware and software. It may refer to a combination of, software, or running software. By way of example, but not limited to, the foregoing components may be a process, processor, controller, control processor, object, thread of execution, program, and/or computer run by a processor. For example, both an application running on a controller or processor and the controller or processor can be a component. One or more components may reside within a process and/or thread of execution, and the components may be located on a single device (e.g., system, computing device, etc.) or distributed across two or more devices.

The above description is merely an illustrative explanation of the technical idea of the present disclosure, and those skilled in the art will be able to make various modifications and variations without departing from the essential characteristics of the present disclosure. In addition, the present embodiments are not intended to limit the technical idea of the present disclosure, but rather to explain it, so the scope of the present technical idea is not limited by these embodiments. The scope of protection of this disclosure should be interpreted in accordance with the claims below, and all technical ideas within the equivalent scope should be interpreted as being included in the scope of rights of this disclosure.

Claims (14)

In a method for an access point (AP) to control packet retransmission of a terminal,
A terminal number estimation step of estimating the number of backlogged terminals that want to transmit packets based on an idle period in which packets are not received at a specific point in time;
A parameter calculation step of calculating a backoff parameter that maximizes throughput based on the estimated number of backlogged terminals; and
A transmission step of transmitting at least one of the number of backlogged terminals and the backoff parameter to the backlogged terminal,
The step of estimating the number of terminals is,
Based on the number of new backlogged terminals at the specific point in time depending on success or collision in transmission of the packet and the average number of backlogged terminals estimated according to the idle period using Bayesian Estimation. to estimate the number of backlogged terminals,
If transmission of the packet is a collision, a packet retransmission method for estimating the number of the backlogged terminals by adding the number of the new backlogged terminals multiplied by the current collision period to the average number of backlogged terminals. According to claim 1,
At this specific point in time,
Packet retransmission, characterized in that the point at which the success or collision period ends in a section including one idle period and a success or collision period for transmission of the packet that occurs after the idle period method. delete delete According to claim 1,
The step of estimating the number of terminals is,
If transmission of the packet is successful, the number of new backlogged terminals is added to the average number of backlogged terminals and the number of backlogged terminals is estimated by excluding one terminal that succeeded in transmitting the packet. A packet retransmission method characterized in that. delete According to claim 1,
The parameter calculation step is,
A packet retransmission method, wherein the backoff parameter is calculated by multiplying the number of backlogged terminals estimated at the specific time by N and taking the reciprocal thereof, where N is a real number of 0 or more. In a method for a terminal to perform packet retransmission,
Reception that receives at least one of the number of backlogged terminals estimated based on an idle period in which packets are not received at a specific point in time and a backoff parameter calculated based on the number of backlogged terminals. step; and
A packet transmission step of setting a backoff time based on the backoff parameter and transmitting a packet based on the backoff time,
The number of backlogged terminals is,
Based on the number of new backlogged terminals at the specific point in time depending on success or collision in transmission of the packet and the average number of backlogged terminals estimated according to the idle period using Bayesian Estimation. It is estimated that,
If transmission of the packet is a collision, a packet retransmission method is estimated by adding the number of new backlogged terminals multiplied by the current collision period to the average number of backlogged terminals. According to claim 8,
At this specific point in time,
Packet retransmission, characterized in that the point at which the success or collision period ends in a section including one idle period and a success or collision period for transmission of the packet that occurs after the idle period method. delete delete According to claim 8,
The backoff parameter is,
A packet retransmission method, characterized in that the number of backlogged terminals estimated at the specific point in time is multiplied by N and the reciprocal thereof is taken, and N is a real number greater than or equal to 0. According to claim 8,
The packet transmission step is,
A packet retransmission method, characterized in that the backoff time is set from an exponential distribution function that averages the reciprocal of the backoff parameter. In the access point (AP) that controls packet retransmission of the terminal,
At a specific point in time, the number of backlogged terminals that want to transmit packets is estimated based on the idle period in which packets are not received, and the throughput is calculated based on the estimated number of backlogged terminals. a control unit that calculates a backoff parameter that maximizes; and
Including a transmission unit that transmits at least one of the number of backlogged terminals and the backoff parameter to the backlogged terminal,
The control unit,
Based on the number of new backlogged terminals at the specific point in time depending on success or collision in transmission of the packet and the average number of backlogged terminals estimated according to the idle period using Bayesian Estimation. to estimate the number of backlogged terminals,
If transmission of the packet is a collision, the access point estimates the number of the backlogged terminals by adding the number of the new backlogged terminals multiplied by the current collision period to the average number of backlogged terminals.

Images