CN102036255A

CN102036255A - Packet sending method based on prediction in communication channel

Info

Publication number: CN102036255A
Application number: CN2010105711938A
Authority: CN
Inventors: 杨双懋; 郭伟; 余敬东; 刘军; 苏俭; 刘伟
Original assignee: University of Electronic Science and Technology of China
Current assignee: University of Electronic Science and Technology of China
Priority date: 2010-12-02
Filing date: 2010-12-02
Publication date: 2011-04-27

Abstract

The invention provides a packet sending method capable of predicting the arrival time of user business packet accurately so as to effectively resolve the packet collision in a communication channel. The packet sending method is as follows: in order to resolve the collision better in the packet sending process, establishing a mathematical model described by time for an arrival time sequence of the user business packet by user business modeling, facilitating the prediction on the arrival time sequence of the user business packet in future, and when a plurality of packets need to be sent and generate collision, and the packets can be decomposed according to the predicted result. The key points in the invention are as follows: an assignment interval for packet transmission in the current time slot is determined by predicting the arrival time of next user business packet, and decides the packet which is sent in the current time slot and arrives in the time duration of the assignment interval. In the invention, the adopted fractal autoregressive integrated moving average (FARIMA) model can be well matched with the current wireless network environment, and by combination with the whole packet transmission method, the packet time delay can be effectively reduced and the network throughput rate can be improved.

Description

Prediction-based packet transmission method in communication channel

Technical Field

The invention belongs to the field of wireless network technology, such as wireless sensor network, wireless self-organizing network, wireless local area network, satellite network and the like, and particularly relates to a multiple access technology of wireless shared channels.

Background

A wireless channel is a shared transmission medium. Therefore, a collision will inevitably occur when a plurality of users communicate on the channel at the same time, thereby reducing the throughput of the system. How to avoid collision of data on the broadcast channel and improve the utilization of the link is a core problem of multiple access. Currently, the multiple access algorithm mainly includes: fixed allocation, on-demand allocation, and random contention 3 types. Due to the distributed nature and the temporary nature of the network and the burstiness of the traffic, neither the fixed allocation multiple access protocol nor the demand allocation multiple access protocol can effectively function. The random contention multiple access algorithm can effectively occupy channel resources under certain conditions, and the technology of reducing the switching delay is widely applied. The systems adopting the random contention multiple access algorithm have a common characteristic that users in the systems randomly occupy channel resources and transmit information packets, and when the transmitted information packets collide, collision resolution is required. The system has the advantages of no need of centralized control, easy increase and decrease of terminal stations, simple operation, small transmission delay and the like. In light load situations, there is less probability of collisions of packets of information in the system, and each station can efficiently utilize the channel as needed. However, with the load increasing, collisions will increase, and since the collided information packets need to be retransmitted, the delay will increase and the throughput will decrease, so that the adoption of a reasonable collision resolution algorithm becomes a key problem for improving the performance of the random contention multiple access system.

The basic idea of conflict resolution is: if the packet in the system is collided, the newly arrived user service packet is made to wait outside the system, and after the successful transmission of the packets participating in collision is finished, the new packet is made to be transmitted. At present, the classical conflict resolution algorithms include a tree conflict resolution Algorithm and an FCFS (First-com First-service Splitting Algorithm) conflict resolution Algorithm.

The existing conflict resolution method comprises the following steps:

1. and (3) tree conflict decomposition: the binary tree decomposition algorithm is mainly used, the groups participating in collision in the binary tree decomposition algorithm are randomly selected to enter a left set or a right set with a certain probability, the priority of the left set is higher than that of the right set, and the decomposition of the right set can be entered only after the left set is successfully decomposed. See J I patent Algorithms for packet slots Channels [ J ], IEEE Transactions on Information Theory, September1979, volume.25, No.5, page(s) (505) 515. tree collision resolution treats collision messages, based on a random manner, and when the number of packets colliding is large, the slot utilization of the system will decrease.

2. FCFS conflict resolution: the packets which are collided are frozen in the collision window, and then the collision packets are decomposed in sequence according to the generation time, so that the packets which arrive first are successfully transmitted first. See documents D Bertsekas, R gallager. datanets [ M ], 2nd Edition, precision-Hall, USA, 1992, page(s): scheduling according to the arrival time of the packet, the FCFS conflict resolution algorithm can reduce idle time slots, but when there are packets with relatively close intervals in the collision packets, resolution with time conditions will need to be performed for multiple times, and especially when the user traffic has self-similarity, the time burst of the traffic is very strong, and the efficiency of the FCFS will be significantly reduced.

3. HSA (Hybrid Splitting Algorithm): the advantages of the tree decomposition algorithm and the FCFS conflict decomposition algorithm are inherited, the generation time of the collision grouping is considered, the generated grouping is served first, and meanwhile when the grouping with the relatively close generation intervals exists in the system, the tree decomposition algorithm is adopted, the whole decomposition process is not limited to the generation time of the grouping any more, and therefore the total time slot number required by decomposition is reduced. See documents Min Sheng, Jiandong land fire, hybrid splitting algorithm for wireless MAC, IEEE Communications Letters, vol.9, Issue 5, May 2005 page(s): 468-470, the key of HSA algorithm is to calculate the optimal time point for switching from tree decomposition algorithm to FCFS conflict decomposition algorithm, and the obtaining of the optimal time point requires that the user service model is assumed to be poisson process, so when the real user service model does not meet the assumption, the optimal time point cannot be obtained, and the performance of the algorithm will be consistent with the tree decomposition algorithm.

The above conflict resolution algorithm has the following disadvantages: the tree conflict decomposition is purely based on a random decomposition mode, and when a large number of groups collide, the performance of the algorithm is obviously reduced; the FCFS decomposes the collision message too much depending on the time condition, and when the time burst of the user service is very strong, the algorithm efficiency is reduced; HSA is too limited, requiring an assumption that the user service model is a poisson process, and its application scope is limited when real user services do not meet this assumption.

Disclosure of Invention

The technical problem to be solved by the invention is to provide a packet transmission method which can accurately predict the arrival time of user service packets so as to effectively decompose packet collisions in a communication channel.

The technical scheme adopted by the invention for solving the technical problems is that the packet sending method based on prediction in the communication channel comprises the following steps:

a packet transmission step based on prediction:

the A1 system has sent out the user traffic packets that arrived before time T (k);

the a2 system builds a FARIMA (autoregressive score integration moving average) model for the arriving time series of user traffic packets that have been sent out before time t (k);

a3 predicting arrival time of next user service packet by the FARIMA model

The A4 system is transmitted in [ T (k), T (k) + a (k) in the current time slot k]User traffic packets arriving in-bound, wherein the assignment interval is

If packet collision occurs in the current time slot k, entering a collision resolution packet sending step; otherwise, return to step A1;

b, a collision resolution packet sending step:

the B1 system checks the packet transmission status in slot k, if a packet collision occurs, executes step B2; if the transmission is successful or the transmission packet is empty and the indicator is in the left set, go to step B3, if empty and the indicator is in the left set, go to step B3, if the transmission is successful and the indicator is in the right set, go to step B4;

b2 sets k to k +1, continues to transmit the first half of the last unsuccessfully transmitted packet in the current time slot k, sets T (k) to T (k-1), α (k) to α (k-1)/2, sets the indicator to left set, the system transmits the user traffic packets arriving in [ T (k), T (k) + a (k) ] in the current time slot k, and then returns to step B1;

b3 sets k to k +1, continues to transmit the second half of the last unsuccessfully transmitted packet in the current time slot k, sets T (k) to T (k-1) + α (k-1), α (k) to α (k-1), sets the indicator to right set, the system transmits the user traffic packets arriving in [ T (k), T (k) + a (k) ] in the current time slot k, and then returns to step B1;

b4 sets k to k +1 and sets the indicator to the right set, and returns to step a 1.

In order to better perform conflict resolution in the packet sending process, the invention establishes a mathematical model described by time for the arrival time sequence of the user service packet by user service modeling, thereby being convenient to predict the arrival time of the future user service packet.

The key point of the invention is that the time of arrival of the next user service packet is predicted

To determine the assignment interval for packet transmission in the current time slot

The assignment interval determines the length of time a (k) the packet arrives in the current slot. The assignment interval a (k) is an arrival time following the next user traffic packet

But the value of is changed in order to guarantee

The prediction is accurate, and the invention adopts a FARIMA (fractional autoregressive integrated moving average) model which is a mathematical model working under the self-similarity and long-correlation conditions. In the traditional conflict resolution, the operation mechanism and the selection of parameters of the algorithm are considered in an MAC layer (a media access control sublayer), different requirements of user services are not considered, a service model of a user is assumed to be Poisson arrival, and the self-similarity and long-term correlation presented by the user services in the current wireless network are inconsistent, so that the actual service is not well fitted, and the practicability of the conflict resolution algorithm is reduced. Different from the prior art, the FARIMA model adopted by the invention can be well matched with the current wireless network environment, the FARIMA model is used for fitting with the current user service group, and the whole group transmission method is combined, so that the group delay can be effectively reduced, and the network throughput rate can be improved.

The invention adopts the mathematical expression of a FARIMA (p, d, q) model as follows:

wherein, X_tThe user service packet arrival time sequence is represented by t, d is a difference order, d belongs to (-0.5, 0.5), p is an autoregressive order, q is a moving average order, p and q are non-negative integers, a_tIs a zero mean and has a variance of σ²And additionally:

Φ(B)＝1-φ₁B-φ₂B²...-φ_pB^p

Θ(B)＝1-θ₁B-θ₂B²-...-θ_qB^q

where Φ (B) and Θ (B) are complex variable polynomials with no common solution, and in addition Φ (B) is represented on the unit disk { B: no solution exists in the condition that B is less than or equal to 1. B is a backward shift operator, i.e. BX_t＝X_t-1. Definition of

In order to be a difference operator, the difference operator,

is a fractional difference operator, the binomial expansion of which is:

wherein,

where n is a temporary variable, and Γ represents a gamma function, defined as:

<math><mrow><mi>Γ</mi><mrow><mo>(</mo><mi>x</mi><mo>)</mo></mrow><mo>=</mo><msubsup><mo>&Integral;</mo><mn>0</mn><mo>∞</mo></msubsup><msup><mi>e</mi><mrow><mo>-</mo><mi>t</mi></mrow></msup><msup><mi>t</mi><mrow><mi>x</mi><mo>-</mo><mn>1</mn></mrow></msup><mi>dt</mi><mo>=</mo><mrow><mo>(</mo><mi>x</mi><mo>-</mo><mn>1</mn><mo>)</mo></mrow><mi>Γ</mi><mrow><mo>(</mo><mi>x</mi><mo>-</mo><mn>1</mn><mo>)</mo></mrow><mo>,</mo><mi>x</mi><mo>></mo><mn>0</mn><mo>,</mo></mrow></math>

then, it is possible to obtain:

wherein g (n) is defined as:

g(0)≡1，g(1)＝-d，g(n)＝g(n-1)*(n-1-d)/n

when 0 < d < 0.5, the FARIMA (p, d, q) model exhibits long-term correlation, and its parameter describing autocorrelation, Hurst parameter H, is 0.5+ d; when d is 0, FARIMA (p, d, q) degenerates into ARMA (p, q).

The parameters p, q and theta are difficult to calculate due to long-term correlation₁，θ₂，...，θ_q，φ₁，φ₂，...，φ_p，σ²Therefore, it is necessary to obtain the parameters p, q, θ by calculating an ARMA (p, q) model (autoregressive moving average) exhibiting a short-time correlation₁，θ₂，...，θ_q，φ₁，φ₂，...，φ_p，σ²The value of (c).

Specifically, the specific method for the system to establish the autoregressive score integration moving average model by using the time sequence of arrival of the user service group that has been sent before time t (k) in step a2 includes:

a2-1 sent user service packet X_tPerforming a de-averaging operation, i.e. performing X_tMu, where a zero mean traffic data sequence X is obtained_t- μ, wherein μ ═ E [ X_t]Is an expectation of a traffic sequence;

a2-2 adopts a regulated Adjusted Range Statistics algorithm to estimate a Hurst (Hurst) parameter H of the sequence, and a parameter d is H-0.5;

a2-3 is an autoregressive moving average model ARMA (p, q) sequence W_t，

A2-4 pairs sequence W with AIC (Akaike Information Criterion, Chikuchi Information content) Criterion_tDetermining order to obtain values of p and q;

a2-5 obtains the sequence W by approximate maximum likelihood estimation_tAll parameters theta of₁，θ₂，...，θ_q，φ₁，φ₂，...，φ_p，σ²；

A2-6 reaction of d, p, q, theta₁，θ₂，...，θ_q，φ₁，φ₂，...，φ_p，σ²And substituting the mathematical expression of the FARIMA (p, d, q) model to obtain the FARIMA (p, d, q) model of the user service.

Specifically, in step a3, the arrival time of the next user traffic packet is predicted by the FARIMA (p, d, q) model

The method comprises the following steps:

using the obtained

Can obtain

Wherein m, i and j are temporary variables;

{\hat{W}}_{t} (1) = E (W_{t + 1})

the method has the advantages that the method predicts the future actual user service, guides the later conflict resolution by using the prediction result, dynamically adjusts the distribution interval according to the conflict situation of the transmitted packet service, improves the conflict resolution efficiency, adopts a self-similarity FARIMA model to fit the actual service, and improves the accuracy of the prediction result compared with the fitting degree of simulating the actual service by adopting a Poisson model.

Drawings

Fig. 1 is a schematic diagram of an assignment interval when a current transmission timeslot k is 4000 in the embodiment;

fig. 2 is a schematic diagram of an assignment interval when the current transmission timeslot is k 4001 in the embodiment;

fig. 3 is a diagram illustrating an assignment interval when the current transmission timeslot is k 4002 in the embodiment;

fig. 4 is a diagram illustrating an assignment interval when the current transmission timeslot is k 4003 in the embodiment;

fig. 5 is a diagram illustrating an assignment interval when the current transmission timeslot is k 4004 in the embodiment;

FIG. 6 is a comparison graph of throughput simulation results of sending packets using the method of the present embodiment and FCFS;

FIG. 7 is a diagram illustrating comparison between the average delay simulation results of the FCFS and the method of the present embodiment;

fig. 8 is a comparison graph of simulation results of average conflict resolution cycles of FCFS and the method according to this embodiment.

Detailed Description

The following provides a specific implementation method of the patent in the wireless ad hoc network:

each node in the single-hop wireless ad hoc network system can model services, the service model adopts an anonymous grouping track collected from an SIGCOMM' 04 (from http:// www.crawdad.org/data. php) conference, service groups are sent according to the track, the system is operated for a period of time, and the nodes are convenient to model the services in the past period of time. After the modeling is successful, the system starts to operate normally until the packet track is completely sent, and the sending process is as follows:

a3 predicting arrival time of next user service packet by the FARIMA model

The A4 system is transmitted in [ T (k), T (k) + a (k) in the current time slot k]The user service packet of the inner arrival is assigned with the interval of

a collision resolution packet transmission step:

As shown in fig. 1, the system has already transmitted the user traffic packet that has reached at time 2000s (t (k) ═ 2000), and predicts the arrival time of the next user traffic packet by the established FARIMA model to be 2000.5s

The assignment interval is

Then, the system transmits the user traffic packet arriving in [2000, 2000.5] s in the current time slot k (k is 4000), wherein the assigned interval is 0.5s, if packet collision occurs in the current time slot k (k is 4000), then the system enters the collision resolution packet transmission step:

when the system checks that a packet collision occurs in time slot k (k is 4000) and the indicator is set as the left set, k is set to k +1, the first half of the last unsuccessfully transmitted packet is continuously transmitted in the current time slot k (k is 4001), T (k) is set to T (k-1), i.e., T (k) is 2000, and α (k) is 0.5/2, and the indicator is set as the left set, the system transmits the user traffic packet arriving in [2000, 2000.25] s in the current time slot k, as shown in fig. 2;

after that, the system checks that packet collision occurs in time slot k (k ═ 4001), sets k ═ k +1, continues to transmit the first half of the last unsuccessfully transmitted packet in the current time slot k (k ═ 4002), sets T (k) ═ T (k-1), i.e., T (k) ═ 2000, α (k) ═ 0.25/2, and sets the indicator to the left set, and the system transmits the user traffic packet arriving in [2000, 2000.125] s in the current time slot k, as shown in fig. 3;

after that, the system checks that no packet collision occurs in time slot k (k ═ 4002), and the user traffic packet arriving in [2000, 2000.125] s is successfully transmitted, then k ═ k +1 is set, the last half of the last unsuccessfully transmitted packet is continuously transmitted in the current time slot k (k ═ 4003), T (k) ═ T (k-1) + α (k-1), i.e. T (k) ═ 2000.125, α (k) ═ α (k-1), i.e. α (k) ═ 0.25/2, and the indicator is set as the right set, and the system transmits the user traffic packet arriving in [2000.125, 2000.25] s in the current time slot k, as shown in fig. 4;

the system checks that the transmission is in [2000.125, 2000.25] in time slot k (k ═ 4003)]If the user service packet arrived within s is successfully sent and the indicator is the right set, the indicator is continuously set as the right set, and the FARIMA model is established through the user service packet arrived within 2000.25s to predict the arrival time of the next user service packet within 2000.5s

Then the system transmits in [2000.25, 2000.5] in the current time slot k (k ═ 4004)]s, where the assignment interval is 0.25s, as shown in fig. 5. If packet collision occurs in the current time slot k (k is 4004), entering a collision resolution packet transmission step again, and if the packet collision occurs in the current time slot k (k is 4004), continuing to determine a new assignment interval by predicting the arrival time of the next user traffic packet.

The specific method for the system to establish the FARIMA model by the time sequence of arrival of the user service packet that has been sent before time t (k) in step a2 is as follows:

a2-1 sentUser traffic packet X_tPerforming a de-averaging operation, i.e. performing X_tMu, where a zero mean traffic data sequence X is obtained_t- μ, wherein μ ═ E [ X_t]Is an expectation of a traffic sequence;

a2-2 adopts a regulated Adjusted Range Statistics algorithm to estimate a Hurst parameter H of the sequence, and a parameter d is H-0.5;

a2-3 is an autoregressive moving average model ARMA (p, q) sequence W_t，

A2-4 uses AIC (Akaike Information criterion) criterion to sequence W_tDetermining order to obtain values of p and q;

The method comprises the following steps:

using the obtained

Can obtain

Wherein m, i and j are temporary variables;

{\hat{W}}_{t} (1) = E (W_{t + 1})

in practice, where infinite summation is involved (e.g., m in step a 3), the larger value is used instead of converting infinite summation into summation of larger value.

It can be seen from the computer simulation result that the conflict resolution of the present embodiment can efficiently and quickly resolve conflict packets under the self-similar service stream, and the system throughput rate, average delay, and average packet conflict resolution period are all obviously superior to the FCFS algorithm:

as shown in fig. 6, the throughput simulation results of this embodiment and the FCFS algorithm are compared: predition _ CRA refers to this embodiment, FCFS refers to the FCFS algorithm, Sig04_ ver01, Sig04_ ver02 and Sig04_ ver03 represent three segments of traffic flows collected from sigcomp' 04 conference, each segment containing 10000 packets. The abscissa is the arrival rate of the packet, the unit is the number of packets/time slot, the ordinate is the throughput rate, and the unit is the number of packets/time slot. As can be seen from fig. 6, the maximum throughput rate of FCFS is only 0.37, whereas the maximum throughput rate of the present embodiment is 0.4.

As shown in fig. 7, the simulation results of the average delay of the FCFS algorithm are compared with each other: predition _ CRA refers to this embodiment, FCFS refers to FCFS, Sig04_ ver01, Sig04_ ver02 and Sig04_ ver03 represent three segments of traffic flows collected from sigcomp' 04 conference, each segment containing 10000 packets. The horizontal coordinate is the arrival rate of the message, the unit is the number of the message/time slot, the vertical coordinate is the average time delay, the unit is the time slot, and the scaling mode is the logarithmic coordinate. As can be seen from fig. 7, the average delay of this embodiment is smaller than the FCFS algorithm by about 5%.

As shown in fig. 8, the simulation results of the average collision resolution cycle of the FCFS algorithm are compared: predition _ CRA refers to this embodiment, FCFS refers to FCFS, Sig04_ ver01, Sig04_ ver02 and Sig04_ ver03 represent three segments of traffic flows collected from sigcomp' 04 conference, each segment containing 10000 packets. The abscissa is the arrival rate of the packet, the unit is the number of packets/time slot, and the ordinate is the average collision resolution period, the unit is the number of times. In the context of traffic flow of Sig04_ ver03 in fig. 8, the average collision resolution period of this embodiment is only about 70% of the FCFS algorithm.

Claims

1. A method for prediction-based packet transmission in a communication channel, comprising the steps of:

a packet transmission step based on prediction:

the a2 system establishes a FARIMA model by establishing an arriving time series of user traffic packets that have been sent completed before time t (k);

a3 predicting arrival time of next user service packet by the FARIMA model

b, a collision resolution packet sending step:

2. The prediction-based packet transmission method in communication channel of claim 1, wherein the specific method for the system to build the autoregressive score integrated moving average model for the time sequence of arrival of the user traffic packets that have been transmitted before time t (k) in step a2 is:

a2-2 adopts a re-standard polar difference method to estimate a hester parameter H of the sequence, and a parameter d is H-0.5;

a2-3 is an autoregressive moving average model ARMA (p, q) sequence W_t，

A2-4 sequence W using Chichi information criterion_tDetermining order to obtain values of p and q;

A2-6 reaction of d, p, q, theta₁，θ₂，...，θ_q，φ₁，φ₂，...，φ_p，σ²And (4) substituting the FARIMA (p, d, q) model to obtain the FARIMA (p, d, q) model of the user service.

3. The prediction-based packet transmission method in a communication channel of claim 2, wherein the FARIMA (p, d, q) model is:

wherein, X_tThe user service packet arrival time sequence is represented by t, d is a difference order, d belongs to (-0.5, 0.5), p is an autoregressive order, q is a moving average order, p and q are non-negative integers, a_tIs one zeroMean and variance σ²And:

Φ(B)＝1-φ₁B-φ₂B²...-φ_pB^p

Θ(B)＝1-θ₁B-θ₂B²-...-θ_qB^q

where Φ (B) and Θ (B) are complex variable polynomials with no common solution, and in addition Φ (B) is represented on the unit disk { B: no solution exists in the condition that B is less than or equal to 1; b is a backward shift operator, i.e. BX_t＝X_t-1(ii) a Definition of

In order to be a difference operator, the difference operator,

is a fractional difference operator, the binomial expansion of which is:

wherein,

where n is a temporary variable and Γ represents a gamma function, defined as:

thus:

wherein g (n) is defined as:

g(0)≡1，g(1)＝-d，g(n)＝g(n-1)*(n-1-d)/n。

4. the prediction-based packet transmission method in a communication channel of claim 3, wherein the arrival time of the next user traffic packet is predicted in step a3 by a FARIMA (p, d, q) model

The method comprises the following steps:

using the obtained

Can obtain

Wherein m, i and j are temporary variables;

{\hat{W}}_{t} (1) = E (W_{t + 1})