KR100784852B1 - Time-based Fairness Packet Scheduling in Wireless Ad-hoc Networks - Google Patents

Abstract

The present invention relates to a distributed packet scheduling method in a wireless ad hoc network, which is based on a time-based method for improving the throughput of an entire network by determining the transmission order of each flow in a distributed manner in consideration of multiple data rates of a physical layer. A packet scheduling method for providing fairness.

The present invention provides a distributed packet scheduling method of an ad hoc network.

Comparing the data rate of each flow with the data rate of the flow with the lowest data rate; Calculating the number of packets to be transmitted using the comparison result; And setting a flag in a frame to be transmitted according to the result of calculating the number of packets and transmitting the flag.

Description

A time-based fairness packet scheduling method in wireless ad-hoc networks

1 is a node graph of a typical ad hoc network to which the present invention is applied.

2 is a diagram illustrating a flow competition of FIG. 1 to which the present invention is applied.

3 is a node graph of an ad hoc network using multiple data rates to which the present invention is applied.

4 is a diagram illustrating the flow competition of FIG. 3 to which the present invention is applied.

FIG. 5 is a diagram comparing packet flows providing throughput-based fairness with each flow service sequence and channel occupancy time of packet scheduling providing time-based fairness according to an embodiment of the present invention. FIG.

FIG. 6 is a diagram illustrating packet scheduling providing time-based fairness in a network providing multiple data rates according to an embodiment of the present invention, and each flow service sequence and channel occupancy of EMLM-FQ when the data rates of all flows are the lowest. Drawing comparing time.

7 is a diagram illustrating a service order and a channel occupancy time of a packet of each flow according to an embodiment of the present invention.

 8 is an overall flowchart of a packet scheduling method according to an embodiment of the present invention.

The present invention relates to a distributed packet scheduling method in a wireless ad hoc network, which is based on a time-based method for improving the throughput of an entire network by determining the transmission order of each flow in a distributed manner in consideration of multiple data rates of a physical layer. A packet scheduling method for providing fairness.

The ad hoc network is a wireless network that provides autonomy and flexibility to provide a wireless data service in emergency rescue or battlefield by easily and autonomously forming a network with only mobile terminals without the help of a fixed base network. The nodes constituting the ad hoc network have a wireless interface, and are often referred to as mobile nodes because they satisfy a host having a mobile computing function and a router having a routing function at the same time. The mobile node has a data transfer function as an intermediate node because the reach distance is limited due to the low power, etc., and the supply of energy is not constant because of the use of a battery.

Existing IEEE 802.11, which is popularly used to construct the ad hoc network, provides one data rate of 2 Mbps, but commercially successful IEEE 802.11b provides data rates of 1, 2, 5.5, and 11 Mpbs and IEEE 802.11g. Provides data rates of 6, 9, 12, 18, 24, 36, and 54 Mbps at the physical layer of each standard. Efforts to use these multiple data rates in the ad hoc network began with the research related to routing, and recently, performance analysis studies have been conducted in the ad hoc networks providing multiple data rates. However, there have been few studies considering multiple data rates in packet scheduling in the ad hoc network. The reason is that in order to provide throughput-based fairness, wired process queuing methods such as start-time fair queuing (SFQ) and weighted fair queuing (WFQ) are applied to the ad hoc packet scheduling. . The basic assumption of this packet scheduling scheme is that the channel capacity is fixed. Therefore, since it is not easy to fix channel capacity in an environment in which multiple data rates are provided, the ad hoc packet scheduling study does not consider an environment in which multiple data rates are provided.

Conventional ad hoc packet scheduling methods provide fairness based on throughput. Scheduling schemes that provide throughput-based fairness can be divided into credit-based process scheduling schemes proposed for TDMA-based ad hoc networks and process scheduling schemes based on time stamps. In order to provide throughput based fixedness, the packet scheduling scheme based on time stamp has two service tags (start tag and finish tag) based on start-time fair queuing (SFQ), and the smallest start tag ( service a packet with a start tag).

1 and 2, issues to be considered when designing packet scheduling of an ad hoc network according to the present invention will be described.

1 illustrates a node graph of a general ad hoc network to which the present invention is applied, and FIG. 2 illustrates a flow competition graph showing the flow competition of FIG. 1.

When designing packet scheduling in an ad hoc network environment, the following design issues should be considered.

 First, because wireless data transmission is broadcasting locally, competition for shared channels is location dependent. For example, when there are five nodes (Ni, i = 0, ..., 4) and four flows (Fj, j = 0, ..., 3) as shown in the node graph of FIG. It can be converted into a flow competition graph as shown in FIG. In FIG. 2 each vertex represents a flow and each edge represents a race relationship between the flows. F0 200 is in competition with F1 201 and F2 202, but is not directly in competition with F3 203. Therefore, F0 200 and F3 203 can be serviced simultaneously. Similarly, F1 201 is in competition with F0 200, F2 202, and F3 203. As such, the set of flows that are in competition between flows depends on the location of the flow.

In addition, flows that are not directly competing, such as F0 200 and F3 203, can be serviced simultaneously, but only one flow can be serviced at a time to provide strict fairness between competing flows. If two flows F0 200 and F3 203 are not in direct competition and are simultaneously serviced, there is a problem that impairs fairness. However, if only one of the flows that can be serviced at the same time, there is a disadvantage in reducing the throughput of the network. This problem is called a spatial channel reuse problem.

2) Distributed Attributes of Ed-Hog Scheduling-In a wired or cellular network, each router, switch, or base station has accurate information about all flows when determining packet scheduling. However, in an ad hoc network, competing flows may occur at different transmitting nodes, and each transmitting node may not directly access flow information of another transmitting node. This indicates that when designing packet scheduling in an ad hoc network, it involves a problem that needs to be calculated using distributed flow information.

Considering the above design issues, a representative scheduling method that applies a wired packet scheduling method such as SFQ to an ad hoc network is EMLM-FQ (Enhanced- Maximize-Local-Minimum Fair Queueing). EMLM-FQ provides each flow in the network with the amount of service shown in Equation 1.

는 플로우

가 시간

부터

까지 받은 서비스의 양이고, C 는 채널 용량이고,

와

는 각각 플로우

와

의 가중치이며, S는 플로우 경쟁 그래프에서 플로우

와 직접 연결되어 있는 플로우의 집합이다.

와

는 위치 종속적 상수이다.In Equation 1

Flow

Fall time

from

Is the amount of service received, C is the channel capacity,

Wow

Each flow

Wow

Is the weight of, where S is the flow in the flow competition graph

A collection of flows that are directly connected to.

Wow

Is a position dependent constant.

However, the channel capacity C is not fixed for each flow as in the IEEE 802.11x physical layer used to construct an actual ad hoc network. Therefore, there is a problem that is not suitable for application in a network using multiple data rates in the physical layer.

Accordingly, an object of the present invention is to provide a distributed packet scheduling method considering multiple data rates in an ad hoc network in order to solve the above problems.

In addition, an object of the present invention is to provide a packet scheduling method that provides a new fairness model, time-based fairness in consideration of the data rate of the physical layer constituting the ad hoc network.

Another object of the present invention is to provide a packet scheduling method for exchanging service tag information of each flow and determining a scheduling order in a distributed method in a packet scheduling method in an ad hoc network.

The present invention for achieving the above object in the distributed packet scheduling method of the ad hoc network,

Comparing the data rate of each flow with the data rate of the flow with the lowest data rate; Calculating the number of packets to be transmitted using the comparison result; And setting a flag in a frame to be transmitted according to the result of calculating the number of packets and transmitting the flag.

Hereinafter, a detailed description of a preferred embodiment of the present invention will be described with reference to the accompanying drawings. In the following description, detailed descriptions of well-known functions or configurations will be omitted when it is determined that the detailed descriptions of the known functions or configurations may unnecessarily obscure the subject matter of the present invention.

1. Network Model

The network environment considered in the present invention considers an environment providing multiple data rates in the physical layer and the MAC layer and a multi-hop wireless ad hoc network in which all nodes share the same channel. Also, only nodes within the transmission range of the transmitting node can receive packets. A single flow is defined as a series of packet streams transmitted from a single transmitting node to a single receiving node.

The MAC layer applied in the present invention follows the RBAR (Receiver Based AutoRate) protocol as a general CSMA / CA paradigm and a multiple data rate adaptation technique. The RBAR protocol is a method in which a receiving node selects an appropriate data rate for transmitting data frames during a request-to-send (RTS) and clear-to-send (CTS) frame exchange, and notifies the transmitting node.

When a transmitting node transmits a short control frame, Request-to-Send (RTS), to a receiving node to transmit one packet, the receiving node checks whether there is a node transmitting a packet among its neighboring nodes. . If no node is transmitting, the signal-to-noise ratio (SNR) is measured to determine the optimal data rate, and the information is included in the clear-to-send (CTS). The transmitting node receiving the CTS sends a Data-Sending (DS) frame in response to the CTS to the receiving node for the purpose of informing neighboring nodes of the success of the RTS-CTS handshake, and transmits a DATA frame. Finally, the receiving node transmits an ACK frame to the transmitting node in response to receiving a successful DATA frame. All nodes one hop away from the transmitting node and the receiving node can hear all of the above control messages.

Hereinafter, time-based fairness according to the present invention will be described with reference to the accompanying drawings.

FIG. 3 shows a node graph of an ad hoc network using multiple data rates to which the present invention is applied, and FIG. 4 shows the flow competition of FIG.

FIG. 5 illustrates a comparison of channel occupancy time and flow order of packets of a packet scheduling providing throughput based fairness and a packet scheduling providing time based fairness according to an embodiment of the present invention, and FIG. This paper shows the packet scheduling that provides time-based fairness in the multi-data rate network according to different flow rates and the channel occupancy time of each flow of EMLM-FQ when the data rate of all flows is the lowest.

2. Time based fairness

The proposed ad hoc packet scheduling is based on packet scheduling on the wire such as Start-Time Fair Queuing (SFQ) to provide throughput-based fairness between flows. This throughput-based fairness means that the total amount of services received by each flow is the same according to the weight of each flow. On the other hand, time-based fairness means that the total channel occupancy time used by each flow is equal.

이다. When all flows in the network are in direct competition with each other as shown in FIG. 4 for the node graph of FIG. 3, FIG. 5 shows each flow for the EMLM-FQ providing throughput based fairness and the packet scheduling method providing time based fairness. Indicates service order and channel occupancy time. Assuming that each flow has the same packet size and weight, the initial service tag for each flow

to be.

If all flows are in direct competition as shown in FIG. 4, the EMLM-FQ services packets of each flow in the order of F0 400, F1 401, and F2 402. When providing time-based fairness, the channel time occupied by each flow must be fair, so that each flow has the same channel occupancy time based on the channel occupancy time used by the F2 402 with the lowest data rate to send one packet. To have. When providing throughput-based fairness, as shown in Figure 7, 10 packets can be served when six packets are served time-based fairness. In other words, network throughput is improved by about 40%.

은 <수학식 2>와 같이 정의한다.Channel occupation time for each flow f

Is defined as in Equation 2.

는 플로우 f의 패킷 사이즈,

는 플로우 f의 데이터률이다.

는 F의 모든 플로우가 하나의 패킷을 서비스 하는데 사용하는 채널 점유 시간에서 플로우 f가 하나의 패킷을 서비스 하는데 사용하는 채널 점유 시간이 차지하는 비율을 나타낸다. F is the set of all flows present in the flow competition graph,

Is the packet size of flow f,

Is the data rate of flow f.

Denotes the ratio of channel occupancy time that flow f uses to service one packet to channel occupancy time that all flows of F use to service one packet.

Assuming the channel is always in use, the total channel occupancy time of the flow is defined as <math 3>.

, Guaranteed Time)은 <수학식 4>와 같이 정의한다.Assuming that the weights of competing flows are the same, the channel occupancy time that each flow should be guaranteed based on time-based fairness (

, Guaranteed Time) is defined as in Equation 4.

은 플로우 경쟁 그래프에서 연결된 플로우들 중 가장 낮은 데이터률을 갖는 플로우의 데이터률이다. 경쟁 그래프의 모든 플로우의 패킷 사이즈가 동일하다고 가정하면 GF(f)는 <수학식 5>로 도식화 된다.

Is the data rate of the flow with the lowest data rate among the flows connected in the flow competition graph. Assuming that the packet sizes of all flows in the contention graph are the same, GF (f) is represented by Equation 5.

 N is the total number of flows connected in the competition graph.

이면, 플로우 f는 보상 받을 시간이 존재하지 않고,

이면, 플로우 f는 보상 받을 시간이 존재한다. 경쟁 그래프에서 연결된 각 플로우가 보상 받아야 하는 시간은 경쟁 관계에 있는 플로우들 중 가장 낮은 데이터률(

)을 가진 플로우가 하나의 패킷을 서비스 할 때, 그 플로우가 보내야 되는 패킷의 수로 나타낼 수 있다. 보상 받아야 하는 시간이 존재하는 플로우 f는 시간 기반 공정성을 달성하기 위해서 f가 전송해야 하는 패킷 수(P(f))는 <수학식 6>과 같이 정의된다.

Flow f has no time to compensate,

If there is, flow f has time to be compensated. The time that each flow connected in the competition graph should be compensated for is the lowest data rate among the competing flows (

When a flow with) serves a packet, it can be represented by the number of packets that the flow should send. In the flow f in which time to be compensated exists, the number of packets P (f) that f must transmit is defined as in Equation 6 to achieve time-based fairness.

Thus, F0 of FIG. 3 must transmit five packets to achieve time based fairness compared to F2 with dmin. Time-based fairness (TF) is defined as in Equation 7.

는 플로우 i가 시간 t₁부터 시간 t₂ 까지 점유하는 채널 점유 시간이다. <수학식 7>의 값이 0에 근접할수록 이상적인 시간 기반 공정성을 제공한다. In the above equation

Is the channel occupancy time that flow i occupies from time t ₁ to time t ₂ . As the value of Equation 7 approaches 0, it provides the ideal time-based fairness.

을 갖는 플로우

이 받는 최소 서비스의 양은 EMLM-FQ의 <수학식 1>에서 정의한 각 플로우가 받는 최소 서비스의 양에서 유도된다. 그 이유는 도 3에서 모든 플로우의 데이터률이

이라 가정할 때, EMLM-FQ에서 제공하는 각 플로우의 최소 서비스 양을 도 6과 같이 제공하기 때문이다.

With

The minimum amount of service received is derived from the minimum amount of service received by each flow defined in Equation 1 of EMLM-FQ. The reason for this is that in FIG.

It is assumed that this is because the minimum service amount of each flow provided by the EMLM-FQ is provided as shown in FIG. 6.

이 받는 최소 서비스 양

은 <수학식 8>과 같이 정의된다.For example, the minimum amount of service received by F2 with the minimum data rate is equal to the minimum amount of service received by F2 in EMLM-FQ, assuming that the data rate of F2 is the data rate of all flows. therefore

Minimum amount of services received

Is defined as in Equation 8.

와

는 각각 플로우 g와 f의 가중치이며, S는 플로우 경쟁 그래프에서 플로우 f와 직접 연결되어 있는 플로우들의 집합이고

와

는 각 플로우의 경쟁관계에 따라 정의한 위치 종속적 상수이다. 플로우의 가중치가 동일하다고 가정하면

는 <수학식 9>과 같다. n은 플로우 경쟁 그래프에서 f와 직접 연결되어 있는 플로우의 수이다.here

Wow

Are the weights of flows g and f, respectively, S is the set of flows directly connected to flow f in the flow competition graph

Wow

Is a position dependent constant defined according to the competition of each flow. Assuming the weights of the flows are equal

Is the same as Equation 9. n is the number of flows directly connected to f in the flow competition graph.

은 <수학식 10>과 같이 정의된다. Minimum amount of service received by flows with data rates greater than d _min

Is defined as in Equation 10.

3. Packet Scheduling

The service tag allocation method and the exchange method for service tag information of each flow of the ad hoc packet scheduling method of the present invention follow EMLM-FQ. However, in order to provide time-based fairness, in order to calculate the number of packets to be transmitted according to the data rate of each flow, all nodes listen to data rate information of the flows of adjacent nodes, store them in their local tables, and The lowest data rate (d _min ) is stored compared to the data rate of the flow existing in the table, and is included in the control frame (RTS, CTS, DS, ACK) for data transmission. If you are listening to information on a lower data rate than the local table d _min, and stores a local table in the data rate d _min, transfer, and inserted in the control frame. Therefore, all transmitting nodes with flows connected to the contention graph get information about the lowest data rate among the contention flows.

The local table may be represented as a table including a flow ID, a start tag, an end tag, a flow data rate, and a minimum data rate dmin existing on a network.

In addition, the number of packets P (f) and <Equation 6> that the transmitting node should transmit is calculated by comparing d _min with the data rate of the flow that the transmitting node is to service during the scheduling process. If greater than 1 and there are backlogged packets, then P (f) packets have the same service tag and try to transmit immediately. That is, the service tag is not updated in the scheduling process until P (f) packets are serviced. P (f) -1 packets except the first among P (f) packets are set to 1 bit interval (NCB: Not Compare Bit) of the RTS frame to prevent RTS discarding at the receiving node during transmission. To transmit. If the NCB section is set to 1 in the RTS frame, the receiving node responds directly to the CTS to service the flow if the channel is not currently in use.

(수신 노드의 로컬 테이블에 따른 플로우 f의 백오프 예측 값)를 포함하는 RTS를 전송한다. RTS를 받은 수신 노드는 자신의 로컬 테이블에서 플로우 f에 대한 백오프 값

이

보다 작거나 같으면 CTS로 응답하고, 그렇지 않으면 CTS를 전송하지 않는다. Each packet transmission in the present invention follows the RTS-CTS-DS-DATA-ACK handshake process and follows the RBAR protocol to determine the data rate at which packets can be transmitted. If one node is doing some transmission by another node during the backoff, it stops the backoff timer until the end of the transmission and updates the service tag information in the local table for the flow being transmitted. If the back off timer of flow f expires and the channel is not busy

Send an RTS including (backoff prediction value of flow f according to the local table of the receiving node). The receiving node receiving the RTS has a backoff value for flow f in its local table.

this

If it is less than or equal to, respond with CTS; otherwise, do not send CTS.

Control frame (RTS, CTS, DS, DS) to inform all neighbor nodes that are one hop away from the sending and receiving nodes about the service tag information of the flow, the data rate and the lowest data rate (d _min ) in the network. ACK) is transmitted with the service tag and d _min , and the data rate of the flow is transmitted with the CTS, DS and ACK frames.

The reason why the data rate of the flow is not transmitted to the RTS is because the RBAR is adopted as a multiple data rate adaptation technique, since the transmitting node does not know the data rate to transmit until the receiving node includes the selected data rate in the CTS and transmits it. to be. In addition, the update service tag for the flow is not included in the RTS and CTS frames. The reason is that RTS and CTS do not guarantee channel acquisition. After the RTS-CTS process is successful, neighboring nodes are notified of update tags for flows in the DS and ACK frames. In this way, the service tag information of the correct flow for scheduling is delivered.

Information about flows that are one hop away from the contention graph may be distributed between the transmitting node and the receiving node. Therefore, the method of setting the backoff value for the flow f of the transmitting node should set the backoff value in consideration of the tables maintained at the transmitting node and the receiving node.

이다.

는 플로우 f의 백오프 값이고,

는 송신 노드의 로컬 테이블에 따른 플로우 f의 백오프 값,

은 수신 노드의 로컬 테이블에 따른 플로우 f의 백오프 값이다.In other words,

to be.

Is the backoff value of flow f,

Is the backoff value of flow f according to the local table of the sending node,

Is the backoff value of flow f according to the local table of the receiving node.

는 정확히 알지만,

은 알 수 없다. 따라서 송신 노드가

을 예측할 수 있도록, 수신 노드는 ACK 프레임에 두 개의 파라미터(M_f,b_f)를 추가하여 전송한다. M_f는 수신 노드의 로컬 테이블에서 플로우 f가 서비스하기 전에, 서비스 되어야 하는 플로우들의 바이트 수이다. M_f는 <수학식 11>과 같이 계산된다.However, at the sending node

I know exactly,

Is unknown. Therefore, the sending node

In order to predict, the receiving node adds two parameters (M _f , b _f ) to the ACK frame and transmits them. M _f is the number of bytes of flows that must be serviced before flow f services in the local table of the receiving node. M _f is calculated as shown in Equation (11).

는 플로우 f의 가중치이고,

는 수신 노드의 로컬 테이블에서 플로우 f의 서비스 태그(

)보다 작은 플로우의 서비스 태그이다.

는 수신 노드의 로컬 테이블에서 서비스 태그보다 작은 서비스 태그를 갖는 플로우들의 집합이다.

는 수신 노드의 테이블에서 플로우 f의 백오프 기간을 나타낸다. 따라서 송신 노드가

를 ACK 프레임을 통해 받으면 임의의 시간 t에서의

은 <수학식 12>와 같이 계산할 수 있다.In the above equation

Is the weight of flow f,

Is the service tag of the flow f in the local table of the receiving node (

Service tag for flows smaller than).

Is a set of flows with a service tag smaller than the service tag in the local table of the receiving node.

Denotes the backoff period of flow f in the table of the receiving node. Therefore, the sending node

Is received through the ACK frame at any time t

Can be calculated as shown in Equation 12.

는 이전에 ACK 프레임을 받은 시간이다.In the above equation

Is the time when the previous ACK frame was received.

Packet scheduling in the present invention follows the following procedure.

If node n detects that the channel is not in use,

에서 가장 작은 서비스 태그를 가지고 있다면 즉시 HOL(Head of Line) 패킷을 전송한다. 만약, f의 데이터률이 d_min보다 크다면, 시간 공정성을 달성하기 위해 전송해야 하는 패킷 수(P(f))를 구하고, P(f)개의 패킷들의 서비스 태그를 업데이트하지 않고 동일한 서비스 태그를 갖는다. P(f)개의 패킷들은 즉시 전송을 시도하고, P(f)개의 패킷들이 서비스 된 후 패킷의 서비스 태그를 업데이트한다. a) Flow table to send local table

If it has the smallest service tag, it immediately sends a HOL (Head of Line) packet. If the data rate of f is greater than d _min , the number of packets P (f) to be transmitted is obtained to achieve time fairness, and the same service tag is updated without updating the service tags of the P (f) packets. Have P (f) packets attempt to transmit immediately, and update the packet's service tag after P (f) packets are serviced.

)에 존재 하면, f의 백오프 값

을

로 설정하고, 백오프 타이머가 동작을 시작한다. b) A flow with a service tag smaller than f can have its own local table (

If present, the backoff value of f

of

Set to, the backoff timer starts operation.

c) If f's backoff timer expires and the channel is not busy, send a HOL packet of f.

Hereinafter, a packet scheduling method according to the present invention will be described with reference to FIG. 7.

7 illustrates a service order and a channel occupancy time of a packet of each flow according to an embodiment of the present invention.

는 초기 서비스 태그 값으로 각각

을 갖는다. 또한

이라 가정하면, 도 7과 같이 F0는 가장 작은 서비스 태그를 갖기 때문에 즉시 pkt 0의 전송을 시작한다. 전송을 시작하기 전에 F0의 데이터률은 네크워크에 존재하는 가장 낮은 데이터률 보다 5배 높기 때문에, 시간 기반 공정성을 달성하기 위해서 전송해야 할 패킷 수를 계산하고 F0의 첫 번째 패킷 pkt 0을 전송할 때, DS와 ACK 프레임에 업데이트 태그를 붙이지 않는다. 그 이유는, 만약 노드 N1이 F0의 업데이트 태그를 수신하면 즉시 F1의 pkt 0(703)를 서비스하기 위해 채널에 접근을 시도할 것이기 때문이다. 따라서, 업데이트 태그를 붙이지 않음으로써, F0의 전송해야 할 나머지 패킷에게 전송할 기회를 줄 수 있다. pkt 0(703) 전송 후에, F0는 스케줄링 과정에서 전송해야 할 5개의 패킷 중 마지막 패킷 pkt 4가 서비스 되기 전까지 서비스 태그를 업데이트 하지 않기 때문에 F0는 가장 작은 서비스 태그를 가지므로 F0의 pkt 1(704) , pkt 2(705), pkt 3(706) 및 pkt 4(707)는 즉시 전송을 시도한다. 또한, pkt 1(704), pkt 2(705), pkt 3(706) 및 pkt 4(707)를 전송할 때, RTS 프레임의 NCB(Not Compare Bit)를 1로 설정하여 전송한다. 이러한 방법으로 수신 노드에서는 값의 비교 없이 RTS 프레임에 대한 응답으로 CTS 프레임을 즉시 전송하도록 할 수 있다. F0의 전송해야 할 5개의 패킷 중 마지막 패킷인 pkt 4(707) 전송시 DS와 ACK 프레임에 업데이트 태그를 붙여서 주변 노드들에게 공지한다. 노드 N1이 F0의 pkt 4(707)의 업데이트 태그를 수신하면 F1의 패킷을 서비스하기 위해서 즉시 채널에 접근한다. Suppose a network like Figure 3 exists. The packet size and weight of each flow are the same. Each flow

Is the initial service tag value

Has Also

Suppose that, since F0 has the smallest service tag as shown in FIG. 7, the transmission of pkt 0 is immediately started. Before starting the transmission, the data rate of F0 is five times higher than the lowest data rate present in the network, so when calculating the number of packets to be transmitted in order to achieve time-based fairness, and sending the first packet pkt 0 of F0, Do not add update tags to the DS and ACK frames. The reason is that if node N1 receives an update tag of F0, it will immediately attempt to access the channel to service pkt 0 703 of F1. Therefore, by not attaching an update tag, the remaining packets of F0 to be transmitted can be given an opportunity to transmit. After pkt 0 (703) transmission, F0 does not update the service tag until the last packet pkt 4 of the five packets to be transmitted in the scheduling process, so F0 has the smallest service tag, so pkt 1 (704) of F0. ), pkt 2 705, pkt 3 706 and pkt 4 707 attempt to send immediately. In addition, when transmitting pkt 1 704, pkt 2 705, pkt 3 706, and pkt 4 707, NCB (Not Compare Bit) of the RTS frame is set to 1 and transmitted. In this way, the receiving node can immediately transmit the CTS frame in response to the RTS frame without comparing the values. When transmitting pkt 4 (707), which is the last packet among the five packets to be transmitted, the update tag is attached to the DS and ACK frames to notify neighboring nodes. When node N1 receives the update tag of pkt 4 707 of F0, it accesses the channel immediately to service the packet of F1.

Before sending the first packet pkt 0 (708) of F1, calculate P (f) = 2 like F0, and set NCB to 1 when sending pkt 1 (709) after transmission of pkt 0 (708) of F1. And attach update tags when transmitting DS and ACK frames. Since F2 is P (f) = 1, there are no packets to be additionally transmitted. Therefore, when transmitting the packet pkt 0 (10) of the F2, it transmits with an update tag when transmitting the DS and ACK frame.

8 is an overall flowchart illustrating a packet scheduling method according to the present invention.

A summary of the procedure described above may be shown as shown in FIG. 8.

Before the node transmits the packet, the node first receives the minimum data rate dmin existing on the network (S801) and counts the number of packets (S802). The number of packets can be calculated by Equation 6 by comparing d _min with the data rate of a flow to be transmitted by a transmitting node during a scheduling process.

As a result of the calculation, it is checked whether the number of packets is greater than 1 (S803), and if it is large, one packet less than the result is transmitted, and a flag-NCB (not compare bit)-is set during transmission (S804).

The updated service tag is included in the last packet from the calculated number of packets and transmitted (S805).

If the calculated number of packets is less than 1, the packet is immediately transmitted without a procedure such as setting a flag including an updated service tag (S806).

Although embodiments of the present invention have been described with respect to specific embodiments, various modifications are possible without departing from the scope of the present invention. Therefore, the scope of the present invention should not be limited to the described embodiments, but should be defined not only by the appended claims, but also by the equivalents of the claims.

According to the present invention, in a network environment in which multiple data rates are provided in the physical layer, a packet to be transmitted is calculated by calculating the number of packets to be transmitted by each flow compared to the data rate of each flow and the lowest data rate on the network. By sending as many as possible, the overall network throughput is greatly improved.

In addition, according to the present invention, the network throughput can be greatly improved by providing time-based fairness based on the data rate in a network having a different data rate for each flow in the physical layer such as a wireless ad hoc network.

Claims (10)

In the distributed packet scheduling method of the ad hoc network, Comparing the data rate of each flow with the data rate of the flow with the lowest data rate; Calculating the number of packets to be transmitted using the comparison result; And And setting and transmitting a flag in a frame to be transmitted according to the calculation result of the number of packets. The method of claim 1, wherein after setting and transmitting a flag in the frame to be transmitted, data rate information of flows of adjacent nodes of all nodes is obtained, stored in a local table, and data of a flow existing in the local table. And storing the lowest data rate in comparison with the rate and including the same in a control frame to transmit the data. The data rate according to claim 2, wherein the information on the lowest data rate stored is included in a control frame at the time of packet transmission and transmitted, and if information about a data rate lower than the stored data rate is obtained from an adjacent node, And updating said stored data rate. 2. The method of claim 1, wherein calculating the number of packets is calculated by the ratio of the data rate of the flow to the data rate of the flow with the lowest data rate. The method of claim 4, further comprising: transmitting (packet number-1) packets when the number of packets exceeds one, and setting a flag in a control frame during transmission; And including the updated service tag in the last packet of the transport packet and transmitting the updated packet. 5. The method of claim 4, wherein when the number of packets exceeds one, the packet is transmitted with an update tag attached to a DS and an ACK frame when the last packet is transmitted. 2. The method of claim 1, wherein when the flag is set to 1, a CTS is sent by a receiving node without discarding the RTS. In the distributed packet scheduling method of the ad hoc network, Comparing the data rate of each flow with the data rate of the flow with the lowest data rate; And When the flow having the lowest data rate as a result of the comparison transmits one packet, the time-based fairness packet scheduling method characterized in that each flow has the same channel occupancy time based on the channel occupancy time used. 9. The method of claim 8, wherein the channel occupancy time T (f) of each flow is one packet pulled at a channel occupancy time that all flows use to service one packet in a set of all competing flows. The time-based fairness packet scheduling method, characterized in that it is defined as the ratio occupied by the channel occupancy time used to service the P. 9. The channel occupancy time GT (f) for each flow to be guaranteed is

Where F is a set of all flows present in the flow competition graph,

Is the packet size of flow f,

Is the packet size of flow i and

Is a data rate of the flow having the lowest data rate among the flows connected in the flow competition graph.

Images