KR101032604B1 - How to reserve data slots in a distributed TMD AAD network - Google Patents

Abstract

The present invention relates to a distributed TDMA Ad-hoc network, and more particularly, to a method for reserving data slots in a distributed TDMA Ad-hoc network in which slots are reserved to avoid data slot collisions and minimize routing overhead in an interference region. will be.
To this end, the present invention provides a data slot reservation method in a distributed time division multiple access (TDMA) ad-hoc network, in which a transmitting terminal selects a data slot by referring to its resource allocation table and transmits data through the selected data slot. The first step of transmitting a request message for the data slot reservation to the receiving terminal to which the transmission is to be transmitted, and if the receiving terminal receives the received data slot reservation request message, the transmitting terminal refers to its resource allocation table. A second process of transmitting a reservation response message to neighboring terminals located within a service area of the transmitting terminal and the receiving terminal if the selected data slot is available and available; and the transmitting terminal transmits the reservation response from the receiving terminal. When the message is received, a reservation confirmation message to the receiving terminal And a third process of transmitting to neighboring terminals located within a service area of the transmitting terminal, and neighboring terminals adjacent to the transmitting terminal and neighboring terminals adjacent to the receiving terminal respectively receive the reservation response message or the reservation confirmation message. And a fourth process of transmitting to terminals located within three hops.

Description

METHODO FOR SLOTS RESERVATION IN THE DISTRIBUTED TIME DIVISION MULTIPLE ACCESS AD-HOC NETWORK}

The present invention relates to a distributed TDMA Ad-hoc network, and more particularly, to a method for reserving data slots in a distributed TDMA Ad-hoc network in which slots are reserved to avoid data slot collisions and minimize routing overhead in an interference region. will be.

In general, unlike a cellular network consisting of a base station and a mobile terminal, Ad-hoc network has the advantage that can quickly establish a communication network without a separate infrastructure. However, in order to enable this, all media access control (MAC) and resource allocation processes should be autonomously between terminals and should be made to minimize collisions between frames during data transmission. To this end, conventionally, a method for enabling each terminal to sequentially use communication resources without collision through the Unifying Slot Assignment Protocol (USAP) has been proposed. USAP-MA (Multiple Access) is based on Time Division Multiple Access (TDMA) and has a structure in which fixed length frames are repeated at regular time intervals.

1 is an exemplary view showing a conventional TDMA frame structure.

As shown, the conventional TDMA frame structure is composed of three independent cycles: a bootstrap cycle (110), a broadcast cycle (120), and a reservation cycle (130). Each cycle consists of eight frames, each frame being 125 msec long. However, the length of each cycle and frame can be applied differently depending on the design. Each 125msec frame consists of a plurality of bootstrap mini slots (140), broadcast slots (150), and reservation / standby slots (160).

However, the prior art (USAP) has not proposed a collision resolution method in which nodes avoid a collision by redundantly reserving a specific slot in an interference region (3 times transmission distance; 3-hop). It simply prevents redundancy within the transmission distance, and the collided data packet is retransmitted to the next frame. Therefore, when the prior art is used in a multi-hop ad-hoc network, the higher the utilization, the more collisions occur.

In addition, it is difficult to efficiently transmit a broadcast message in the related art. The simplest way to implement a broadcast is by simple flooding. This is a method of retransmitting all messages received by all the neighboring terminals, which is relatively simple to implement but has a disadvantage of wasting radio resources. That is, in order to deliver a message to the entire network, as many transmissions as the total number of terminals are required. In order to solve this problem, in a protocol such as OLSR, a transmitting terminal designates some of 1-hop neighbor terminals as a multipoint relay (MPR), and reduces overhead by allowing only MPRs to participate in retransmission when a broadcast message is received. Presented. In order to select an MPR, each terminal needs to periodically share neighboring terminal information of each terminal with neighboring terminals. However, when such a control message is handled in the same manner as general data, a case in which the optimum MPR may not be selected due to a slow response due to a collision is caused.

Accordingly, the present invention provides a slot reservation method for minimizing the collision of data slots in the interference region of the Ad-hoc network in order to solve the above problems.

According to an aspect of the present invention, in the method for reserving a data slot in a distributed TDMA Ad-hoc network, a transmitting terminal selects a data slot by referring to its resource allocation table and selects the selected data. A first process of transmitting a request message for a data slot reservation to a receiving terminal to which data is to be transmitted through a slot; and when the received data slot reservation request message is received, the receiving terminal refers to its resource allocation table. A second process of transmitting a reservation response message to neighboring terminals located in a service area of the transmitting terminal and the receiving terminal if the data slot selected by the transmitting terminal is available and available; and the transmitting terminal is the receiving terminal. If the reservation response message is received from the The third process of transmitting to neighboring terminals located in the service area of the receiving terminal and the transmitting terminal, and neighboring terminals adjacent to the transmitting terminal and neighboring terminals adjacent to the receiving terminal are respectively received the reservation response message or the reservation. And transmitting a confirmation message to terminals located within three hops.

The present invention provides a frame structure of the distributed TDMA Ad-hoc MAC protocol reflecting hierarchical optimization with the routing protocol in the distributed TDMA MAC protocol, thereby reserving slots and transmitting data in a distributed manner, By avoiding collisions, the transmission performance can be improved, and OLSR Hello messages for routing can be transmitted without collisions in the Routing Information Broadcast (RIB) slot.

1 is an exemplary view showing a conventional TDMA frame structure.
2 is an exemplary diagram illustrating a TDMA frame structure according to an embodiment of the present invention.
3 is an exemplary view showing a Hello message frame structure according to an embodiment of the present invention.
4 is an exemplary view showing in detail the Hello field in the Hello message according to an embodiment of the present invention.
5 is an exemplary diagram illustrating a RAT message frame structure according to an embodiment of the present invention.
6 is an exemplary diagram showing an example of reserving a User Data slot according to an embodiment of the present invention.
7 is an exemplary diagram illustrating a network topology in which a collision occurs when a user data slot is reserved according to an embodiment of the present invention.

Hereinafter, with reference to the accompanying drawings will be described in detail the operating principle of the preferred embodiment of the present invention. In the following description of the present invention, detailed descriptions of well-known functions or configurations will be omitted if it is determined that the detailed description of the present invention may unnecessarily obscure the subject matter of the present invention. Terms to be described later are terms defined in consideration of functions in the present invention, and may be changed according to a user, a user's intention or custom. Therefore, the definition should be based on the contents throughout this specification.

The present invention proposes a slot reservation method for minimizing collision in the interference region. In addition, the present invention proposes a collision resolution method when a slot collision occurs.

That is, in the present invention, when a reservation response message and a reservation confirmation message are accidentally used with the same slot in the process of transmitting up to three hops, the collision terminals may assign a preemptive value by assigning some variables related to a collision occurrence situation to a predetermined equation. After that, we compare these values to indicate the final ownership for that slot.

2 is an exemplary diagram illustrating a TDMA frame structure according to an embodiment of the present invention.

As shown, the TDMA frame structure according to the embodiment of the present invention includes a Routing Information Broadcast (RIB) slot field 210, which is a section for transmitting an OLSR (Optimized Link State Routing) Hello message for routing, A slot information broadcast (SIB) slot field 220 for exchanging user data slot allocation information and performing reservation of user data slots, and a section of user data slots field 230 in which actual data is transmitted.

One RIB slot in RIB slots and one SIB slot in SIB slots are slots allocated to each mobile terminal, and the OLSR Hello message for routing is transmitted through the RIB slot and SIB slot allocated to the mobile terminal. The mobile terminals transmit and receive User Data by reserving User Data slots.

3 is an exemplary diagram illustrating a Hello message frame structure according to an embodiment of the present invention.

As shown, the Hello message frame structure according to an embodiment of the present invention is composed of a Type field 310, TX ID field 320, HELLO field 330, CRC field 340, Figure 2 Is transmitted through the RIB slot.

The Type field 310 is a frame type, and any one or more types of three types of HELLO, Resource Allocation Table (RAT), and DATA are recorded, and the TX ID field 320 is a terminal for transmitting a HELLO message frame. The ID, i.e., the identifier, is recorded, and the HELLO field 330 records the HELLO message. In addition, a cyclic redundancy check (CRC) field 340 is a field for checking an error in data transmitted through a communication link.

4 is an exemplary view showing in detail the Hello field in the Hello message according to an embodiment of the present invention.

As shown, the Hello field in the Hello message according to an embodiment of the present invention is a Reserved field 410 indicating that a slot has already been reserved, an Htime field 420 indicating a time interval at which the Hello message is generated, and the terminal is multi-pointed. Willingness field 430 indicating the willingness to perform as a relay (Multipoint Relay), and Neighbor List Map field 440 containing status information such as the hop count of neighboring terminals and the willingness to perform as a multipoint relay.

Such an OLSR Hello message structure according to an embodiment of the present invention is included in a Hello field in a Hello message.

5 is an exemplary diagram illustrating a RAT message frame structure according to an embodiment of the present invention.

As shown, a resource allocation table (RAT) message frame according to an embodiment of the present invention includes at least one RAT entry and an ACK map. The present invention transmits a resource reservation request message (RR) for requesting resource reservation of a user data slot through the RAT entry, or transmits an ACK (Resource Reservation Acknowledge, RA) for a resource reservation request. When receiving the ACK for the reservation request, in order to prevent a problem in which the hidden terminal is generated transmits a confirmation (Resource Reservation Confirm, RC). The hidden terminal is a terminal that has not received the reservation response message among the neighboring terminals of the terminal that has transmitted the resource reservation request message. The hidden terminal may duplicate a reserved slot and cause a collision. RAT RA, RC Entry is transmitted to the neighboring three hops to coordinate the transmission of data without collision between the terminals within the three hops.

Each terminal manages a resource allocation table (RAT) so as to know resource usage states of itself and neighboring terminals. Based on resource allocation information received from neighboring terminals, the RAT is updated to maintain the latest information. When sending a RAT RR or sending a RAT RA after receiving a RAT RR, a reservation is attempted for a slot other than the slot used in the RAT.

The ACK information about the received data is expressed as a bitmap and transmitted. Set the bit value of the successful slot to '1'. The bit value of the slot that failed to receive or does not receive data is set to '0'.

The RAT message frame includes a Type field 510, a TX ID field 520, a RAT Entry 1 field 530, a RAT Entry n field 540, an ACK map field 550, and a CRC field 560. There may be n RAT Entry fields in the RAT message.

The Type field is a frame type, and there are three types of types: HELLO, RAT, and DATA. In addition, the TX ID field indicates an identifier (ID) of the terminal transmitting the RAT message frame, and there may be fewer or more than n RAT entries. The ACK map field indicates an acknowledgment map for the received data, and the CRC field is a field for checking an error in data transmitted through the communication link.

Each RAT entry includes a TX ID field 531, an RX ID field 532, a Type field 533, a Traffic Type field 534, a Channel field 535, a Sub-frame Index field 536, and a Sub. A frame Allocation Map field 537 and a Number of Frames field 538 are included.

The TX ID field indicates an ID of a terminal transmitting a data packet using a corresponding user data slot, and the RX ID field indicates an ID of a terminal receiving a data packet. The Type field indicates a RAT message frame type. These types include Resource Request (RR), Resource ACK (RA), Resource Confirm (RC), and Resource Update (RU). That is, when the RAT message type transmitted from the transmitting terminal to the receiving terminal is a resource request or resource confirmation, the TX ID field 520 in the RAT message frame and the TX ID field 531 in the RAT entry include IDs of the same transmitting terminal. On the other hand, when the RAT message type sent by the transmitting terminal to the receiving terminal is a resource response, the TX ID field 510 in the RAT message frame and the RX ID field 532 in the RAT entry include the ID of the same transmitting terminal. This is because two terminals transmit and receive each other.

In addition, the Traffic Type field indicates VoIP, video, image, ftp, etc., the Channel field indicates a channel ID for multi-channel transmission, and the Sub-frame Index field indicates which sub-frame of the user data slots is used. The Sub-frame Allocation Map field indicates the bit slot used in the sub-frame as a bit map. In addition, the Number of Frames field indicates the period using the corresponding slot in the number of frames.

3) User Data Slot

The user data slot section 230 is a section in which real data is exchanged based on a reservation made in the SIB slot 220 section. The user data slot section consists of a plurality of subframes, and one subframe consists of a plurality of slots.

Among the plurality of subframes, the terminal is allocated slots of some subframes and transmits and receives data packets through the assigned slots.

A terminal according to the present invention can reserve several slots and several channels over several subframes with one reservation. When reserving a large number of slots over several subframes in order to increase the transmission rate in an image or FTP, a restriction is made to increase the transmission rate slowly rather than rapidly to prevent the starvation of other traffic. Since multicasting, broadcasting, or short message transmission has a higher priority than other traffics, in some cases, best effort traffic may occupy a reserved slot.

If there is no empty slot at the time of reservation, best-effort traffic allows slots that have already been reserved to be used through redundant reservation for higher priority traffic. To this end, the transmitting terminal selects to occupy the largest number of slots in the entire user data slot interval among the best effort traffic by referring to its own RAT, and has the lowest number of frames among the subframes used in the corresponding traffic. It is possible to reserve the slots of the remaining subframes.

In addition, when reserving real-time data such as voice or multimedia data, the transmitting node reserves slots to be used by the relay terminal on the transmission path so that transmission can be performed while minimizing delay due to the relay terminal up to 3 hops.

The resource allocation table (RAT) is a table used by a terminal to reserve a data slot. The resource allocation table (RAT) includes a data slot allocated to the terminal or a data slot reserved by the terminal. .

6 is an exemplary diagram illustrating an example of reserving a user data slot according to an embodiment of the present invention.

The SIB slot according to an embodiment of the present invention performs an operation of reserving a user data slot to transmit data. Each terminal transmits a RAT message for reservation in its own SIB slot to a neighboring terminal, as if the terminal is previously allocated an RIB slot.

As shown, the process of reserving a user data slot according to an embodiment of the present invention will be described as follows. The numbers shown in FIG. 6 indicate that each process is performed sequentially.

In step ①, the transmitting terminal S selects an idle slot with reference to its resource allocation table (RAT) to reserve a user data slot, and then requests a resource allocation table reservation (Resource Allocation Table). The reservation request (RAT RR) message is transmitted to the receiving terminal to transmit the intention to the receiving terminal (R).

Upon receiving the resource allocation table reservation request message in step ②, the terminal checks whether the slot selected by the transmitting terminal is available by referring to the resource allocation table owned by the terminal. In addition, the available slot is expressed in a bitmap to transmit a resource allocation table reservation response message to inform the transmitting terminal and the neighboring terminals of the reservation. The neighboring terminals are terminals existing in a service area of a receiving terminal, and at least one neighboring terminal may exist.

In step ③, when the transmitting terminal receives a Resource Allocation Table Reservation Acknowledgment (RAT RA) message from the receiving terminal, a hidden terminal is generated to prevent a hidden terminal from occurring. A Resource Allocation Table Reservation Confirm (RAT RC) message is broadcast to neighboring terminals. The hidden terminal is a terminal that has not received the reservation response message of step 2 among neighboring terminals of the transmitting terminal S, and may cause interference by using a slot reserved by the hidden terminal. If the transmitting terminal does not receive the resource allocation table reservation response message, it retransmits the reservation request message after a predefined time interval (RATTimeOut), and the maximum number of such retransmissions is limited to a certain number of times.

In step ④, the neighboring terminals of the transmitting terminal and the receiving terminal float up to 3 hops of the RAT RA and RAT RC messages to prevent the same slot from being selected in the interference region. In this case, overhead may be reduced by floating only the MPR terminal among neighboring terminals. The neighboring terminals receiving the RAT RA and the RAT RC message may update their RAT with reference to the RAT message to reserve a User Data slot.

In order to reserve User Data slots through this process, each terminal attempts to avoid User Data slots already reserved by other terminals with reference to RAT when reserving User Data slots. . If the terminals located where it is difficult to immediately update the RAT because they are more than three hops away from each other, a collision occurs because the other terminal does not know which User Data slot is being used. However, even if the terminals are located within three hops, the same User Data slot may be reserved by chance while the RAT message is transmitted up to three hops. In case of such a collision, the RAT message is transmitted up to three hops and then the collision can be recognized. The collision terminals obtain a preemption value by substituting some variables related to the collision situation into a predetermined equation, and compare the values to indicate the final ownership of the slot.

When the presence of another terminal using the same slot is found through RAT exchange, first, a preemption value of the other terminal is obtained. The preemption value is a value for knowing which of the terminals to use the data slot has a priority. At this time, the information necessary for the calculation is already obtained through the RAT exchange. Comparing the calculated results, as long as the terminal has the largest preemption value, the terminal has the right to continue using the user data slot in which the collision occurs. The remaining terminals do not use the corresponding slot any more, and attempt to reserve the User Data slot in the SIB slot section in the next frame.

Conflict resolution using preemption value can be implemented by simple operation without exchanging additional control message to solve the problem in case of conflict already. In addition, all values necessary for calculating the preemption value can be obtained through the RAT message exchange, and since the RAT message is transmitted to each terminal in a predefined slot in the frame, no additional overhead is caused.

Hereinafter, a process of calculating the preemption value according to the present invention will be described.

The method of calculating the preemption value can have various expressions depending on the method of determining the priority. Equation 1 below is an example of an equation for calculating a preemption value, and determines priority based on priority and class.

Priority represents a priority according to traffic type, class represents a priority of a terminal, and ID is a variable representing an identifier capable of uniquely identifying a terminal in the entire network. In other words, the class variable has a different value according to the level of the group to which the terminal belongs, that is, in the case of military service, since the battalion commander has a higher level than the platoon commander level, the class corresponds to the battalion commander than the class corresponding to the platoon commander. class is bigger In addition, the priority variable is a value that specifies a priority differently according to a packet type for transmitting and receiving terminals belonging to the same class. That is, among the terminals belonging to the same platoon level, one terminal transmits and receives a packet as a data packet, while the other terminal transmits and receives a packet as a voice packet. Variables also have high values. T_collision is defined as the time offset from the start point of the frame to the first User Data slot where duplicate reservation is made. This serves to prevent a case where a specific terminal always has a high preempt value V_pre compared to other terminals in a collision situation. The & symbol represents a bit-level concatenation operation. 2 & 2 means 22. The% symbol represents a remainder operator, and n represents the number of terminals constituting the entire network. Hereinafter, a process for resolving collision in the Ad-hoc network will be described in FIG. 6.

7 is a diagram illustrating a network topology in which a collision occurs when a user data slot is reserved according to an embodiment of the present invention.

Hereinafter, a method of solving a problem in which a collision occurs when reserving a user data slot according to an embodiment of the present invention will be described in detail with reference to FIG. 7.

It is assumed that terminal 1 has data to send to terminal 3 and terminal 8 has data to send to terminal 4. In order to minimize the end-to-end time delay, it is assumed that the transmitting terminal reserves the time slots consumed by each hop at once, and this is the same time slot by chance. In this case, it can be seen that the transmission transmitted from the terminal 5 to the terminal 4 collides with the transmission transmitted from the terminal 1 to the terminal 2 in the terminal 2 and thus the terminal 2 acts as a hidden terminal. Terminals 1 and 8 are more than three hops away, so it is not immediately known that the collision. When the RAT starts to be delivered in the next frame, the UE 5 knows that there is traffic from 1 to 3, and knows that this causes a collision with the traffic it is relaying. RATs containing collision information of two traffics are delivered to terminal 1 through terminal 2 and to terminal 8 through 8 in the next frame, respectively, and terminals 1 and 8 use the preemptive value calculated using the collision-related variables found through the RAT. As a result of the comparison, the larger one has a right to use that time slot.

That is, as shown, when the reservation request transmitted from the terminal 1 to the terminal 3 and the reservation request transmitted from the terminal 8 to the terminal 4 are simultaneously transmitted, when the first frame and the second frame are transmitted, the terminal 1 and 8 are In the transmission and reception process, it is known that collisions occur with each other, and the preemption value is calculated.

The preemption value V_pre can be obtained as follows. For example, it is assumed that the ID of the terminal 1 is 84535, the ID of the terminal 8 is 15843, and the priority of each terminal is equal to 3. It is assumed that the total number of terminals n is 8.

V_pre (node1) = 3 & 3 & ((84535 + 100)% 8) & 84535 = 33384535

V_pre (node8) = 3 & 3 & ((15843 + 100)% 8) & 15843 = 33715843

Since V_pre (node1) <V_pre (node8), UE 8 uses the corresponding time slot and UE 1 needs to reserve another time slot.

While the invention has been shown and described with reference to certain preferred embodiments thereof, it will be understood by those skilled in the art that various changes and modifications may be made without departing from the spirit and scope of the invention. Therefore, the scope of the present invention should not be limited to the described embodiments, but should be determined not only by the scope of the following claims, but also by the equivalents of the claims.

Claims (8)

A data slot reservation method in a distributed time division multiple access (TDMA) ad-hoc network,
A first process of the transmitting terminal selecting a data slot with reference to its resource allocation table and transmitting a request message for reserving a data slot to a receiving terminal to which data is to be transmitted through the selected data slot;
When the received data slot reservation request message is received, the receiving terminal checks whether a data slot selected by the transmitting terminal is available by referring to its resource allocation table, and if available, sends a reservation response message to the transmitting terminal and the receiving terminal. A second process of transmitting to neighboring terminals located within a service area of the terminal;
A third step of transmitting, by the transmitting terminal, a reservation confirmation message to neighboring terminals located within a service area of the receiving terminal and the transmitting terminal when the reservation response message is received from the receiving terminal;
Neighboring terminals adjacent to the transmitting terminal and neighboring terminals adjacent to the receiving terminal each include a fourth process of transmitting the received reservation response message or the reservation confirmation message to terminals located within three hops,
And each of the transmitting terminal and the receiving terminal calculates a preemption value for using the data slot.
The method of claim 1, wherein the resource allocation table
The data slot reservation method in a distributed TDMA Ad-hoc network including a data slot allocated to each terminal, or a data slot reserved by each terminal in order for a plurality of terminals existing in the Ad-hoc network to reserve a data slot.
The method of claim 1, wherein each neighboring terminal receiving the reservation response message and the reservation confirmation message further updates its resource allocation table.
The data of the distributed TDMA Ad-hoc network of claim 1, further comprising retransmitting the reservation request message after a predefined time interval if the transmitting terminal does not receive the reservation response message from the receiving terminal. How to reserve a slot.
The method according to claim 1,
A fifth process of transmitting, by the receiving terminal, a slot information broadcast message of a next frame to the transmitting terminal if the data slot selected by the transmitting terminal is not available;
The transmitting terminal further comprises a sixth step of transmitting a slot information broadcasting message of a next frame to the receiving terminal when the received slot information broadcasting message is received.
delete The method of claim 1, wherein the preemption value is
A method for reserving data slots in a distributed TDMA Ad-hoc network, characterized in that it is a value for knowing which of the terminals to use the data slot has a priority.
The method of claim 7, wherein the preemption value is calculated through Equation 2 below.
&Quot; (2) &quot;
V_pre = priority & class & ((ID + T_collision)% n)% ID
In Equation 2, class represents a level value of a group to which a terminal belongs, priority represents a priority according to a traffic type among terminals in the same group, ID represents a terminal identifier, and T_collision represents a frame of a transmitted frame. Represents a time offset to the first User Data slot in which duplicate reservation is made based on a starting point, n denotes the number of terminals existing in the Ad-hoc network, and & denotes a bit-level concatenation operation. And% represents the remainder of the operation.

Images