Method for discovering route from source node to destination node

The present invention relates to a wireless network, and more particularly to searching for a route in an ad hoc network.

An ad hoc network is a collection of communication nodes that are not centrally managed like a conventional network. Moreover, the topology of ad hoc networks changes frequently. Nodes move in and out of the network at will, and the nodes in the network provide dynamic routing. Nodes are often mobile (wireless) and have limited resources.

Common applications for ad hoc networks are military command and control, exploration and rescue, sensors, and disaster relief, offices, university campuses, homes, mobile radio data networks, and these and other life or security / safety. Includes operations with numerous other mission-critical resources in network deployments that require close attention.

Before nodes in an ad hoc network can communicate with each other, they must first find a route. The ad hoc on-demand distance vector (AODV) protocol routes only when requested. See "Ad hoc On-Demand Distance Vector Routing" by Perkins et al. (Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, pp.90-100, February 1999).

This can be done as follows. When the source node has a packet to send to the destination node but does not have a route to that destination node, the source node broadcasts a route request (RREQ) packet. The packet specifies the destination and a unique RREQ broadcast identifier. Eventually, the destination node receives the request packet and responds with a route response packet. The normal data packet can only be forwarded after the source node receives the response packet.

During operation, the route cache needs to be maintained as nodes enter and exit the network. This requires a significantly complex routing algorithm and a fairly large route cache.

<p> It is desirable to provide ad hoc routing for nodes that is not as complex as prior art routing algorithms.</p>

<p> An ad hoc network by causing the source node to generate a data packet containing the source address, the destination address, and a field instructing the source node to request route information from the source node to the destination node. The route from the source node to the destination node is searched for in.</p><p> The data packet is forwarded through the network until it is received by the destination node. In response, the destination node generates a route response packet containing route information.</p><p> The route information can include costs. Route response packets are forwarded through the network until they are received by the source node.</p><p> During the transfer, multiple route response packets with varying costs can be generated. The source node can then perform a cost calculation and select the best route based on that cost.</p>

Node Definition The ad hoc wireless communication network according to the present invention includes a plurality of nodes. Each node is equipped with a radio for transmitting and receiving data and control packets.

Two types of nodes are defined in the present invention, namely simple routing nodes (RN-) and complex routing nodes (RN +), which are distinguished by their complexity and routing function. RN-Nodes are very simple devices with limited resources, such as memory and processing power. RN-Nodes are not used to perform complex routing processes. RN + nodes have much more memory and processing power and can therefore execute routing algorithms. The RN + node can also use the route cache to hold routing information.

The network 100 of the present invention is composed of heterogeneous nodes and includes RN + and RN-nodes that are uniformly distributed. That means that any node has approximately equal numbers of adjacent RN + and RN-nodes. All that is required of the nodes of the invention is to generate and forward data and RREP packets. The nodes of the present invention are not required to understand or process prior art RREQ packets. Since the present invention does not use RREQ packets, it enables a fast, inexpensive, simple, and good ad hoc network.

Here, the operation of the RN-node regarding routing will be described. Since the RN-node does not store routing information, the RN-node routes the packet using a simple process that does not need to be stored. This is done by a method known as "tree routing".

Figure 1 shows network 100, with nodes (A through G, X and Z) arranged as a tree, specifically limited spanning. Node 101 is the source node and node 102 is the destination node. To enable tree routing, all nodes in Network 100 have a limited understanding of the network topology. That is, the node knows the tree structure 100 that defines the network in a parent / child relationship. Line 103 connecting the nodes shows the relationship. Line 103 indicates a potential communication link or hop. Multiple hops form a route.

Each node can determine whether another node is an ancestor, a descendant, or neither an ancestor nor a descendant. In the exemplary network 100, node E is the parent of node B, i.e. similarly, node B is a child of node E. In addition, node D has offspring nodes X and A and an ancestor node G. All other nodes are neither descendants nor ancestors of node D. All nodes that have a common parent node are considered "clusters", for example, node CZF, node XAD and node BEG form a cluster.

For this topology, the method according to the invention routes packets between nodes according to a tree structure. As an example of this routing, the source node X101 needs to send a data packet to the destination node Z102. Node X determines that node Z is neither a descendant nor an ancestor, and simply "ups" the tree and forwards the packet to its parent node D. Node D also determines that node Z is neither a descendant nor an ancestor, and goes up the tree and forwards the packet to its parent node G.

Note that Node G is still known as the "root" of Tree 100. The root node knows all offspring nodes and can therefore act as a coordinator node.

Node G determines that Node Z102 is its descendant. Therefore, node G forwards the packet down the tree to its child node F. Node F also forwards the packet to destination Z102. The entire route from node X to node Z is X-&gt; D-&gt; G-&gt; F-&gt; Z. This type of routing is called "tree routing" and is based solely on the topology defined by the parent / child relationship.

The RN-node of the present invention stores only its own parent / child relationship. From this information, the RN-node can determine if the other node is an ancestor or a descendant. In this way, a network containing only RN-nodes can route packets to any other node in the network.

The problem with this approach is that the route is not determined on the basis of cost, but only on the basis of the parent / child relationship. That is, here there are ways to improve routes and nodes other than forwarding packets based on parent or child nodes.

Several routing methods are known for routing packets through wireless networks. Most of these methods are based on simple metrics such as the number of "hops" or "energy" consumed during packet transmission.

One example of such a technique is the AODV routing algorithm. In AODV, the source node X101 starts by searching for a route to the destination node Z102 by broadcasting a route request (RREQ) packet. RREQ packets are forwarded through the network until they reach destination node Z. Destination node Z responds with a route response (RREP) packet. The route from node X to node Z is determined by an intermediate node that stores the cost for the route to node Z and the next hop while the RREQ and RREP packets are being forwarded.

In order to select the best route, the node must store information about the cost of searching for the route. The cost is stored in a routing table that holds the next hop and cost for a given destination node. Using this type of routing technique, a node can determine the best possible route for a given cost criterion.

Figure 1 shows that there are several possible paths from node X to node Z. For example, there are tree routes XDGFZ and routes XABCZ, XAECB. By using the additional memory and processing power available at the RN + node, all three of these paths can be searched and compared during the route search.

However, this technique is not available on RN-nodes. This can add some RN + nodes to the network to help find and utilize "more desirable" routes. Of course, in a network in which the RN- and RN + nodes according to the present invention are composed of heterogeneous nodes, the RN-node does not store the routing table, so it may not always be possible to search for the best route.

However, the present invention provides a solution to search for most of the optimal pathways, if any. Moreover, the present invention does not combine the routes exactly so that the node does not perform extra packet forwarding or overload the network with route-finding traffic, reducing available bandwidth. To do so.

Cost calculation of RREQ and RREP packets for route search In cost-conscious routing using RREQ, the source node starts a route request by broadcasting the RREQ packet. If the intermediate RN + node receives the RREQ packet, it rebroadcasts the packet if it does not have a route entry for the destination. By rebroadcasting in this way, a plurality of RREQ packets are generated. The RREQ packet arrives at the destination node in an unknown order after receiving various time delays depending on the route to which the packet travels, and then accumulating various costs.

As a result, as shown in Figure 2, the destination node generates another RREP packet each time it receives another cost RREQ packet that is lower than the previously known cost, and it is the source node. Unicast to. The overall effect is that the route search generates multiple RREQ packets 201 from the source node to the destination node and multiple RREP packets 202 from the destination node to the source node, with multiple source nodes. A cost calculation for the packet must be performed to determine the RREP route 203 used to send the data packet. Therefore, cost calculation of RREP packets as well as cost calculation of RREQ packets is indispensable for cost-effective route search.

Cost Calculation of RREP Packets for Route Search As shown in FIG. 3, the underlying concept of the present invention is to perform cost calculation only after receiving RREP packet 302. That is, only the source node is involved in performing the calculation and determining the best route.

This would result in lower network traffic compared to calculating the cost of both RREQ and RREP packets without degrading performance. The present invention also utilizes an existing tree structure in order to completely eliminate the need for RREQ packets during route search.

Instead of starting to route with RREQ packets, as in the prior art, the source node 101 of the present invention uses all the knowledge that the source node has about the network topology, eg, as described above, to use the data packet. Send 301 directly to destination node 102. Intermediate RN-Nodes forward data packets in the same way. The intermediate RN + node can forward the data packet to the destination node with additional routing information, or the intermediate RN + node can utilize the tree structure.

Upon receiving the data packet, the destination node generates RREP packet 302. The RN + node forwards RREP packets towards the source node 101, thus generating multiple RREP paths from the destination node to the source node. Upon arrival of the RREP packet, the source node chooses the best route 303 based on the cost of each route identified by the RREP packet 302. Subsequent data packets follow the chosen route.

The routing method of the present invention reduces network traffic much more than known prior art methods.

The routing method of the present invention utilizes a tree structure to first forward a data packet and then selects a better path, if any. The method of the present invention is simpler than the conventional AODV method in that it does not require RREQ packets and therefore requires fewer packets.

Packet Structure Figure 4 shows the data packet 400 and Figure 5 shows the RREP packet 500. Most of the fields and bits in these two packets have the same structure as before, except for the fields and bits described in more detail below. The upper line shows the number of bits or bytes, and the lower line shows the function of bits and bytes.

First, the source node sends the data packet 400 to the destination node along the tree path. For the first data packet, the "RREP request flag" field 401 is set to 1. This field allows the data packet to effectively act as a route request packet. The "next hop address" 402 is inserted by the forwarding node.

Upon receiving a data packet with the RREP request flag "on", the destination generates RREP packet 500. If the destination node is an RN-node, the RREP packet is unicast along the tree path and returned to the source node. RN-The destination node sets the "broadcast flag" bit 501 to 0 and puts its address in the "forwarding node address" field 502. The destination node sets the "destination address" field 503 to the address of the source node and the "source address" field 504 to the address of the source node of the data packet. The destination address and source address fields do not change when the RREP packet is forwarded to the source node. The "accumulated cost" 505 is updated as the packet is forwarded.

Packet Processing Depending on the node type RN + or RN-, the processing of RREP packets is slightly different. The present invention also assumes that both RN + and RN-nodes route packets using a routing tree.

The following rules describe how a node forwards RREP packets. RN-A node always puts RREP packets received from one node into another cluster. That is, the receiving node is an intermediate ancestor or offspring of the transmitting node.

As long as the RREP packet has a low cumulative cost based on RREP ID 506 and destination address 503, RN + will always broadcast the RREP packet.

By following this rule, RREP packets can be returned from the destination node to the source node across several routes. As the RREP packet crosses the network, the routing table is established by the RN + node that forwards the RREP packet. RN + uses the lowest cost route each time it forwards an RREP packet with a particular RREP ID from a particular destination node. The source node can receive multiple RREP packets. If the source node is an RN + node, the source node updates its routing table.

FIG. 6 shows the process followed when receiving a data packet (601). The node determines if it is the destination node (602). Determine if the RREP flag 401 is on (603). If on, determine if the node is an RN + node (604). If it is an RN + node, it broadcasts an RREP packet (605) and processes the data.

On the other hand, if it is not an RN + node, it unicasts the RREP packet to the parent node (607) and processes the data packet (608).

If the node is not the destination node, determine if the node is an RN + node (610). If it is an RN + node, it determines if its destination node is a descendant node (611). If it is not a descendant node, it determines if the entry exists in the routing table (612). Unicast the data packet, if it exists (613).

If the destination node is a descendant node, unicast the data packet to the child node (s) (620).

If the receiving node is neither a destination node nor an RN + node, determine if the destination node is a descendant node (630). If it is a descendant node, unicast the data packet to the child node (s) (620).

On the other hand, if it is not a descendant node, it is determined whether the data packet is from a child node (640). Unicast the data packet to the parent node if it is from a child node (641). Otherwise, the data packet is dropped (650).

Figure 7 shows the process that follows when an RREP packet is received (701). The node determines if it is an RN-node (702). If it is an RN-node, determine if it is the source node (703). If it is the source node, it discards the packet (704).

On the other hand, if the node is not an RN-node, it determines if the node is the source node (710). If it is a source node, record its route if its cost is low (711), otherwise discard its RREP packet (704).

On the other hand, if the node is not the source node, it is determined whether the cost is reduced. If the cost is not reduced, drop the RREP packet (704). On the other hand, when the cost is reduced, the route to the destination is recorded and the RREP packet is broadcast.

If the node is neither an RN-node nor a source node, it determines if the packet is from the parent node (730). If it is from the parent node, it determines if the source node is a descendant node (731), otherwise it discards the packet (704). If it is a descendant node, unicast its RREP packet to the child node (732).

If the RREP is not from the parent node, it determines if the packet is from a child node (740), otherwise it discards the packet (704). If it is from a child node, it determines if the destination node is a descendant node (750), otherwise it discards the packet (704). If it is a descendant node, unicast the RREP packet in its tree (760).

Although the present invention has been exemplified by preferred embodiments, it should be understood that various other modifications and modifications can be made within the spirit and scope of the invention. Therefore, the object of the appended claims is to cover all such modifications and modifications that fall within the true spirit and scope of the invention.

<figref num="1">It is a figure of the ad hoc network by this invention.</figref><figref num="2">It is a block diagram of the route search of the prior art.</figref><figref num="3">It is a block diagram of the route search by this invention.</figref><figref num="4">It is a block diagram of the data packet by this invention.</figref><figref num="5">It is a block diagram of the route response packet by this invention.</figref><figref num="6">It is a flow chart of the process for processing the data packet by this invention.</figref><figref num="7">It is a flow chart of the process for processing the route response packet by this invention.</figref>