KR100776327B1 - Dynamic Load Balancing Routing Method in Wireless Networks - Google Patents

Abstract

The present invention is to provide a dynamic load balancing routing method that can improve the packet transmission rate and delivery time by routing in consideration of the degree of congestion of a specific node in a wireless network, Route Request message (Route Request: Broadcasting a RREQ packet to all connected first neighbor nodes, and broadcasting a route request message in which its own buffer information is added to the route request message received from the first neighbor node. Transmitting the data to all other second neighbor nodes connected to each other; and comparing the buffer information included in the path request message input from the second neighbor node with its own buffer information, and setting the buffer information recorded in the path request message to the minimum value. Updating, broadcasting, and transmitting to the connected destination node; And selecting a path having an updated minimum valid buffer having a maximum value among buffer information of the path request message received from one or more paths, and transmitting a route reply (RREP) to a source node.

Description

Dynamic Load-Balancing Routing in Radio Mesh Network

1 is a structural diagram of a wireless network network node according to an embodiment of the present invention

2 is a flowchart illustrating a dynamic node balancing routing method in a wireless network according to an embodiment of the present invention.

3 is a flowchart illustrating a dynamic node balancing routing method in a wireless network according to another embodiment of the present invention.

* Explanation of symbols for main parts of the drawings

S: source node D: destination node

A ~ B, P ~ R, I ~ K: connection node

The present invention relates to communication and applications over a wireless network, and more particularly, to a dynamic load balancing routing method that can prevent traffic congestion and improve the performance of an entire network during routing.

A radio mesh network is a network in a wireless multihop mode environment, and is a network topology in which wireless nodes are self-configurable. This has the advantage of facilitating easy coverage expansion and capacity enhancement of the entire wireless network by the addition of repeaters in a fluid network environment.

Therefore, it has been studied for the purpose of temporarily configuring a network in an area where an infrastructure does not exist or where an infrastructure based on the infrastructure is not easy to deploy. Recently, wireless network network technology is expected to be applied to various applications such as home networking, sensor network, and personal area network (PAN), and active research is being conducted as one of the next generation networking methods. In addition, the wireless network network routing protocol has become the most important research field as a technology that enables communication between nodes.

However, the reality is that the efficient routing scheme for the wireless network network environment is still insufficient.

That is, the routing schemes in the existing wireless network network are the minimum distance and power-based or four-layer congestion control scheme, and the routing considering the congestion does not consider the real-time monitoring. In addition, the routing protocol that supports most network networks in use is based on the adhoc routing protocols such as DSR and AODY.In the case of load balancing routing, the traffic information includes the number of packets and the number of connections. And byte counts, etc., do not handle the handling of nodes where actual congestion is concentrated.

Such congestion actually occurs at a specific node even in a path. Existing routing techniques do not select paths using the state information of the actual specific node where congestion occurs. I can't help seeing it.

In addition to these problems, as the demand for multimedia applications increases recently, higher bandwidths and traffic are required, and traffic concentrations frequently occur at specific nodes, and packet loss and communication delay due to congestion occur more frequently. In particular, the existing routing scheme uses a route cache, which increases the load on a particular node, resulting in worse routing performance of the wireless network.

Therefore, there is an urgent need for a routing method that can effectively solve such problems.

The present invention has been made to solve the above problems, and provides a dynamic load balancing routing method that can improve the packet transmission rate and delivery time by routing in consideration of the degree of congestion of a specific node on a wireless network. There is a purpose.

Another object of the present invention is to provide a dynamic load balancing routing method that measures congestion in real time to prevent congestion and achieves load balancing in a dynamic path discovery process.

It is still another object of the present invention to provide a routing method that proposes a more accurate and higher performance protocol by selecting a path in consideration of load balancing by using state information of a specific node in which congestion is concentrated.

A feature of the dynamic load balancing routing method in a wireless network according to the present invention for achieving the above object is (A) source node connected by broadcasting a Route Request message (RREQ) packet (broadcast) transmitting to all connected first neighbor nodes; and (B) all other second neighbors connected by broadcasting a route request message with its buffer information added to the route request message received from the first neighbor node. (C) comparing the buffer information included in the path request message inputted from the second neighbor node with its own buffer information, updating and broadcasting the buffer information recorded in the path request message to a minimum value. Transmitting to a connected destination node; and (D) a buffer of the route request message received from at least one or more paths at the destination node. The minimum effective update of the buffer beam, select the path having the maximum value in response message to the source node may comprises the step of transmitting (Route Reply RREP).

Preferably, the plurality of connection nodes further comprises the step of monitoring the state of its interface buffer to determine the number of packets accumulated in the interface buffer and valid buffer space information remaining free.

Preferably, the buffer information is characterized by including the number of packets accumulated in the interface buffer and the effective buffer space information remaining as a margin.

Preferably, the step (C) further includes transmitting to the destination node a path request message in which buffer information updated to a minimum value is repeatedly recorded until all connected neighbor nodes are applied.

Preferably, the step (D) comprises the steps of: (D1) detecting a minimum valid buffer through buffer information of a path request message input to a destination node, and (D2) comparing the detected minimum valid buffer with a predefined congestion threshold value; Determining whether the corresponding path is congested; and (D3) if it is determined that the path is congested, selecting one path having the maximum value of the minimum valid buffer among a plurality of paths, and responding to the source node. RREP).

Preferably, the step (D2) is characterized in that the path is determined to be congested if the minimum valid buffer is less than the defined congestion threshold.

Preferably, as a result of the determination in step (D3), if it is determined that the condition is not in a congestion state, the method further includes the step of selecting a path having a minimum hop among a plurality of paths and transmitting a response message (RREP) to the source node. do.

Preferably, the congestion threshold value is defined through a correlation between a communication delay time due to congestion of a node and a communication delay time due to an increase in the number of hops.

Preferably, the step (D) comprises (Da) detecting a first minimum valid buffer and a second minimum valid buffer through the buffer information of the path request message respectively input to the first path and the second path, and (Db); Calculating an error range based on the difference between the first minimum valid buffer and the second minimum valid buffer; and (Dc) comparing the calculated error range with a predefined node difference threshold to determine congestion between the two paths. (Dd) if it is determined that the degree of congestion between the two paths is severe, selecting one path having the maximum value of the least valid buffer among the plurality of paths and transmitting a response message (RREP) to the source node. Characterized in that it comprises a step.

Preferably, the step (Dc) is characterized in that it is determined that the two paths do not have a degree of congestion if the error range is less than the defined congestion threshold.

Preferably, if the determination result of (Dc) determines that there is no degree of congestion between the two paths, the method may further include selecting one path having the least hop among the plurality of paths and transmitting a response message (RREP) to the source node. It is characterized by.

Preferably, the node difference threshold value is defined through a correlation between communication delay time due to congestion between nodes and communication delay time due to an increase in the number of hops.

Preferably, the step (D) may further include detecting a first minimum valid buffer and a second minimum valid buffer through the buffer information of the path request message respectively input to the first path and the second path, and the detected first A first determination step of determining whether the corresponding path is congested by comparing a minimum valid buffer with a predefined congestion threshold value; and when the first determination result determines that the path is congested, the first minimum valid buffer and the second minimum valid buffer are determined. Calculating an error range through a difference between valid buffers; and a second determination step of determining a congestion degree between two paths by comparing the calculated error range with a predefined node difference threshold value; If it is determined that the congestion between the two paths is severe, it sends a response message (RREP) to the source node by selecting one path having the maximum value of the least valid buffer among the multiple paths. It is characterized by including a system.

Other objects, features and advantages of the present invention will become apparent from the following detailed description of embodiments with reference to the accompanying drawings.

A preferred embodiment of a dynamic load balancing routing method in a wireless network according to the present invention will be described with reference to the accompanying drawings. However, the present invention is not limited to the embodiments disclosed below, but may be implemented in various forms, and only the present embodiments are intended to complete the disclosure of the present invention and to those skilled in the art to fully understand the scope of the invention. It is provided to inform you.

FIG. 1 is a structural diagram of a wireless network network node according to an embodiment of the present invention, and FIG. 2 is a flowchart illustrating a dynamic node balancing routing method in a wireless network according to an embodiment of the present invention.

As shown in FIG. 1, the structure of a wireless network network node includes one source node S and one destination node D, and at least one path between the source node S and the destination node D. It consists of a plurality of connection nodes (A ~ C, P ~ R, I ~ K) to be connected (connection) to have.

At this time, the plurality of connection nodes (A ~ C, P ~ R, I ~ K) monitors the state of its interface buffer to determine the number of packets accumulated in the interface buffer and the information of the effective buffer space remaining as a free space have. For reference, connection node A is 5, connection node B is 2, connection node C is 4, connection node I is 3, connection node J is 6, connection node K is 5 It is assumed that the connection node P has 4, the connection node Q has 7 and the connection node R has 4 free buffer spaces. At this time, the value of the free buffer space is a numerical value representing the size or capacity of the buffer, and is represented as a constant to help understand the description.

Through this structure, the source node S and the destination node D exchange route request messages (RREQ) and response messages (Rute Reply: RREP) to select an optimal route and perform routing. .

Referring to FIG. 2, the dynamic node balancing routing method in the wireless network is described in detail as follows.

First, the source node S broadcasts a Route Request Message (RREQ) packet and transmits it to all neighbor nodes which are connected. In this case, since the neighbor node connected to the source node S is the connection node A, the connection node A receives a path request message transmitted from the source node S (S100).

Subsequently, the connection node A adds its buffer information to the received route request message RREQ. In this case, the buffer information preferably includes the number of packets accumulated in the interface buffer and the buffer space information remaining as a margin.

The buffer information is information used as a criterion for measuring a congestion situation. The larger the number of packets and the smaller the free buffer space, the corresponding node is determined to be congested. In this specification, in order to make the description easier, it should be noted that the buffer information is limited to the remaining buffer space information and is not intended to be limited thereto. In addition, according to the number of packets can be any number of embodiments within the scope of the technical idea, it should be recognized that any information can be used as long as the information to measure the congestion status of the node.

As such, the connection node A broadcasts a route request message including its free buffer space information 5 to all connected neighbor nodes. At this time, neighboring nodes connected to the connection node A include a connection node P, a connection node B, and a connection node I. Therefore, the connection node P, the connection node B, and the connection node I receive a path request message including the free buffer space information 5 of the connection node A (S200).

Next, the connection nodes P, B, and I compare the free buffer space information included in the input path request message with their free buffer space information and update the free buffer space information recorded in the path request message to the minimum value. The path request message including the updated free buffer space information is broadcasted and transmitted to another connected neighbor node (S300).

The process is repeated until all of the connection nodes are applied. Through this, the path request message in which the free buffer space information updated to the minimum value is recorded through all the connection nodes is finally broadcasted to the destination node D and transmitted (S400).

A more detailed description of all paths that may occur in the structure of a wireless network network node as shown in FIG. 1 is as follows.

First, a first path having an S-> A-> P-> Q-> R-> D path is as follows.

The connection node P receives the path request message in which the free buffer space information '5' is recorded via the connection node A, and then free buffer space information '5' recorded in the input path request message and its own free space. Compare buffer space information '4'. At this time, since the free buffer space information 4 is smaller than the recorded free buffer space information 5, the free buffer space information recorded in the path request message is updated to '4'. In addition, the free buffer space information updated by '4' is recorded in the path request message, and then broadcast and transmitted to the connected node Q, which is another connected neighbor node.

Subsequently, the connection node Q receives the path request message in which the free buffer space information '4' is recorded via the connection node P, and then free buffer space information '4' recorded in the input path request message and its own. Compare the free buffer space information '7'. At this time, since the recorded free buffer space information 4 is smaller than its own free buffer space information 7, the free buffer space information recorded in the path request message is kept at '4'. Then, the free buffer space information updated by '4' is recorded in the path request message, and then broadcasted and transmitted to the connected node R, which is another connected neighbor node.

Subsequently, after the connection node R receives the path request message in which the free buffer space information '4' is recorded via the connection node Q, the connection node R and its own free buffer space information '4' recorded in the input path request message are connected. Compare the free buffer space information '4'. At this time, since the recorded free buffer space information 4 and its own free buffer space information 4 are the same, the free buffer space information recorded in the path request message is maintained at '4'. Then, the free buffer space information updated to 4 is recorded in the path request message, and then broadcasted and finally transmitted to the destination node D, which is another neighbor node connected thereto.

Next, the second path having the path S-> A-> B-> C-> D is as follows.

After the connection node B receives the path request message with the free buffer space information '5' recorded through the connection node A, the free node space information '5' and its free space recorded in the input path request message are received. Compare buffer space information '2'. At this time, since the free buffer space information 2 is smaller than the recorded free buffer space information 5, the free buffer space information recorded in the path request message is updated to '2'. The free buffer space information updated by '2' is recorded in the path request message, and then broadcasted and transmitted to the connected node C, which is another connected neighbor node.

Subsequently, after the connection node C receives the path request message in which the free buffer space information '2' is recorded via the connection node B, the connection node C and the free buffer space information '2' recorded in the input path request message have their own. Compare the free buffer space information '4'. At this time, since the recorded free buffer space information 2 is smaller than its free buffer space information 4, the free buffer space information recorded in the path request message is maintained at '2'. Then, the free buffer space information updated by '2' is recorded in the path request message, and then broadcast is finally transmitted to the destination node C, which is another connected neighbor node.

Next, the third path having the path S-> A-> I-> J-> K-> D is as follows.

After the connection node I receives the path request message with the free buffer space information '5' recorded through the connection node A, the free node space information '5' recorded in the input path request message and its own free space Compare buffer space information '3'. At this time, since the free buffer space information 3 is smaller than the recorded free buffer space information 5, the free buffer space information recorded in the path request message is updated to '3'. In addition, the free buffer space information updated by '3' is recorded in the path request message, and then broadcasted to the connected node J, which is another neighboring node.

Subsequently, after the connection node J receives the path request message in which the free buffer space information '3' is recorded via the connection node I, the connection node J and the free buffer space information '3' recorded in the input path request message have their own. Compare the free buffer space information '6'. At this time, since the recorded free buffer space information 3 is smaller than its free buffer space information 6, the free buffer space information recorded in the path request message is maintained at '3'. The free buffer space information updated by '3' is recorded in the path request message, and then broadcasted and transmitted to the connected node K, which is another connected neighbor node.

Subsequently, after the connection node K receives the path request message having the free buffer space information '3' recorded through the connection node J, the connection node K and its own free buffer space information '3' recorded in the input path request message have their own. Compare the free buffer space information '5'. At this time, since the recorded free buffer space information 3 is smaller than its own free buffer space information 5, the free buffer space information recorded in the path request message is maintained at '3'. Then, the free buffer space information updated to '3' is recorded in the path request message, and then broadcast is finally transmitted to the destination node D, which is another neighboring node connected thereto.

As such, when the minimum free buffer space information updated and written to the minimum value in the path request message input from the source node S to the destination node D through the respective paths is called the minimum valid buffer, the first path S− > A-> P-> Q-> R-> D), the minimum valid buffer has a '4'. The minimum valid buffer has '2' through the second path (S-> A-> B-> C-> D) and the third path (S-> A-> I-> J-> K- > D), the minimum valid buffer has '3'.

The destination node D selects the path with the largest valid buffer among the path request messages received from the various paths, and sends a route reply (RREP) to the source node S to start communication. It becomes (S500).

Therefore, the destination node D selects the first path having the largest value among the minimum valid buffers input, and transmits a response message RREP to the source node S. FIG.

As such, by selecting the path in consideration of load balancing by using the real-time state information of a particular node concentrated in the routing process, it is possible to provide a higher performance dynamic load balancing routing method.

On the other hand, if the routing is performed using only the state information of a specific node, a hop count may be increased and a transmission delay may be increased. In other words, it is obvious that as the number of hops increases, the communication time from the source node S to the destination node D becomes longer.

Therefore, if the path is selected based on the congestion state information of a specific node simply by ignoring the hop count, in the worst case, the communication delay time due to the increase in the hop number may be longer than the communication delay time due to the node congestion. It could be.

Therefore, the number of such cases is solved by using at least one of a node's congestion threshold value and a node difference threshold value.

3 is a flowchart illustrating a dynamic node balancing routing method in a wireless network according to another embodiment of the present invention.

Referring to FIG. 3, new path request messages arrive at the destination node D through steps S100 to S400 of FIG. 2 (S510).

The second minimum valid buffer Qcur is detected through the path request message currently input to the destination node D, and the first minimum valid buffer Qpre is detected through the path request message previously input to the destination node D. ) Is detected (S520).

Subsequently, it is determined whether the corresponding path is congested by comparing the second minimum valid buffer Qcur with a predefined congestion threshold. That is, if the second minimum valid buffer Qcur is less than the defined congestion threshold, the corresponding path is regarded as a congestion state (S530).

At this time, comparison and determination for congestion use separate comparison means and control means. The comparison means and the control means is a category that can be easily described by those of ordinary skill in the technical field of the present invention, the specific configuration thereof will be omitted.

Therefore, if it is determined that the determination result (S530) is not in a congestion state, routing is performed using the minimum hop as a major metric as in the conventional method. That is, the destination node D selects one path having the least hop among the plurality of paths, and transmits a response message RREP to the source node S (S550).

In addition, if it is determined that the congestion state (S530), the congestion state to perform the routing using the load balancing method described in FIG. That is, the destination node D selects one path having the maximum value of the second minimum valid buffer Qcur among the plurality of paths, and transmits a response message RREP to the source node S (S560).

The congestion threshold is preferably defined as a value that minimizes the communication delay time by applying a correlation between the communication delay time due to congestion of the node and the communication delay time due to the increase in the number of hops.

In addition, when the destination node D receives two or more path request messages, the error range between the detected second minimum valid buffer Qcur and the first minimum valid buffer Qpre is calculated. The degree of congestion between the two paths is determined by comparing the calculated error range with a predefined node difference threshold. That is, if the calculated error range between the two paths is less than the defined node difference threshold, it is determined that the two paths have little congestion (S540).

At this time, the comparison and determination for the degree of congestion between the two paths uses separate comparison means and control means. The comparison means and the control means is a category that can be easily described by those of ordinary skill in the technical field of the present invention, the specific configuration thereof will be omitted.

Therefore, if it is determined in step S540 that there is little congestion between the paths, routing is performed using the minimum hop as a major metric as in the conventional method. That is, the destination node D selects one path having the least hop among the plurality of paths and transmits a response message to the source node S (S550).

In addition, when it is determined in step S540 that the degree of congestion between the paths is severe, routing is performed using the load balancing method described in FIG. 2. That is, the destination node D selects one path having the maximum value of the minimum valid buffer among the plurality of paths, and transmits a response message to the source node S (S560).

The node difference threshold value is preferably defined as a value that minimizes the communication delay time by applying a correlation between the communication delay time according to the degree of congestion between nodes and the communication delay time due to the increase in the number of hops.

Although the technical spirit of the present invention described above has been described in detail in a preferred embodiment, it should be noted that the above-described embodiment is for the purpose of description and not of limitation. In addition, one of ordinary skill in the art of the present invention will appreciate that various embodiments are possible within the scope of the technical idea of the present invention. Therefore, the true technical protection scope of the present invention will be defined by the technical spirit of the appended claims.

The dynamic load balancing routing method in the wireless network according to the present invention as described above has the following effects.

First, in consideration of the degree of congestion of the nodes in the wireless network network, it is possible to improve the packet transmission rate and transmission time to improve the performance of the wireless network network communication.

Second, more accurate and high-performance protocol can be proposed by selecting the path considering load balancing by using the status information of a specific node that is actually congested during the routing process.

Third, the dynamic load balancing routing method in the wireless network according to the present invention is applicable to the mobile terminal and the network router, which is robust to mobility and can efficiently use the wireless bandwidth.

Claims (17)

(A) broadcasting a Route Request Message (RREQ) packet from a source node and transmitting it to all connected first neighbor nodes; (B) broadcasting a route request message with its buffer information added to the route request message received from the first neighbor node and transmitting the route request message to all other connected second neighbor nodes; (C) comparing the buffer information included in the path request message inputted by the second neighbor node with its own buffer information, updating the buffer information recorded in the path request message to a minimum value, and broadcasting the same to the connected destination node; Wow, (D) sending a reply message (RUTE) to a source node by selecting a path having an updated minimum valid buffer among the buffer information of the path request message received from at least one path at a destination node having a maximum value; Dynamic load balancing routing method comprising a. The method of claim 1, And monitoring the state of the interface buffers of the first and second neighbor nodes to determine the number of packets accumulated in the interface buffer and valid buffer space information remaining free. In-Load Balancing Routing Method. The method of claim 1, And the buffer information includes information about the number of packets accumulated in the interface buffer and valid buffer space information remaining free. The method of claim 1, wherein step (C) And transmitting to the destination node a path request message recorded with the buffer information updated to the minimum value repeatedly until all connected neighbor nodes are applied. The method of claim 1, wherein step (D) (D1) detecting the minimum valid buffer through the buffer information of the path request message input to the destination node; (D2) determining whether the corresponding path is congested by comparing the detected minimum valid buffer with a predefined congestion threshold value; (D3) if it is determined that the congestion is in a congestion state, selecting one path having the maximum value among the minimum valid buffers and transmitting a response message (RREP) to a source node; Dynamic load balancing routing method. The method of claim 5, wherein the step (D2) And determining that the corresponding path is congested when the minimum valid buffer is less than a defined congestion threshold. The method of claim 5, If it is determined that the congestion state (D3) is not in a congestion state, the method further comprises the step of selecting a path having the least hop of the plurality of paths to send a response message (RREP) to the source node In-Load Balancing Routing Method. The method of claim 5, The congestion threshold is a dynamic load balancing routing method, characterized in that it is defined through the relationship between the communication delay time due to the congestion of the node and the communication delay time due to the increase in the hop number. The method of claim 1, wherein step (D) (Da) detecting the first minimum valid buffer and the second minimum valid buffer through the buffer information of the path request message respectively input to the first path and the second path; (Db) calculating an error range through a difference between the first minimum valid buffer and the second minimum valid buffer; (Dc) comparing the calculated error range with a predefined node difference threshold to determine a degree of congestion between two paths; (Dd) if it is determined that the degree of congestion between the two paths is severe, selecting one path having the maximum value of the least valid buffer among the plurality of paths and transmitting a response message (RREP) to the source node; Dynamic load balancing routing method. The method of claim 9, wherein (Dc) step And if the error range is less than a defined congestion threshold, determine that the two paths have no congestion. The method of claim 9, And if it is determined that there is no congestion between the two paths as a result of the determination of (Dc), selecting one path having the least hop among the plurality of paths and transmitting a response message (RREP) to the source node. Dynamic load balancing routing method. The method of claim 9, The node difference threshold value is defined by the relationship between the communication delay time due to the increase in the number of hops and the communication delay time according to the degree of congestion between nodes, the dynamic load balancing routing method. The method of claim 1, wherein step (D) Detecting a first minimum valid buffer and a second minimum valid buffer through the buffer information of the path request message respectively input to the first path and the second path; A first determination step of determining whether the corresponding path is congested by comparing the detected first and second minimum valid buffers with a predefined congestion threshold value; Calculating an error range based on a difference between the first minimum valid buffer and the second minimum valid buffer when it is determined that the congestion state is congested; A second determination step of determining a degree of congestion between two paths by comparing the calculated error range with a predefined node difference threshold value; And if it is determined that the degree of congestion between the two paths is severe, selecting one path having the maximum value of the least valid buffer among the plurality of paths and transmitting a response message (RREP) to the source node. Dynamic load balancing routing method. The method of claim 13, wherein the first determination step And determining that the corresponding path is congested when the minimum valid buffer is less than a defined congestion threshold. The method of claim 13, And if it is determined that the traffic is not congested, selecting one path having the least hop among the plurality of paths and transmitting a response message (RREP) to the source node. Balancing routing method. The method of claim 13, wherein the second determination step And if the error range is less than a defined congestion threshold, determine that the two paths have no congestion. The method of claim 13, And if it is determined that there is no congestion between the two paths, selecting one path having the least hop among the plurality of paths and transmitting a response message (RREP) to the source node. Dynamic load balancing routing method.

Images