KR101122241B1 - Throughput enhancement methods in multi-hop ad hoc networks - Google Patents

Abstract

The present invention relates to a method of transmitting an event generated in a sensor network to a sink node, and more particularly, to a method of transmitting an event generated to a sink node without collision.

To this end, the present invention provides a method for determining a minimum contention window size in a sensor node constituting a sensor network, wherein transmission data that needs to be transmitted to a higher neighbor sensor node among collected collected data and immediate transmission of the transmission data are required. Extracting transmission data immediately; Calculating a transmission weight that is a ratio of the immediate transmission data to the transmission data; And determining a minimum contention window size in inverse proportion to the calculated total transmission weight including the transmission weight.

Sensor network, CSMA / CA, contention window, routing, weights, nodes, sink nodes, data packets

Description

Throughput enhancement methods in multi-hop ad hoc networks

The present invention relates to a method of transmitting an event generated in a sensor network to a sink node, and more particularly, to a method of transmitting an event generated to a sink node without collision.

In general, a mobile communication system transmits and receives data between a mobile element and a base station. The mobile station and the base station directly transmit and receive data without passing through other mobile terminals or nodes. However, a sensor network uses other sensor nodes when it wants to transfer data from a sensor node to a sink node.

Hereinafter, a structure of a general sensor network will be described with reference to FIG. 1. As shown in FIG. 1, the sensor network consists of a sink node and a plurality of sensor nodes. Although FIG. 1 illustrates only one sink node, the sensor network may be composed of at least two sink nodes according to a user's setting.

The sensor node collects information about a target area set by a designated user. The information on the target area collected by the sensor node may include ambient temperature, humidity, object movement, and gas leakage. The sensor node transmits data of information collected in the target area to the sink node. The sink node receives data transmitted by the sensor nodes forming the sensor network. The sensor node located within a certain distance from the sink node directly transmits data to be transmitted to the sink node. However, a sensor node that is not located within a certain distance transmits the collected data to sensor nodes adjacent to the sink node instead of passing the collected data directly to the sink node.

As described above, the reason why the sensor node which is not located within a certain distance transmits data by using adjacent sensor nodes is to minimize power consumption due to data transmission. That is, the distance between the sink node and the sensor node and the power consumed by the sensor node to transmit data to the sink node are generally proportional to each other.

Therefore, the sensor node that is not located within a certain distance from the sink node can minimize the power consumption due to the data transmission by transmitting the collected data using a plurality of sensor nodes.

In general, the IEEE 802. 11 protocol is now standardized in Medium Access Control (hereinafter referred to as MAC) and the physical layer. In addition, the basic MAC structure is composed of a distributed coordination function (hereinafter referred to as DCF) based on carrier sense multiple access with collision avoidance (CSMA / CA). Here, the DCF is a method for sharing and using one medium in a network composed of a plurality of nodes, and only a node winning the competition can transmit data.

1 is a diagram illustrating a method of transmitting data in a conventional DCF section. First, if there is data to be transmitted by a given sensor node, it is first checked whether the medium is in a "busy" state or an "idle" state. That is, it checks whether another sensor node is occupying the medium and transmitting. If the result of the check is "idle", the medium is continuously observed as "idle" state by DIFS (DCF Inter Frame Space), which is the interval between frames, and when the state is "idle" state, the frame is transmitted.

If the check indicates that the medium is in the "busy" state, the transmission is delayed until it changes to the "idle" state, where a number of sensor nodes are waiting for the medium to change from the "busy" state to the "idle" state. The end point is the interval with the highest collision probability. Accordingly, IEEE 802.11 employs a random backoff procedure to minimize collisions in competition between sensor nodes.

Then, backoff is performed to wait for an arbitrary time before transmitting the frame. In this case, when a predetermined sensor node enters the backoff, carrier sensing is performed to check the activity of the medium for each backoff slot. If the medium is "idle", it reduces the backoff time by a Slot Time, and if the medium is "busy" it is deferred without decreasing the backoff time. In addition, the backoff is determined by the number of slot times, and each station has an arbitrary number of random backoffs within a contention window (hereinafter referred to as CW) before transmitting data. Determine the number of slot times. That is, the equation for obtaining the backoff is as follows.

Backoff Time = Random () × a Slot Time

Here, a Slot Time is a value determined according to a corresponding physical layer (PHY), and Random () is an arbitrary integer value obtained from a closed section [0, CW]. In addition, CW is an integer between CWmin and CWmax, and CW starts from the value of CWmin and increases to the next value (about 2 times) each time it is retransmitted without receiving an acknowledgment.

If there is a lot of contention in the network and the network condition is not good, the response frame for the frame is not transmitted and the maximum number of retransmission attempts for the frame is exceeded. By continuing to initialize, there is a problem that the sensor nodes participating in the competition drop many frames in successive collisions, resulting in a drop in overall throughput.

The present invention proposes a method of transmitting data collected or received by a sensor node to a sink node without collision or loss. In addition, the present invention proposes a method for transmitting data collected or received by a sensor node to a sink node without delay of data transmission using minimum energy.

In the method for determining the minimum contention window size in the sensor node constituting the sensor network to solve the above-mentioned problem, the transmission data that needs to be transmitted to the upper neighboring sensor node among the collected data and the immediate transmission of the transmission data Extracting the transmission data as soon as required; Calculating a transmission weight that is a ratio of the immediate transmission data to the transmission data; And determining a minimum contention window size in inverse proportion to the calculated total transmission weight including the transmission weight.

In the method, the total transmission weight is the sum of the total transmission weight of the lower neighbor sensor node received from the lower neighbor sensor node and the transmission weight calculated by the sensor node, wherein the sensor node has multiple paths to transmit the data. If it is a path, the transmission weight obtained by dividing the total transmission weight by the number of the multipaths is transmitted to the uplink neighboring sensor node.

In the above-described method, the minimum contention window size is proportional to the number of sensor nodes detecting a specific event among the sensor nodes constituting the sensor network.

In order to solve the above problems, the present invention extracts the transmission data that needs to be transmitted to the upper neighboring sensor node among the collected collected data and the immediate transmission data that is required to be immediately transmitted among the transmission data, and the immediate transmission of the transmission data. A calculating unit calculating a transmission weight which is a ratio of data; A determination unit that determines a minimum contention window size in inverse proportion to a total transmission weight including the calculated transmission weight; And a control unit instructing the calculation unit to calculate the transmission weight and instructing the determination unit to determine the minimum contention window size.

The total transmission weight of the sensor node described above is the sum of the total transmission weights of the lower neighboring sensor nodes received from the lower neighboring sensor nodes and the transmission weights calculated by the sensor nodes. And calculating the transmission weight obtained by dividing the total transmission weight by the number of the multipaths, and the transmitter transmits the calculated transmission weight to the uplink neighboring sensor node.

The present invention to solve the above problems is an upper sensor node; From the collected data, the transmission data that needs to be transmitted to the upper neighboring sensor node and the immediate transmission data that are required for the immediate transmission are extracted, and the transmission weight that is the ratio of the immediate transmission data to the transmission data is calculated. A sensor node for determining a minimum contention window size in inverse proportion to a total transmission weight including the calculated transmission weight; A sensor network for determining a minimum contention window size, including a lower sensor node for transmitting a transmission weight to the sensor node.

The total transmission weight of the sensor network described above is the sum of the total transmission weights of the lower neighboring sensor nodes received from the lower neighboring sensor nodes and the transmission weights calculated by the sensor nodes. In the case of the multipath, the transmission weight obtained by dividing the total transmission weight by the multipath number is transmitted to the uplink neighboring sensor node.

As described above, the present invention transmits data collected or received by the sensor node to the sink node without collision or loss. In addition, the present invention transmits data collected or received by the sensor node to the sink node without delay of data transmission using minimum energy. Therefore, the present invention can efficiently transmit the data collected by the sensor node constituting the sensor network to the sink node.

The foregoing and further aspects of the present invention will become more apparent through the preferred embodiments described with reference to the accompanying drawings. Hereinafter will be described in detail to enable those skilled in the art to easily understand and reproduce through this embodiment of the present invention.

3 illustrates single path routing and multipath routing according to an embodiment of the present invention. Hereinafter, single path routing and multipath routing will be described with reference to FIG. 2.

According to FIG. 3, sensor node 1, sensor node 2, sensor node 3, and sensor node 4 form one group, and sensor node 5, sensor node 6, sensor node 7, and sensor node 8 form one group. . The sensor nodes 1 to 4 transmit the collected data to the sensor node 9, and the sensor nodes 5 to 8 transmit the collected data to the sensor node 10. Therefore, the sensor 9 and the sensor node 10 are not enough space to store in the buffer due to the temporarily received data, which causes data loss.

When the data is lost, the sensor nodes 1 to 8 must retransmit the lost data, and energy consumption due to the data retransmission occurs. Therefore, there is a need for a method of transmitting the collected data to the sink node without data collision or loss. The present invention proposes a method of adjusting the contention window size so that the collected data can be transmitted to the sink node without collision or loss. In general, the node determines the contention window size for transmitting data.

In the context of the present invention, sensor nodes are randomly located in a specific area, and sink nodes are located at a point in a particular area. Sensor nodes and sink nodes are located in a specific area and then fixed. In addition, the sensor node and the sink node have the same transmission radius and sensing radius, and the packet for data transmission has the same size.

[Definition 1]

The flow of data packets from node i to node j is defined as fij.

[Definition 2]

In multipath routing, each node transmits the collected data in one of the multipaths. That is, each path divides and transmits the collected data. Therefore, the data to be transmitted by the relay node is the sum of the data collected by the relay node and the data received.

Li means the total data transmission amount of the relay node, and the unit is pps (packet per second). rki means the data packet transmission amount of path fki, and gi means its data packet transmission amount.

[Definition 3]

A node can distinguish between data that needs to be sent immediately and data that needs to be sent after a certain time.

Fi means a transmission weight, Ri means a data transmission amount to be sent immediately, gi means a data transmission amount to be transmitted. In general, it is assumed that all source nodes send the collected data immediately.

[Definition 4]

Therefore, the total transmission weight of the sensor nodes constituting the sensor network is the sum of the weights of the previous nodes and their own weights.

를 포함한다. 따라서 센서 노드는 전달받은 데이터 패킷에 포함되어 있는

와 자신의

를 이용하여 갱신한다.Generally, data packets are

It includes. Therefore, the sensor node is included in the received data packet

And own

Use to update.

FIG. 4 is based on the transmission weights transmitted from the sensor node 1, the sensor node 3, the sensor node 4, the sensor node 9, and the sensor node 10 constituting the multi-path routing of FIG. 3 according to an embodiment of the present invention. The time taken to calculate the total transmission weight is shown.

According to FIG. 4, the total transmission weight of sensor node 1 is 1, the total transmission weight of sensor node 3 is 2.5, the total transmission weight of sensor node 4 is 1.5, the total transmission weight of sensor node 9 is 4, and the sensor node The total transmission weight of eight is eight. As described above, it is assumed that each sensor node immediately transmits its collected data. Therefore, the total transmission weight of sensor node 1 and sensor node 2 is 1. Since the sensor node 2 may transmit the collected data to one of the sensor node 3 and the sensor node 4, the sensor node 3 and the sensor node 4 are each assigned a transmission weight of 0.5 from the sensor node 2. Therefore, the total transmission weight of the sensor node 3 becomes 1.5, which is the sum of its own transmission weight 1 and the transmission weight 0.5 by the sensor node 2. Other sensor nodes that make up multipath routing calculate the total transmission weight in the same way.

According to FIG. 4, the sensor nodes constituting the multipath routing can be within 0.2 seconds to calculate their total transmission weight. That is, the sensor node 10 takes 0.2 seconds to calculate its total transmission weight using the received transmission weight.

The following equation shows an example of calculating the minimum contention window size using the total transmission weight.

중에서 하나를 선택하며, 본 발명과 관련해서 싱크 노드에서 Wo를 결정해서 센서 네트워크를 구성하고 있는 센서 노드들로 전송한다. C는 센서 네트워크에서 이벤트가 발생한 지역에 위치하고 있는 센서 노드의 수와 관련된 파라미터이다.Wo is a constant

One of them is selected, and Wo is determined by the sink node according to the present invention and transmitted to the sensor nodes constituting the sensor network. C is a parameter related to the number of sensor nodes located in the region where an event occurs in the sensor network.

When an event is detected, each source node broadcasts a message containing the detected event identifier and its identifier to nodes within two adjacent hops. That is, a node receiving a message from a neighbor node broadcasts a message received to other neighbor nodes. The node receiving the message calculates the number of source nodes that sent the message in relation to the event. Therefore, C changes depending on the density of source nodes that make up the network.

When an event is detected, the value of C increases as the number of sensor nodes that generate data increases.

According to the equation, the source node can set a large size of the minimum contention window to avoid collisions. The relay nodes may set the minimum contention window size smaller than that of the source node.

Table 1 below shows total transmission weights and minimum contention window sizes of nodes located on the single path routing path and the multipath routing path of FIG. 2 using equations. In addition, Table 1 in Table 1 sets C to 4 and Wo to 32.

Single path routing Multipath Routing Node ID Fagg Minimum Competitive Window Size Fagg Minimum Competitive Window Size One One 124 One 124 2 One 124 One 124 3 3 42 2.5 50 4 One 124 1.5 83 5 One 124 One 124 6 One 124 1.5 83 7 2 62 1.5 83 8 4 31 4 31 9 4 31 4 31 10 8 16 8 16

According to Table 1, in single path routing, the node 1, node 2, node 4, node 5 and node 6 have a fagg of 1 and a minimum contention window size of 124. In single path routing, Node3's Fagg is 3 and the minimum contention window size is 42. In single path routing, node 7 has a Fagg of 2, a minimum contention window size of 62, node 8 and node 9 faggs 4, and a minimum contention window size of 31. In single path routing, node 10 has a Fagg of 8 and a minimum contention window size of 16.

In addition, according to Table 1, in the multipath routing, node 1, node 2 and node 5 have a fagg of 1, and the minimum contention window size is 124. In multipath routing, Node3's Fagg is 2.5 and its minimum contention window size is 50. In multipath routing, nodes 4, 7 and 7 have a fagg of 1.5 and a minimum contention window size of 83. In multipath routing, nodes 8 and 9 have a Fagg of 4, a minimum contention window size of 31, a node 10 fagg of 8, and a minimum contention window size of 16.

In connection with the present invention, the sensor node calculates a minimum contention window size in inverse proportion to the calculation unit calculating a total transmission weight, which is a ratio of data that needs to be transmitted to a higher neighbor sensor node and data that needs to be transmitted immediately. It includes a decision unit to determine. The sensor node also instructs the calculation unit to calculate the total transmission weight, and includes a control unit instructing the determination unit to determine the minimum contention window size. Of course, in addition to the above-described configuration, other components including the storage unit and the transmission unit may be included in the sensor node.

FIG. 5 is a diagram illustrating a method for setting a minimum contention window size and a conventional IEEE 802.11 DCF and S-MAC protocol according to the present invention.

FIG. 5 (a) shows the number of collisions during data packet transmission, and FIG. 5 (b) shows the number of data packets lost in the buffer of the sensor node. Fig. 5 (c) shows the data packet rate, and Fig. 5 (d) shows the data throughput of the sensor node. FIG. 5 (e) shows the data packet transmission delay rate, and FIG. 5 (f) shows the energy consumption rate according to the data packet transmission.

Referring to FIG. 5, it can be seen that the transmission of data packets by determining the minimum contention window size using the proposed scheme has a higher effect than the conventional scheme.

While the present invention has been particularly shown and described with reference to exemplary embodiments thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the scope of the present invention .

1 is a diagram illustrating a sensor node constituting a general sensor network.

2 is a view showing a method of transmitting data in a conventional DCF interval,

3 illustrates single path routing and multipath routing according to an embodiment of the present invention.

FIG. 4 illustrates the time taken to calculate the total transmission weight in the sensor node constituting the sensor network according to an embodiment of the present invention.

5 is a view showing the effect of the method using the present invention as compared to the conventional method.

Claims (13)

In the method for determining the minimum contention window size in the sensor node constituting the sensor network, Extracting the transmission data that needs to be transmitted to the upper neighboring sensor node among the collected collection data and the transmission data that is immediately required for real-time transmission having a high priority among the transmission data; Calculating a transmission weight that is a ratio of the immediate transmission data to the transmission data; Determining a minimum contention window size in inverse proportion to a total transmission weight including the calculated transmission weight; The total transmission weight is, The method of determining a minimum contention window size, characterized in that the sum of the total transmission weight of the lower neighboring sensor node received from the lower neighboring sensor node and the calculated transmission weight of the sensor node. delete The method of claim 1, wherein the sensor node, And if the path to transmit the data is a multipath, transmitting the transmission weight obtained by dividing the total transmission weight by the number of the multipath to the upper neighboring sensor node. The method of claim 1 wherein the minimum contention window size is: And a proportional proportion to the number of sensor nodes detecting a specific event among the sensor nodes constituting the sensor network. 5. The method of claim 4, wherein the minimum contention window size is calculated by Equation 5 below.

CWmin [i]: minimum contention window size at node i Wo:

C: system parameter (the number of sensor nodes that detect a particular event)

: Total transfer weight of node i The method as claimed in claim 5, wherein the Wo is determined by the sink node and transmitted to the sensor nodes constituting the sensor network. Among the collected data, the transmission data that needs to be transmitted to the upper neighboring sensor node and the transmission data that is immediately required for real time transmission having the highest priority among the transmission data are extracted, and the transmission weight that is the ratio of the immediate transmission data to the transmission data. A calculating unit calculating a; A determination unit that determines a minimum contention window size in inverse proportion to a total transmission weight including the calculated transmission weight; And a control unit instructing the calculation unit to calculate the transmission weight and instructing the determination unit to determine the minimum contention window size. The total transmission weight is, The sensor node for determining the minimum contention window size, characterized in that the sum of the total transmission weight of the lower neighboring sensor node received from the lower neighboring sensor node and the calculated transmission weight of the sensor node. delete The method of claim 7, wherein the calculating unit calculates a transmission weight obtained by dividing the total transmission weight by the number of the multipaths when the path to transmit the data is a multipath, The transmitter determines the minimum contention window size, characterized in that for transmitting the calculated transmission weight to the upper neighboring sensor node. Upper sensor node; From the collected data, the transmission data that needs to be transmitted to the upper neighboring sensor node and the transmission data that are immediately transmitted are required when the high priority of the transmission data is required, and the transmission is the ratio of the immediate transmission data to the transmission data A sensor node for calculating a weight and determining a minimum contention window size in inverse proportion to a total transmission weight including the calculated transmission weight; And a lower sensor node for transmitting a transmission weight to the sensor node. The total transmission weight is, The sensor network for determining the minimum contention window size, characterized in that the sum of the total transmission weight of the lower neighboring sensor node received from the lower neighboring sensor node and the calculated transmission weight of the sensor node. delete The method of claim 10, wherein the sensor node, And transmitting the transmission weight obtained by dividing the total transmission weight by the number of the multipaths to the upper neighboring sensor node when the path to transmit the data is the multipath. The sensor network of claim 12, wherein the minimum contention window size is calculated by Equation 6 below.

CWmin [i]: minimum contention window size at node i Wo:

C: system parameter (the number of sensor nodes that detect a particular event)

: Total transfer weight of node i

Images