KR100749518B1 - Routing method for mobile ad hoc network based on routing table using clustering - Google Patents

Abstract

A routing method in a table-based mobile ad hoc network using clustering is provided to be capable of reflecting changed information only upon a control message used for forming topology, thereby reducing a control overhead and shortening a data transmission path through adaptive routing. Each cluster head generates predetermined control messages for setting a data transmission path by referring to self global routing tables, and transmits the control messages to other nodes(S110). The nodes update self global routing tables and local routing tables to form topology of a mobile ad hoc network which becomes a basis of the data transmission path(S120). The data transmission path is shortened by the formed topology through adaptive routing(S130).

Description

Routing method for mobile Ad hoc network based on routing table using clustering}

1 is a flowchart of a routing method in a table-based mobile ad hoc network using clustering according to an embodiment of the present invention;

2 is a block diagram of a mobile ad hoc network according to an embodiment of the present invention.

The present invention relates to a routing method on a mobile ad hoc network, and more particularly, to a routing method in a table-based mobile ad hoc network using clustering that can reduce control overhead and improve convergence speed of table information.

A mobile ad hoc network refers to a network configured autonomously by mobile nodes in a place without a fixed infrastructure. Since the transmission distances of mobile nodes should be limited in consideration of energy consumption and spectral efficiency, communication between mobile nodes far away For this purpose, multi-hop communication is used.

Such a mobile ad hoc network requires a routing method that can efficiently maintain or maintain a path in a dynamic topology because the topology may change from time to time due to the nature of the mobility of nodes.

Conventional routing methods used in such mobile ad hoc networks include on-demand and proactive methods, such as Dynamic Source Routing (DSR) or Ad hoc On-Demand Distance Vector (AODV). The request-based method does not always maintain the entire path to all mobile nodes in the network, but searches for the path and performs data transmission only when data transmission is required.

Therefore, such a request-based method has a problem that a temporary delay occurs during the path discovery time and a control packet for path discovery needs to be flooded to all or part of the network, thus causing temporary network overload and interrupting communication of other sessions. .

In addition, table-based methods such as Destination-Sequence Distance-Vector (DSDV) and Wireless Routing Protocol (WRP) broadcast their path information periodically or when the network topology changes, regardless of whether or not each node transmits data. This ensures that each node keeps up-to-date path information for the other nodes.

In this table-based scheme, since each node holds path information of other nodes, it is possible to transmit data without unnecessary steps of path searches. However, since a control message must be transmitted for the maintenance of the route table, unnecessary communication resources are wasted, and the control overhead is greatly increased in proportion to the number of nodes.

SUMMARY OF THE INVENTION The present invention has been made to solve the above problems, and an object thereof is to provide a routing method in a table-based mobile ad hoc network using clustering that can prevent network overload or waste of communication resources using a clustering scheme. There is this.

Other objects and advantages of the invention will be described below and will be appreciated by the embodiments of the invention. In addition, the objects and advantages of the present invention can be realized by means and combinations indicated in the claims.

The present invention for achieving the above object is a routing method of a mobile ad hoc network consisting of a cluster of mobile ad hoc nodes and a plurality of cluster heads that are nodes managing each cluster, each cluster head having its own global routing table. A control message transmission step of generating a predetermined control message for setting a data transmission path with reference to the other node and transmitting the generated control message to other nodes; A topology forming step of updating a global routing table and a local routing table of the node receiving the predetermined control message to form a topology of a mobile ad hoc network that is the basis of a data transmission path; And a path shortening step of shortening a data transmission path by the topology formed in the topology forming step through adaptive routing.

In addition, it is preferable to further include a path shortening step of shortening the data transmission path through adaptive routing.

Here, the predetermined control message may be generated periodically or generated when there is a change in topology.

Further, the predetermined control message is preferably generated including the changed information in the global routing table managed by each cluster head.

In addition, in the path shortening step, all nodes have the same global routing table as the corresponding cluster head of the cluster to which they belong, so that the data transmitted between each node is formed through the global routing table held by the node without passing through the cluster head. Is preferably sent to.

In addition, it is more preferable that the predetermined control message is transmitted through the plurality of bridges and continuously delivered up to three hops.

Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings. Prior to this, terms or words used in the present specification and claims should not be construed as being limited to the common or dictionary meanings, and the inventors should properly explain the concept of terms in order to explain their invention in the best way. Based on the principle that can be defined, it should be interpreted as meaning and concept corresponding to the technical idea of the present invention.

Therefore, the embodiments described in the specification and the drawings shown in the drawings are only the most preferred embodiment of the present invention and do not represent all of the technical idea of the present invention, various modifications that can be replaced at the time of the present application It should be understood that there may be equivalents and variations.

Hereinafter, FIG. 1 is a flowchart illustrating a routing method in a table-based mobile ad hoc network using clustering according to an embodiment of the present invention, and FIG. 2 illustrates a configuration of a mobile ad hoc network according to an embodiment of the present invention. This will be described with reference.

According to a table-based mobile ad hoc routing method using clustering according to an embodiment of the present invention, first, a cluster head, which is a node for managing a cluster (), which is a group of mobile ad hoc nodes, transmits data on a mobile ad hoc network. A predetermined control message for updating the data transmission path is generated by referring to its own global routing table including routing information for transmitting the predetermined control message to other nodes on the mobile ad hoc network (S110).

The predetermined control message may be periodically generated and transmitted, or may be generated and transmitted when there is a change in topology due to the loss or movement of a specific node.

At this time, the structure of a predetermined control message according to an embodiment of the present invention is shown in Table 1.

[Table 1] Structure of a control message according to an embodiment of the present invention

 ureq_src  ureq_src_seq  ureq_id  ureq_forwarder  hop_count  route_info  13  120  xx  13  0 Changed Global Routing Table on Clusterhead 13

Here, the ureq_src, ureq_src_seq, and ureq_id fields each include a node generating a control message, a sequence number counted each time ureq_src generates a control message, and an information value for assigning uniqueness to the control message to avoid duplicate reception of the control message. Means.

According to the present invention, in selecting a path using the control message, a path for transmitting a control message having a large sequence number (which has a more recent sequence number) is selected, and if the sequence number is the same, hop_count (the number of hops). Select a path with a shorter distance.

In addition, in the present invention, when a control message is received, ureq_src and ureq_id are examined in the fields of the received control message, and when a control message having the same ureq_src and ureq_id values is received, the received message is removed.

In addition, the ureq_fowarder and hop_count fields each indicate how far the control message has been moved from the previous node that sent the control message to it, and ureq_src, and has a different value for each node.

In addition, the route_info field contains the changed information in the global routing table of the cluster head that generated the control message.

Thus, in the present invention, the size of the control message is greatly reduced by including only the changed information in the global routing table managed by each cluster head without including the information in the routing table for all paths in the control message.

In addition, the predetermined control message is transmitted through a bridge connecting the cluster heads, and is preferably continuously transmitted to neighboring nodes within three hops.

By continuously transmitting control messages, the convergence time of routing table information can be much shorter than the conventional method of waiting for a period allocated to each node and delivering only to nodes one hop away from each node.

Next, the node receiving the predetermined control message updates its global routing table or local routing table to form a topology of the mobile ad hoc network (S120).

Hereinafter, an operation of updating the local routing table by each node and an operation of updating the global routing table by each cluster head will be described.

First, in the process of updating the local routing table, each node receives a predetermined control message transmitted from the cluster head, and checks whether there is an entry for the transmitting cluster head transmitting the predetermined control message in its local routing table. Review.

Then, if there is no entry for the transmitting clusterhead in its local routing table, the transmitting clusterhead is added to the entry to establish the reverse link.

At this time, if the node receiving the predetermined message is a bridge, it transmits a control message, and if it is a cluster head, it updates its global routing table.

Next, in the process of updating the global routing table, the clusterhead receives the control message and examines whether there is an entry for the transmitting clusterhead that has transmitted the predetermined control message in its global routing table.

Then, if there is no entry for the sending clusterhead in its global routing table, add the sending clusterhead to the entry, and if there is an entry for the sending clusterhead, the received control message Compares the sequence number in the entry with the sequence number in its own entry.

If the sequence number of the received control message is larger or the sequence number of the received control message is the same as the sequence number in its entry, but the distance of the control message is short (the shorter path exists). Updates the global routing table according to the received message.

Table 2 and Table 3 show the structure of the local routing table and the global routing table updated through the above method, respectively.

[Table 2] Structure of the regional routing table according to an embodiment of the present invention

 Next node  Distance (hops)  UREQ_ID  13  One  xx

[Table 3] Structure of the global routing table according to an embodiment of the present invention

 Destination clusterhead (destCH)  Next clusterhead (nextCH)  Distance (hops)  Cluster member node set  Sequence Number (Seq.No)  0  9  2  One  120  2  9  6  17  110  3  9  4  12  124  4  4  3  5, 6, 7, 8  116  9  9  2  10, 11, 15  114  13  13  0  14, 16  110  18  9  5  19  110

In this case, Table 2 is a local routing table that the bridge node '15' received and updated a predetermined control message broadcast by the cluster head '13' among the components of the present invention shown in the configuration diagram of FIG. 1 is a global routing table of the cluster head '13' among the components of the present invention shown in the configuration diagram of FIG.

On the other hand, the present invention can reduce the data transmission path by the topology formed in the 'S120' step through the adaptive routing (S130).

Hereinafter, the data transmission path in the present invention will be described with reference to FIGS. 1 and 3, and an example of transmitting data before the path is shortened by the adaptive routing will be described.

First, when data is transmitted from the member node 16 of the cluster head 13 to the destination node 19, the member node 16 transmits data to the cluster head 13, which is its cluster head.

Clutterhead '13' then searches for the existence of destination node '19' in its global routing table. In this example, as shown in FIG. 5, the destination cluster head which is the cluster head including the destination node '19' is the cluster head '18', and the cluster head '13' is the next cluster head which is the cluster head for transmitting the data to the destination cluster. The data is sent to head '9'. Thereafter, the data is transmitted from the cluster head '9' to the destination node along the local paths 9, 5 and 19.

Thus, before the transmission path is shortened, six hops of '16', '13', '15', '9', '5', and '19' are used to transfer data from the node '16' to the destination node '19'. Had to go through.

Next, let's look at how to shorten the path by adaptive routing and the result.

In order to shorten the path by adaptive routing, it is first assumed that all nodes except the clusterhead also have a global routing table.

Thereafter, each node updates its global routing table by reflecting the predetermined control message when the predetermined control message transmitted to form the topology in step S120 is transmitted through itself. It will have the same global routing table as the corresponding clusterhead of the cluster to which it belongs.

Therefore, when transmitting data, each node can transmit data without going through the cluster head by using its own global routing table, thereby shortening the data transmission path.

Here, the process of updating the global routing table is the same as the operation of updating the global routing table by the cluster head described above.

Hereinafter, when the adaptive routing is applied, the shortened path from the node '16' to the destination node '19' will be described as described above.

First, the node '16' uses its global routing table to know that the next cluster head, '9', is two hops away from the cluster head. Send data to head '9'.

Then, when node '15' in the direction of being transmitted to clusterhead '9' receives data in the middle, node '15' also transmits the data to clusterhead '18' using its global routing table.

Again, if node '5' in the direction of being transmitted to cluster head '18' receives data in the middle, node '5' also transmits the data to node '19' which is the destination node using its global routing table. do.

As such, when the transmission path is shortened, data can be transmitted through only four hops of '16', '15', '5', and '19' in order to transmit data from the node '16' to the destination node '19'. .

By using adaptive routing through the above method, not only the transmission path is shortened, but also the data can be transmitted without passing through the cluster head, thereby reducing the congestion in the cluster head.

On the other hand, since there are a plurality of bridges that are nodes connecting the cluster heads between the cluster heads, in the present invention, when any one or more of the one or more bridges are moved or destroyed, a change occurs in the topology. Alternatively, the path is restored by replacing the data transmission path by the moved or destroyed bridge by using the multipath formed through the other bridge except the destroyed bridge (S140).

By using the multipath formed through the other bridges except the moved or destroyed bridges, there is an advantage that the network can be operated without additional recovery process.

As mentioned above, although this invention was demonstrated by the limited embodiment and drawing, this invention is not limited by this, The person of ordinary skill in the art to which this invention belongs, Of course, various modifications and variations are possible within the scope of equivalents of the claims to be described.

According to the present invention, the control overhead is reduced by reflecting only the changed information in the control message used for forming the topology.

In addition, since the control message is continuously transmitted up to 3 hops, the convergence time of the routing table information can be much shorter than that of the conventional method.

Furthermore, adaptive routing can shorten the data transmission path and reduce cluster head congestion.

Claims (6)

A routing method of a mobile ad hoc network comprising a cluster that is a group of mobile ad hoc nodes and a plurality of cluster heads that manage each cluster. A control message transmission step of each cluster head generating a predetermined control message for setting a data transmission path by referring to its own global routing table and transmitting the same to other nodes; A topology forming step of updating a global routing table and a local routing table of the node receiving the predetermined control message to form a topology of a mobile ad hoc network that is the basis of a data transmission path; And A routing method in a table-based mobile ad hoc network using clustering comprising a path shortening step of shortening a data transmission path by a topology formed in the topology forming step through adaptive routing. The method of claim 1, When there is a change in the topology formed through the topology forming step due to the movement or disappearance of any one or more bridges connecting each cluster head, use a multipath formed through other bridges except the moved or destroyed bridges. And restoring a path by replacing a data transmission path by the moved or destroyed bridge, thereby recovering the path. The method of claim 1, wherein the predetermined control message, A routing method in a table-based mobile ad hoc network using clustering, which is generated periodically or when there is a change in topology. The method of claim 1, wherein the predetermined control message, A routing method in a table-based mobile ad hoc network using clustering, wherein the clustered head is generated by including changed information in a global routing table managed by each cluster head. According to claim 1, wherein the path shortening step, Every node has the same global routing table as its clusterhead in its cluster, A method for routing in a table-based mobile ad hoc network using clustering, in which data transmitted between nodes is transmitted through a global routing table owned by the node rather than through a cluster head. The method of claim 2, wherein the predetermined control message, A routing method in a table-based mobile ad hoc network using clustering, which is delivered through the plurality of bridges and is continuously delivered up to three hops.

Images