KR101386835B1 - Multihop transmission method for increasing node's lifetime in wireless Ad Hoc network - Google Patents

Abstract

In the present invention, when performing multi-hop transmission between terminals in a wireless ad hoc environment, a transmission path is configured to terminals having long survival time, resources are allocated to guarantee end-to-end rate and QoS conditions, and PSM is applied. Multi-hop for reducing the transmission power consumption of the terminal and solving this through TPC, rescheduling, and rerouting in case of interference and collision, thereby increasing multi-hop transmission QoS and lifetime. To provide a transmission method.
To this end, the present invention, a multi-hop transmission method in a wireless ad hoc network, the routing step of performing a routing to determine the multi-hop transmission path; A scheduling step of performing scheduling for the determined multi-hop transmission path and allocating transmission resources for each multi-hop link; Transmitting data and control information for multi-hop transmission using a result of performing the scheduling, and operating in a power saving mode (PSM); And an interference control step of controlling interference by performing transmission power control (TPC), rescheduling, or rerouting as a collision occurs during multi-hop data transmission or the amount of interference exceeds a first threshold. In the routing step, the multi-hop transmission path is determined using a routing cost in consideration of power consumption rate and energy remaining amount of each node.

Description

Multihop transmission method for increasing node's lifetime in wireless Ad Hoc network

The present invention relates to a multi-hop transmission method for guaranteeing quality-of-service (QoS) and maximizing the lifetime of a transmission path in a wireless ad hoc network. Routing technology that finds a path that maximizes the survival time of transmission path while guaranteeing end-to-end quality of service in multi-hop transmission, scheduling technology that allocates transmission resources in consideration of transmission rate per link, and power consumption of UE Power Saving Mode (PSM) control technology to reduce power consumption, and Transmit Power Control (TPC), rescheduling and rerouting technology to resolve interference and collisions during transmission It relates to a multi-hop transmission method comprising a.

The ad hoc network is a technology in which nodes (a node and a terminal are used in the same sense) in the environment without an infrastructure dynamically construct a self-communication network to communicate directly between nodes. In order to transmit data from a source node to a destination node through an ad hoc network, multi-hop communication is required between the source node and the destination node. For multi-hop transmission that delivers data through multiple nodes, routing to find the transmission path and scheduling to allocate transmission resources are performed. In general, PSM operation is performed to reduce power consumption of a battery-powered node.

In the ad hoc network, various routing schemes have been proposed. Generally, a shortest path routing scheme for reducing the number of multihop transmission hops is used. Various algorithms and operating protocols have been proposed. In addition, power-aware routing schemes have been proposed for the purpose of increasing the lifetime of the network in consideration of power consumption and energy remaining of the terminal. However, the existing routing methods do not present a specific algorithm for a method of simultaneously considering the power consumption rate of the terminal and the remaining battery capacity of the terminal according to the state of the transmission link. Considering bays, the battery survival time is determined and the transmission path is determined using the same.

Ad-hoc scheduling scheme is to guarantee end-to-end QoS by allocating resource amount to be used for each transport link constituting multi-hop. In general, in order to reduce scheduling overhead in a complex ad hoc network environment, many carrier Sense Multiple Access / Collision Avoidance (CSMA / CA) schemes have been used in which transmission terminals use resources in a competitive manner without a separate resource allocation process. However, in order to prevent collisions and increase resource usage efficiency, scheduling schemes for allocating dedicated resources for each transmission link have been studied. It allocates limited radio resources for each link for the purpose of guaranteeing end-to-end QoS and increasing transmission rate. However, the conventional scheduling method simply allocates different resources to each link so that they do not overlap, and there is a problem in that resource utilization efficiency decreases because links with less interference cannot use resources at the same time. In addition, there is a problem that a specific algorithm for how much resources to allocate to maximize the end-to-end transmission rate is not presented.

In addition, a transmit power control (TPC) algorithm for controlling the transmit power of a terminal has been proposed as a method for reducing mutual interference and reducing power consumption of a terminal between multi-hop links. Here, the TPC is a method of controlling the transmission power according to the link quality formed between the transmission and reception terminals. If the link quality is good, the TPC can provide a desired transmission rate even with a small transmission power. If the quality is bad, increase the transmit power. The operation of the TPC can increase the battery survival time of the terminal by reducing the inter-link interference and lowering the transmission power of the terminal. However, the conventional TPC algorithm decides the transmission power to satisfy the required Signal to Interference-plus-Noise Ratio (SINR) value, and determines the transmission power only by considering its link quality. There is a problem that does not reduce its transmission power in consideration of interference. Thus, interference exists between links on the same transmission path, resulting in a drop in the end-to-end transmission rate.

The power saving mode (PSM) is a method of reducing power consumption by turning off a transmission / reception module when the terminal does not transmit or receive data. For this purpose, a transmission and reception period between the transmission and reception terminals and a sleep mode are turned off. ), And wake up and sleep periodically. The terminal transmits and receives data only in the wake mode, and reduces power consumption by turning off the transmit / receive power in the sleep mode. The IEEE 802.11 standard defines a PSM scheme that operates in Ad Hoc mode. However, the PSM method of the IEEE 802.11 ad hoc mode determines wake and sleep at intervals of a superframe interval, and wakes up within a frame even when only one small packet is transmitted. It follows a simple way of maintaining state. As a result, there is a problem in that a section in which sleep can be reduced is not obtained to obtain a sufficient power saving effect.

It is therefore an object of the present invention to solve the problems of the prior art as described above.

Therefore, in the present invention, when performing multi-hop transmission between terminals in a wireless ad hoc environment, a transmission path is configured with terminals having long survival time, resources are allocated to guarantee end-to-end transmission rate and QoS conditions, and PSM is used. By reducing the transmission power consumption of the terminal and solving this through TPC, rescheduling, and rerouting in case of interference and collision, multi-hop transmission QoS guarantee and multiplication for increasing the lifetime The purpose is to provide a hop transmission method.

In other words, unlike the conventional routing method in which the power consumption and energy remaining of the terminal are simply considered, the routing method of the present invention calculates a routing cost in consideration of the power consumption for each link transmission and reception and the remaining battery capacity of the terminal. By using this, it is possible to select a transmission path with a long survival time.

In addition, unlike the conventional scheduling method of allocating different orthogonal resources for each link, the scheduling method of the present invention increases the resource reuse rate by scheduling the same resource to be used simultaneously between the links without interference. Therefore, each link can be allocated a larger amount of resources, thereby increasing the end-to-end transfer rate. In addition, each resource amount allocated to each simultaneous transmission link is determined to ensure end-to-end QoS.

In addition, in the present invention, unlike the conventional method of determining wake and sleep by a fixed unit of time when PSM is applied, the device wakes only during the time of data transmission and reception and sleeps during the rest of the time. Sleep) to minimize the power consumption of the terminal.

In addition, the present invention solves the problem by lowering the transmission power of the terminal interferes through the TPC when interference and collision occurs. Unlike the conventional TPC based on only the link quality transmitted by the UE, the present invention solves the problem of simultaneous transmission link interference and guarantees the end-to-end transmission rate through the TPC. In addition, if the interference problem is not solved by the TPC method, a rescheduling or rerouting method is additionally applied to solve the interference and collision problem that may occur during multi-hop transmission.

The objects of the present invention are not limited to the above-mentioned objects, and other objects and advantages of the present invention which are not mentioned can be understood by the following description, and will be more clearly understood by the embodiments of the present invention. It will also be readily apparent that the objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.

According to an aspect of the present invention, there is provided a method of multihop transmission in a wireless ad hoc network, the method comprising: routing to determine a multihop transmission path by performing routing; A scheduling step of performing scheduling for the determined multi-hop transmission path and allocating transmission resources for each multi-hop link; Transmitting data and control information for multi-hop transmission using a result of performing the scheduling, and operating in a power saving mode (PSM); And an interference control step of controlling interference by performing transmission power control (TPC), rescheduling, or rerouting as a collision occurs during the multi-hop data transmission or the amount of interference exceeds the first threshold. . In this case, the routing step determines a multi-hop transmission path using a routing cost in consideration of the power consumption rate and the remaining energy of each node. The scheduling may include allocating the same transmission resources to two or more transmission links within the limit of no interference between the multi-hop links, and considering orthogonal number of resources used in consideration of the amount of interference generated between simultaneous transmitting nodes. Determine the resource usage according to the link transmission rate. The power saving mode (PSM) operation is performed by turning off a transmission / reception module and switching to a sleep mode during a period of no transmission / reception during multi-hop transmission. In the interference control step, when a collision occurs during multi-hop data transmission or the amount of interference exceeds the first threshold, a TPC operation is performed to remove interference and resume transmission, or TPC is performed. If it is not possible to solve the problem, perform rescheduling and resume transmission. If the problem cannot be solved even by performing TPC or rescheduling, rerouting is performed and the scheduling step is performed.

The present invention as described above, when performing the multi-hop transmission between the terminals in a wireless ad hoc environment, configures the transmission path to the long survival time terminal, and allocates resources (scheduling) to ensure the end-to-end rate and QoS conditions In order to reduce the transmit power consumption of UE by applying PSM and to solve this problem through TPC, rescheduling, and rerouting in case of interference and collision, multi-hop transmission QoS is guaranteed and lifetime is increased. It can be effected.

That is, the routing scheme proposed by the present invention uses the routing cost in consideration of the power consumption rate and the remaining battery capacity of the terminal to allow the long-lived terminals to participate in the multi-hop transmission, thereby improving the survival time of the multi-hop full path. There is an effect that can be increased.

In addition, the scheduling scheme proposed by the present invention increases the reuse rate of limited radio resources and determines resource usage according to link transmission rate, thereby increasing multi-hop end-to-end transmission rate and guaranteeing QoS.

In addition, the PSM method proposed in the present invention operates in a sleep mode during a period in which there is no transmission / reception during multi-hop transmission, thereby reducing power consumption of the terminal and thereby increasing lifetime of the multi-hop path. It works.

In addition, the TPC, rescheduling, and rerouting schemes proposed by the present invention can eliminate collisions and interferences in a short time by using a method of reducing transmission power or reallocating resources when interferences and collisions occur. By determining the worst node that is a transmission problem and performing routing again based on this, the interference is eliminated and the transmission is resumed, thereby ensuring the multi-hop end-to-end rate and QoS.

1 is a flowchart illustrating a multi-hop transmission method for increasing node survival time in a wireless ad hoc network according to the present invention;
2 is an exemplary diagram for setting a path in an ad hoc network environment;
FIG. 3 is a detailed flowchart of an embodiment of a routing operation using a routing cost according to the present invention; FIG.
4 is a diagram illustrating an embodiment of a multi-hop scheduling method (when transmitting 6 hops) according to the present invention;
5 is a diagram for explaining an embodiment of a method of determining the number of used resources (N) according to the present invention;
6 is a diagram illustrating an embodiment of a case where resource usage time according to the present invention is equally allocated (when six hops are transmitted).
7 is a diagram for explaining an embodiment of an operation of a transmit power control (TPC) according to the present invention;
8 is a diagram illustrating an embodiment of a rescheduling operation process according to the present invention;
9 is a diagram illustrating an embodiment of a determination condition of a worst node according to the present invention;
10 is a diagram for explaining an embodiment of removing a worst node;
11 is a diagram for explaining an embodiment of replacing a worst node;
12 is a diagram for explaining an embodiment of adding a new node around a worst node;
FIG. 13 shows an example of a transmission framework in an ad hoc mode of the IEEE 802.11 protocol. FIG.
14 is a structural diagram of an embodiment of a multi-hop transmission framework (in case of resource allocation of different sizes) according to the present invention based on the IEEE 802.11 protocol;
15 is a structural diagram of an embodiment of a multi-hop transmission framework (in the case of resource allocation of the same size) according to the present invention based on the IEEE 802.11 protocol;
16 is a diagram illustrating an embodiment of a multihop TPC operation process according to the present invention based on the IEEE 802.11 protocol;
17 is a diagram illustrating an embodiment of a multi-hop rescheduling operation process according to the present invention based on the IEEE 802.11 protocol;
18 shows an example of a result of comparing total power consumption (when demand rate = 100 Kbps).
19 shows an example of a result of comparing total power consumption (when demand rate = 1 Mbps);
20 is an exemplary diagram of an Outage Probability comparison result (when request rate = 100 Kbps).
21 is an example of an Outage Probability comparison result (when request rate = 1 Mbps),
22 is an exemplary view of the results of comparing the lifetime.

BRIEF DESCRIPTION OF THE DRAWINGS The above and other objects, features and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings, It can be easily carried out. In the following description, well-known functions or constructions are not described in detail since they would obscure the invention in unnecessary detail.

And throughout the specification, when a part is referred to as being "connected" to another part, it includes not only "directly connected" but also "electrically connected" with another part in between. Also, when a component is referred to as " comprising "or" comprising ", it does not exclude other components unless specifically stated to the contrary .

Hereinafter, preferred embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1. The whole operation process

The multi-hop transmission method according to the present invention includes a routing, scheduling, data transmission, and PSM operation process for multi-hop data transmission in a wireless ad hoc network. This includes scheduling and rerouting.

1 is a flowchart illustrating a multi-hop transmission method for increasing node survival time in a wireless ad hoc network according to the present invention.

First, routing is initially performed to determine a multihop transmission path (11). That is, the routing method may increase the survival time of the multi-hop entire path by allowing the long-lived terminals to participate in the multi-hop transmission by using a routing cost in consideration of the power consumption rate and the energy remaining of the terminal.

In other words, in order to increase the survival time of multi-hop transmission, routing is performed in consideration of the energy remaining amount and power consumption rate of the terminal. Each terminal has a different battery level, and the power consumption rate during transmission and reception varies according to the quality of a link connected to the terminal. When the routing is performed by applying the routing cost proposed in the present invention, a transmission path having a maximum lifetime can be provided.

Thereafter, scheduling is performed for each multi-hop transmission path to allocate transmission resources for each multi-hop link (12). That is, scheduling of transmission is performed by determining a resource amount and related parameters required for multi-hop transmission and setting related control information for the corresponding transmission path.

In other words, the scheduling scheme improves the reuse rate of limited radio resources by allocating the same resources to two or more transmission links within the limit of no interference between the multi-hop links, and determines the number of orthogonal resources used. In addition, by determining the resource usage according to the link transmission rate (determining the orthogonal resource size allocated in consideration of the transmission rate per link), it is possible to increase the multi-hop end-to-end transmission rate and guarantee the QoS. It will be described later in detail with reference to 6.)

Thereafter, data and control information for multi-hop transmission are transmitted using the scheduling result (scheduled information and resources), and when there is no transmission / reception, a PSM operation of transitioning to a sleep mode is performed (13). As such, the PSM method operates by turning off a transceiver module and switching to a sleep mode during a period when there is no transmission / reception during multi-hop transmission, thereby reducing power consumption of the terminal and thereby increasing the lifetime of the multi-hop path. (The specific operation method will be described later in detail with reference to FIGS. 4 and 6.)

If a collision occurs during multi-hop data transmission or the amount of interference exceeds a threshold (14), if resolution is possible through the TPC first (for example, if the collision occurs and the threshold exceeded the amount of interference is solved by the TPC). Perform the TPC operation to remove the interference (15), and if the collision still occurs or the amount of interference exceeds the threshold despite the TPC is applied (16), rescheduling is performed to remove the interference (17). If resolution is not possible with both methods (for example, if a collision still occurs or the amount of interference exceeds a threshold after performing TPC or rescheduling) (18), rerouting is performed and the scheduling process is performed. Repeated from (12) (19).

That is, when collision and interference occur during data transmission due to the movement of the terminal and the change in the channel environment, the TPC is performed to lower the transmission power of the interfering terminal or perform rescheduling (rescheduling). Redistribution of resources eliminates collisions and interference, or determines the worst node that is a problem in transmission, and reroutes based on this to eliminate interference and quickly resume transmission. A detailed operation method will be described later in detail with reference to FIGS. 7 to 12.

2. Routing Operation Process

2 is a diagram illustrating an example of routing in an ad hoc network environment.

Routing is to establish an intermediate transmission path between a source node (Src) and a destination node (Dst) in an ad hoc network environment as shown in FIG. The routing scheme according to the present invention selects an intermediate node for the purpose of maximizing the lifetime of the established transmission path. Here, the survival time of the transmission path is defined as the time taken for one or more links to be disconnected due to the exhaustion of the battery of one or more nodes on the path and thus the multihop transmission becomes impossible.

2-1. Routing Cost Determination Method

When designing routing costs, first consider the battery lifetime of each transmitting node. The battery survival time is related to the amount of energy that a node uses for receiving / transmitting and thus is determined by the amount of power used for receiving / transmitting each node and the receiving / transmitting time.

At this time, the routing cost C _j is determined as follows.

Receiving time (T _j ^rx ) and transmission time (T _j ^tx ) required when relaying data of size D _req to the next node in any intermediate node j of FIG. 2 are represented by Equation 1 below. Calculated as

Where R _ij represents a possible data rate when transmitting data from node i to node j. Therefore, the reception and transmission energy consumed when delivering the data of the size D _req in the intermediate node j is calculated as shown in Equation 2 below.

Here, P _rx and P _tx represent the amount of power (Watt unit) required for the communication node to receive and transmit per unit time, respectively. Therefore, the total amount of energy consumed when the intermediate node j is included in the routing path and participates in data transmission is determined as shown in Equation 3 using Equations 1 and 2 above.

In this case, when the remaining energy amount of the intermediate node j is called E _j , when the intermediate node j participates in the multi-hop transmission, the lifetime of the intermediate node j is calculated as shown in Equation 4 below.

Therefore, the routing cost according to the present invention is determined as the inverse of the lifetime, and is given by Equation 5 below (ie, the larger the survival time value of the node, the lower the routing cost).

In addition, the following constraints may be included in addition to the above-described routing cost calculation formula.

That is, when the energy remaining of any intermediate node j is smaller than the predetermined threshold or the transmission rate between the two nodes a and b is smaller than the predetermined threshold, the routing cost is set to infinity and the corresponding intermediate node j May not be included in the path.

2-2. Routing Behavior Procedure

In order to determine a routing cost, any node j needs rate information (R _ij , R _jk ) and current energy amount (E _j ) information of links connected to it. In order to collect such information, each node periodically or at the time of a request event occurs, has rate information (or rate-to-signal information with signal-to-interference-plus-noise ratio (SINR) and signal-to-noise ratio (SNR)). to noise ratio, channel quality, etc.) can be measured, stored, updated, and shared. In addition, each node can measure / store / update / share information on its current remaining energy amount periodically or when a request event occurs.

Routing cost according to the present invention can be applied to existing routing protocols (Optimized Link State Routing (OLSR), Dynamic Source Routing (DSR), Ad-Hoc On-Demand Distance Vector (AODV), etc.) Do. That is, the route information is exchanged between the transmitting node and the destination node by using the new routing cost value proposed by the present invention instead of the routing cost used in the existing routing protocol. When routing cost information is obtained between transmission-destination nodes using the selected routing protocol, final path determination may be determined according to the following equation (7).

That is, the path having the smallest value of the routing cost may be selected or the path having the smallest sum of the total costs may be finally selected. The final determination of the path is possible if the routing cost information is available at either the sending node or the destination node.

3 is a detailed flowchart illustrating a routing operation process using a routing cost according to the present invention, and illustrates an operation process based on a dynamic source routing (DSR) protocol using a routing cost. .

First, a source Src node broadcasts a Route Request packet to find a transmission path to a destination Dst node. The route request packet includes path information, rate information, and energy remaining information. The source node first broadcasts the route request packet including only its ID as path information.

Then, the node receiving the broadcast route request packet adds its ID to the path information, adds the link rate value calculated using the link quality information measured while receiving the packet, to the rate information, Add the remaining energy to the remaining energy information. Thereafter, the route request packet including the added information is broadcast again.

In this way, each node adds each piece of information and forwards the route request packet to all network nodes, and the destination node that receives the route request packet finally gets the best path based on the received route request information. (You can also forward the received information to the source node so that the source node selects the final path.)

방식에 따라 결정할 수 있다.That is, the destination node determines the final path with the information of the Route Request packets received for a predetermined time without broadcasting the route request packet. Final path determination method described above

It can be decided according to the method.

As such, when the destination node determines the final path, a route response packet is transmitted to the source node including the path information and the link rate information of the determined path. At this time, the route response packet is delivered to the source node via the corresponding path using the determined final path information.

3. Scheduling Operation Process

When the transmission path is determined by the routing operation, resources required for transmission must be allocated for each connected multihop link. This section describes the scheduling method for this.

4 is a diagram illustrating an embodiment of a multi-hop scheduling method according to the present invention, which shows a multi-hop scheduling method when the number of transmission hops is 6 (the number of nodes is 7).

Basically, to increase the reuse rate of resources, schedule the transmission using the same resources between non-interfering links. For example, when it is determined that there is little interference between each other, transmission from node 1 to 2 and transmission from node 4 to 5 are simultaneously performed. However, since the transmission from node 1 to 2 is impossible at the same time, the transmission from node 2 to node 3 cannot be performed at the same time, and the transmission from node 3 to node 2 and node 3 due to direct interference from node 3 to node 2 are not possible. → 4 cannot be transmitted at the same time. As a result, as illustrated in FIG. 4, transmissions may be performed using the same resources at the same time between links at least two hops apart. As described above, when performing multi-hop scheduling considering simultaneous transmission, it is important to determine the number of resources allocated orthogonally to each other, and this depends on the amount of interference generated between simultaneous transmission terminals. Using the allocated resources, each terminal performs multi-hop transmission in a predetermined order. At the same time, each node performs a PSM operation that reduces power consumption by turning off the transmit / receive module and turning it into sleep mode when it is not transmitting or receiving.

3-1. How to determine the number of resources used (N)

4 illustrates the case of using three orthogonal resources for 6-hop transmission. In order to determine the number of orthogonal resources to be used, the amount of interlink interference transmitted simultaneously according to the number of transmission hops should be considered. First, a control packet (ie, a hello or beacon message) for mutual interference measurement between nodes existing on a predetermined routing path is transmitted. The arbitrary node j determines the neighbor node set that interferes with itself according to the received signal strength or message decoding as shown in Equation 8 below.

In other words, if a received signal strength (RSS) value received from node y is greater than a predetermined threshold or a message transmitted by node y can be decoded, a node set interfering with node y to me Will be added to With the determined interference node set Y, each node j determines the interference hop number R _j as shown in Equation 9 below.

The number of interference hops indicates the maximum number of hops to the node that interferes with me, which can be determined as the maximum value of the difference between the sequence number of the node belonging to the set of my interference nodes and my sequence number. In general, as illustrated in FIG. 4, the value of the used resource number N may be determined as the maximum interference hop number of all nodes on the transmission path + 2. This is because at least two must be added to reduce the mutual interference effect during transmission. Therefore, the value of the used resource number N may be determined as shown in Equation 10 below.

If the interference tolerance is lower, use a value greater than 2.

5 is a diagram illustrating an embodiment of a method of determining the number of used resources N according to the present invention.

First, each severity broadcasts a Hello message at any time, and the neighboring nodes receive it to determine the interfering node set Y respectively. Since all transmitting nodes on the multi-hop path have completed this process, the interference node set Y _j and the interference hop number R _j can be known.

After completing the above process, the destination node sends a response message to the source node, and includes the maximum R _j value in the message. Each node receiving the response message informs the source node of the maximum R _j value by comparing the R _j value included in the response message with my R _j value and inserting a larger value.

A method of determining the number N of used resources without a complicated operation procedure as in the method described with reference to FIG. 5 may be appropriately selected as a value of N> = 3 in consideration of an average interference range occurring in general multi-hop transmission.

3-2. How resource number is determined for each link

The resource number used by each link j → k may be sequentially determined according to the following Equation 11 according to the determined number N of used resources.

Here, A mod B means the remainder of A divided by B. Therefore, when N = 3, n _jk is 1, 2, 3, 1, 2, 3, 1, 2, 3,... Each transport link has a value of 1, 2, 3, 1, 2, 3, 1, 2, 3,... Resources are used in the order of. Therefore, the simultaneous transmission link set is defined as a set of links having the same number of used hops as shown in Equation 12 below.

3-3. How to determine the usage time (time slot length) of each resource

When the amount of data to be transmitted on each link is given as D _req to satisfy the required end-to-end rate requirement, the time required for transmission on each link is determined as shown in Equation 13 below.

If the IEEE 802.11 WLAN protocol is used as the transmission protocol, the ACK message may be calculated as shown in Equation 14 in consideration of additional ACK message transmission and IFS (Inter-Frame Space) overhead.

Here, T _ack means ACK message transmission time, T _SIFS means SIFS (Short Inter-Frame Space) transmission time. The transmission time (time slot length) of each resource can be determined in two ways depending on the complexity of scheduling and can be selectively used.

In the first method, the amount of resources (resource usage time) allocated to each link is equally determined. The maximum value of resource usage time required for each link is determined as shown in Equation 15 below. FIG. 6 is a diagram illustrating an embodiment of a case in which resource usage time according to the present invention is equally allocated (when transmitting 6 hops). FIG.

In this case, as shown in FIG. 6, the usage time of each resource is equally allocated to T, which is determined by the transmission time from the node 5 to the longest transmission time. That is, the method of allocating the same resource usage time to all links is determined as the maximum value of the transmission time required by all nodes in consideration of QoS information of transmission data and transmission rates of all links on the transmission path. In this method, since the amount of resources used is the same for all links, the overhead of informing this resource length information is reduced, and the scheduling process 12 in FIG. 1 can be simplified.

The second method is to determine the resource usage time allocated to each link differently according to the resource used, and the time used for each resource is different as shown in FIG. Accordingly, the usage time of each resource is determined for each simultaneous transmission link, and is determined as the maximum value of the transmission time required between the simultaneous transmission links as shown in Equation 16 below. That is, the method of allocating different time according to the used resource is determined by the maximum value of the transmission time required by each simultaneous transmission node in consideration of the QoS information of the transmission data and the transmission rate between the simultaneous transmission links.

4. Transmit Power Control (TPC) Operation Process

Inter-link interference may occur when the topology or channel changes due to the movement of the terminal during multi-hop data transmission. This leads to data collisions, which hinders QoS of multi-hop transmissions. In the case of such interference and collision, TPC operation can eliminate interference and resume transmission quickly.

7 is a diagram illustrating an embodiment of an operation of a transmit power control (TPC) according to the present invention.

The receiving node recognizes a corresponding terminal that interferes with a collision and requests the corresponding terminal to perform a TPC. The TPC request is transmitted to the corresponding terminal that interferes through the control packet. The interfering terminal, i.e., the terminal that needs to perform the TPC, should reduce the transmission power, and reduce the transmission power as much as possible by using the timeslot of the allocated resources. (Reducing the transmission power lowers the transmission data rate. The actual usage time of the allocated resource increases.) In the case of the interfering node 4 in FIG. 7, the transmission power is lowered and the usage time of the transmission resource is used up. At this time, since the transmission power is lowered and transmitted, interference to the node 2 is alleviated.

The operation of determining the transmission power value is the same as that of determining the transmission power by the following Equation 17.

5. Rescheduling Operation Process

Interference can occur due to additional topology and channel changes even though TPC is performed when interference occurs. In such a case, re-scheduling between the interfering links separates the used resources to eliminate interference and resume transmission. . In addition, when interference cannot be eliminated through the TPC (that is, when the interfering node is using up the allocated resources), rescheduling is performed on the corresponding resource part.

8 is a diagram illustrating an embodiment of a rescheduling operation process according to the present invention.

When a collision occurs, the terminal recognizes the interference and requests rescheduling to separate resources from the terminal. The request for performing rescheduling is transmitted to the corresponding terminal that interferes through the control packet. The resource usage time T _i value of each link determined at the time of rescheduling allows the transmission while satisfying the QoS without interference by using the TX time value originally intended for the link. In the future, the resource usage time for each link can be reset by recalculating the possible data rates.

6. Rerouting Operation Process

If rescheduling with TPC does not solve the interference and collision problem, rerouting is performed. Rerouting can be performed again from the beginning through a routing operation for initial connection establishment, or can be performed by determining the worst node and searching the route only around the corresponding worst node. . This section describes how to determine and reroute worst nodes on a transmission path.

9 is a diagram illustrating an embodiment of a determination condition of a worst node according to the present invention.

When i, j, and k nodes are connected in sequence to perform multi-hop transmission, when j node becomes a worst node, it is a case where R _ij <α or R _jk <α or T _j <β. Here, R _ij represents the transmission rate between the transmitting node i and the receiving node j, T _j represents the survival time of the j node, and α and β represent thresholds for the transmission rate and the survival time that must be satisfied, respectively. Therefore, if the transmission rate of the two links connected with the node j or the survival time of the node j itself does not exceed the predetermined threshold, the node j is determined to be a worst node. In this case, in order to guarantee the transmission rate and survival time in the entire transmission path, first, the worst node is removed and node i and node k are directly connected, second, node j is removed and replaced with other neighboring nodes. You can optionally use one of three ways to leave node j and add other nodes on the transmission path.

10 is a diagram illustrating an embodiment of removing a worst node.

If you remove the worst node (worst node), and a direct connection between the node i and the node k, while R _ik> α as shown in FIG. 10 is a case where the condition satisfying T _i> β is satisfied. In this case, even if there is no node j, if the link between i → k is directly connected and the survival time T _i according to the transmission rate between i → k and the transmission power of the transmitting node i satisfies the predetermined threshold, the worst node is removed. Can be connected directly.

11 is a diagram illustrating an example of replacing a worst node, and illustrates a case of replacing a worst node with a new neighboring node.

When a new node l is found and the paths are connected from i → l → k, node l can be used when conditions of Ri _il > α, R _lk > α, T _i > β, and T _l > β are satisfied simultaneously.

12 is a diagram illustrating an embodiment of adding a new node around the worst node.

There are two cases, where case I occurs when R _jk <α or T _j <β, where a new node l is added on the j → k link. At this time, the added node l must satisfy all conditions R _jl > α, R _lk > α, T _j > β, and T _l > β. Case II occurs when R _ij <α, where a new node l is added on the i → j link. At this time, the added node l must satisfy both R _il > α, R _lj > α, T _i > β, and T _l > β.

The three methods (removal, replacement, addition) for guaranteeing the transmission rate and survival time of the entire link in case of the above-described worst node may be optionally selected, or two or more methods may be applied simultaneously. It may be.

In addition, the transmission rate R, which is a metric value used in the determination and resolution method of the worst node, may be replaced with various metrics indicating the link quality. For example, the SINR value, the SNR value, the RSS value, the channel gain value, and the like can be replaced. In addition, instead of the survival time T of the used node, it is possible to replace the energy remaining amount E, a value corresponding to the speed of the node, and various other values corresponding to the node capability.

7. IEEE 802.11 protocol based operation process

The above-described scheduling, TPC, and rescheduling operations may be applied to the IEEE 802.11 WLAN protocol to verify the actual operation of the schemes proposed by the present invention.

FIG. 13 shows an example of a transmission framework in an ad hoc mode of the IEEE 802.11 protocol.

If the synchronization between nodes communicating directly is correct, beacon messages are sent and received at the start of the superframe. Within the beacon interval, the transmission interval is divided into an Announcement Traffic Indication Message (ATIM) window and a data transmission interval. During the ATIM window period, the UE notifies that there is data to be exchanged with each other through a handshake. This is accomplished by exchanging ATIM packets and ACK packets for them between the transmitting and receiving nodes. The node transmitting the ATIM message completes the transmission by transmitting a data packet based on contention in the next data transmission interval and receiving an ACK. Nodes that exchange ATIM messages during the ATIM window period awake during data transmission to perform data transmission and reception, and nodes that do not exchange ATIM messages doze during data transmission to reduce power consumption. This process is repeatedly performed every beacon cycle.

FIG. 14 is a structural diagram of an embodiment of a multi-hop transmission framework according to the present invention based on the IEEE 802.11 protocol (in case of resource allocation of different sizes), which is a case where the multi-hop transmission method according to the present invention is applied to the IEEE 802.11 protocol. The architecture of a multihop transport framework is shown.

14 corresponds to a case of allocating resources of different sizes. In this case, MTIM (Multihop Traffic Indication Message) packet is defined and an interval in which it can be transmitted is allocated within a beacon interval. To this end, the beacon packet contains an indication that specifies that there is an MTIM transmission immediately following.

The MTIM packet is transmitted during the T _MTIM period after the beacon packet, and the first MTIM packet is randomly determined by the contention method in consideration of other multi-hop transmitting terminals. The MTIM packet indicates that there is multi-hop transmission between connected terminals, and the information included in the MTIM packet is as follows.

① time length information allocated within the beacon interval: T _MTIM , T _ATIM , T _multihop , T ₁ , T ₂ , T ₃ , T _contention

② N number of resources used

③ Use link number information by hop number

④ routing path information (S,…, i, j, k,…, D)

⑤ Information on TPC usage by link (ON = 1 / OFF = 0)

In this case, the length T _MTIM of the MTIM transmission interval may be determined as shown in Equation 18 below.

In this case, t _beacon , t _MTIM , and t _SIFS represent time for transmitting a beacon, MTIM packet, and SIFS time, respectively. In addition, t _add is a time allocated additionally for contention-based transmission of the first MTIM packet. The T _MTIM time increases because the number of MTIMs to be exchanged increases in proportion to the number of nodes on the transmission path.

To maintain compatibility with conventional 802.11 ad-hoc mode operation ATIM window and the contention (contention) data transmission interval of the base are maintained, T _ATIM allocated for this purpose and T _contention The length is appropriately determined within the time remaining after allocating T _MTIM and T _multihop . The operation of ATIM and T _contention is the same as that of the existing 802.11 protocol.

The MTIM message is broadcast by each node in the T _MTIM interval. The node sending the MTIM knows that the other node broadcasts the same MTIM. Therefore, transmission of an ACK packet, which should generally be responded to during data transmission, can be omitted. In addition, the interval between each MTIM packet transmission ensures continuous MTIM transmission without the interference of other terminals that do not participate in multi-hop transmission using the SIFS interval.

The UE participating in all multi-hop transmissions maintains an awake state in the T _MTIM and T _ATIM intervals and the data transmission / reception intervals, and reduces power consumption by switching to a doze state other than transmission and reception.

T _MTIM During this period, other neighbors can see that there are multi-hop transmissions, and since the channel becomes busy when the MTIM begins to transmit, it may interfere until the end of a series of MTIM transmissions. none.

If MTIM packets are to be transmitted each time within a beacon interval, the overhead they occupy can be large, so the following methods are considered as a way to reduce the overhead.

First, if the previously transmitted information is the same as the information to be transmitted this time, only the indication indicating that there is no change with the previous information when the MTIM is transmitted every beacon period.

Second, when there is little changed information, only the changed value is mentioned separately to compress and transmit the MTIM information.

15 is a structural diagram of an embodiment of a multi-hop transmission framework (in the case of resource allocation of the same size) according to the present invention based on the IEEE 802.11 protocol.

If the resource usage time is equally allocated as described above in FIG. 6, multi-hop transmission is possible using the transmission framework shown in FIG. 15 without transmitting the MTIM packet. That is, since it is not necessary to inform the time information allocated to each used resource, the node uses the beacon and broadcasts information on the same amount of allocated resource without transmitting the MTIM packet to inform all nodes of the time of use of the resource. . This approach significantly reduces the overhead of MTIM packet transmission and has the advantage of maintaining compatibility with existing 802.11 protocols. Since the operation of the multi-hop transmission is the same as described above, the description thereof will be omitted.

7-1. How TPC Works in the 802.11 Framework

16 is a diagram illustrating an embodiment of a multihop TPC operation process according to the present invention based on the IEEE 802.11 protocol.

The terminal, which has not received the collision, recognizes the terminal that interferes with the terminal and requests the terminal to perform a TPC. The TPC execution request is made by forwarding the MTIM transmission by setting whether the node performs TPC.

At this time, the source node serving as a master also performs reverse forwarding so that the changed MTIM message information can be known. (At this time, since MTIM is transmitted in different directions, there is no interference / collision between MTIMs. ) The transmit power level reduced by the UE that needs to perform the TPC is determined as the power that can be lowered as much as possible by using a given timeslot.

7-2. Rescheduling Behavior in the 802.11 Framework

17 is a diagram illustrating an embodiment of a multi-hop rescheduling operation process according to the present invention based on the IEEE 802.11 protocol.

The terminal, which has not received the collision, recognizes the terminal that interferes with the terminal and requests the terminal to perform rescheduling. The request for performing rescheduling is possible by modifying scheduling information and transmitting it in the MTIM transmission. At this time, the information that needs to be corrected is as follows.

① Time length information: T _multihop , T ₁ , T ₂ , T ₃ , T _contention

② Number of hops used N value (= number of timeslots used)

③ Use link number information by hop number

At this time, the source node serving as the master also performs reverse forwarding so that the changed MTIM message information can be known. Each node receiving the modified MTIM information transmits data in each allocated resource region based on the new information.

8. Performance Verification of Multi-hop Transmission Method According to the Present Invention

The performance comparison result of the multi-hop transmission method according to the present invention and the conventional method are derived through the simulation as follows.

Table 1 below shows parameter values used in the simulation.

In the conventional IEEE 802.11 ad hoc scheme, a beacon interval is determined in a multiple of 100 ms using a fixed PSM period, and does not use a TPC. On the other hand, the present invention uses a TPC to vary the PSM period in consideration of rate requirements. Therefore, performance analysis uses the traditional method (fixed resource size) using the fixed PSM length (fixed resource amount), the proposed method using variable PSM length (type described in FIG. 13), and the variable PSM length. The method of additionally performing the TPC (when the TPC described in FIG. 7 is applied to the method described in FIG. 6) was compared.

8-1. Total Power Consumption Comparison Results

FIG. 18 shows an example of a result of comparing total power consumption (when demand rate = 100 Kbps), and FIG. 19 shows a result of comparing total power consumption (when demand rate = 1 Mbps). As an example, a graph comparing the total power consumption for the case where the end-to-end required rate is 100 Kbps and 1 Mbps, respectively.

In FIG. 18 and FIG. 19, the total power consumption shows the total power consumed by all nodes participating in the multihop transmission. Proposed methods that use variable PSM lengths (indicated by triangles) and those that use variable PSM lengths and perform additional TPCs (Proposed PSM + TPC, circled) are the traditional methods (Conventional PSMs, rectangles). It can be seen that the power saving effect is increased by increasing the time to sleep compared to), and further reduction of the transmission power through the TPC operation results in a larger power saving effect.

8-2. Outage Probability Comparison Results

FIG. 20 is an example of an Outage Probability comparison result (when demand rate = 100 Kbps), and FIG. 21 is an example of Outage Probability comparison result (when request rate = 1 Mbps). As an example, a graph comparing the probability of outage is shown for the case where the end-to-end required rate is 100 Kbps and 1 Mbps, respectively.

Outage probability in FIG. 20 and FIG. 21 indicates a probability of not satisfying the required transmission rate. Proposed methods that use variable PSM lengths (indicated by triangles) and those that use variable PSM lengths and perform additional TPCs (Proposed PSM + TPC, circled) are the traditional methods (Conventional PSMs, rectangles). As the beacon period is shortened compared to the Rx, the end-to-end transmission rate is increased, so the outage probability is lowered.

8-3. Lifetime comparison results

22 is an exemplary view of the results of comparing the lifetime.

FIG. 22 illustrates a case in which a conventional shortest hop routing scheme (Conventional Shortest Hop Routing (represented by a rectangle)) is used and a scheme using a variable PSM length which is an embodiment of multi-hop transmission according to the present invention. + PSM, represented by a triangle) and a variable PSM length, and using the TPC (Proposed Routing + PSM + TPC, circle) shows a comparison of the lifetime (lifetime).

In FIG. 22, the life time is defined as a time taken after a path is set until a node on the path runs out of battery and no longer maintains the path. In the conventional shortest hop routing scheme, since the node characteristic information is not used, the performance of the shortest hop routing scheme is constant, whereas the schemes according to the present invention consider the remaining energy of the node and the transmission rate between the connection links, and use PSM or TPC. Therefore, it can be seen that the life time increases compared to the conventional method, and as the number of connectable nodes increases, the life time increases (node diversity effect).

On the other hand, the multi-hop transmission method according to the present invention as described above may be implemented in the form of program instructions that can be executed by various computer means may be recorded on a computer readable medium. The computer-readable medium may include program instructions, data files, data structures, and the like, alone or in combination. The program instructions recorded on the medium may be those specially designed and constructed for the present invention or may be available to those skilled in the art of computer software. Examples of computer-readable media include magnetic media such as hard disks, floppy disks and magnetic tape; optical media such as CD-ROMs and DVDs; magnetic media such as floppy disks; Magneto-optical media, and hardware devices specifically configured to store and execute program instructions such as ROM, RAM, flash memory, and the like. The medium may be a transmission medium such as an optical or metal line, a wave guide, or the like, including a carrier wave for transmitting a signal designating a program command, a data structure, or the like. Examples of program instructions include machine language code such as those generated by a compiler, as well as high-level language code that can be executed by a computer using an interpreter or the like. The hardware device may be configured to operate as one or more software modules to perform the operations of the present invention, and vice versa.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it is to be understood that the invention is not limited to the disclosed exemplary embodiments, but, on the contrary, Various permutations, modifications and variations are possible without departing from the spirit of the invention.

Therefore, the scope of the present invention should not be construed as being limited to the embodiments described, but should be determined by the scope of the appended claims, as well as the appended claims.

Claims (17)

delete In the multi-hop transmission method in a wireless ad hoc network,
A routing step of performing routing to determine a multihop transmission path;
A scheduling step of performing scheduling for the determined multi-hop transmission path and allocating transmission resources for each multi-hop link;
Transmitting data and control information for multi-hop transmission using a result of performing the scheduling, and operating in a power saving mode (PSM); And
An interference control step of controlling interference by performing transmission power control (TPC), rescheduling, or rerouting as a collision occurs during multi-hop data transmission or the amount of interference exceeds a first threshold,
The routing step,
A multi-hop transmission method for determining a multi-hop transmission path using a routing cost in consideration of power consumption and energy remaining of each node.
3. The method of claim 2,
The routing step,
If the energy remaining amount of any node is less than the second predetermined threshold or the transmission rate between the arbitrary node and another node is smaller than the third predetermined threshold, the routing cost is infinite so that the arbitrary node is not included in the transmission path. Multihop transmission method, set to a value.
3. The method of claim 2,
The routing step,
A multihop transmission method for determining a path having the smallest value of the routing cost or a path having the smallest sum of the total routing costs as the multihop transmission path.
In the multi-hop transmission method in a wireless ad hoc network,
A routing step of performing routing to determine a multihop transmission path;
A scheduling step of performing scheduling for the determined multi-hop transmission path and allocating transmission resources for each multi-hop link;
Transmitting data and control information for multi-hop transmission using a result of performing the scheduling, and operating in a power saving mode (PSM); And
An interference control step of controlling interference by performing transmission power control (TPC), rescheduling, or rerouting as a collision occurs during multi-hop data transmission or the amount of interference exceeds a first threshold,
Wherein the scheduling step comprises:
Allocate the same transmission resources to two or more transmission links within the limit of no interference between the multi-hop links, and determine the number of orthogonal resources used in consideration of the amount of interference occurring between the nodes transmitting simultaneously. Multi-hop transmission method for determining resource usage accordingly.
6. The method of claim 5,
The number of used resources,
A method of multi-hop transmission, determined as "the maximum number of interference hops of all nodes on the transmission path + 2 or more".
6. The method of claim 5,
The number of used resources,
The multi-hop transmission method of determining a value of 3 or more in consideration of the average interference range that occurs during multi-hop data transmission.
6. The method of claim 5,
Wherein the scheduling step comprises:
A method of multi-hop transmission, in which resource usage (resource usage time) allocated to each link is equally determined.
The method of claim 8,
Determining the resource usage equally,
Multi-hop transmission method for determining the maximum transmission time required by all nodes in consideration of the quality-of-service (QoS) information of the transmission data and the transmission rate of all links on the transmission path.
6. The method of claim 5,
Wherein the scheduling step comprises:
A method of multi-hop transmission, in which resource usage (resource usage time) allocated to each link is determined differently according to used resources.
11. The method of claim 10,
The process of determining the resource usage differently,
And determining the maximum transmission time required by each simultaneous transmission node in consideration of the QoS information of the transmission data and the transmission rate between the simultaneous transmission links.
In the multi-hop transmission method in a wireless ad hoc network,
A routing step of performing routing to determine a multihop transmission path;
A scheduling step of performing scheduling for the determined multi-hop transmission path and allocating transmission resources for each multi-hop link;
Transmitting data and control information for multi-hop transmission using a result of performing the scheduling, and operating in a power saving mode (PSM); And
An interference control step of controlling interference by performing transmission power control (TPC), rescheduling, or rerouting as a collision occurs during multi-hop data transmission or the amount of interference exceeds a first threshold,
The power saving mode (PSM) operation,
In a multi-hop transmission, a node operates by turning off a transmission / reception module and switching to a sleep mode during a period of no transmission and reception.
In the multi-hop transmission method in a wireless ad hoc network,
A routing step of performing routing to determine a multihop transmission path;
A scheduling step of performing scheduling for the determined multi-hop transmission path and allocating transmission resources for each multi-hop link;
Transmitting data and control information for multi-hop transmission using a result of performing the scheduling, and operating in a power saving mode (PSM); And
An interference control step of controlling interference by performing transmission power control (TPC), rescheduling, or rerouting as a collision occurs during multi-hop data transmission or the amount of interference exceeds a first threshold,
The interference control step,
If a collision occurs during the multi-hop data transmission or the interference amount exceeds the first threshold, the transmission power control (TPC) operation may be performed to eliminate the interference and resume transmission, or if the transmission power control (TPC) may not solve the problem. Performing rerouting and proceeding to the scheduling step if resolving is not possible even by rescheduling and retransmission, or performing transmission power control (TPC) or rescheduling.
14. The method of claim 13,
The interference control step,
If collisions and interferences occur during multi-hop data transmission due to the movement of nodes and changes in the channel environment, the transmission power of the interfering nodes is reduced by performing TPC or redistribution of transmission resources. Multi-hop transmission method to remove the collision and interference, or to remove the interference by determining the worst node (worst node) to perform rerouting.
15. The method of claim 14,
The transmission power control (TPC) performing process,
And minimizing transmission power by the interfering node to use all timeslots of allocated resources, thereby reducing the transmission power as much as possible.
15. The method of claim 14,
The worst node determination process,
And determining the arbitrary node as the worst node when a transmission rate of two links connected to any node is less than a second predetermined threshold or a survival time of the certain node is less than a third predetermined threshold.
17. The method of claim 16,
The rerouting process,
Remove the worst node and directly connect the two nodes on both sides of the worst node, or remove the worst node and replace it with another node around the worst node, or leave the worst node and transfer the other node around the worst node. In addition to the above, multi-hop transmission method.

Images