Network system for establishing path using redundancy degree and method thereof

• US 20050157697A1
• Filed: 01/18/2005
• Published: 07/21/2005
• Est. Priority Date: 01/20/2004
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Lee, Ji-hoon, Kim, Jung-ho, An, Sun-shin, Noh, Won-jong
• Granted Patent: US 7,394,776 B2
• Time in Patent Office: Days
• US Class Current: 370/349
• CPC Class Codes: H04L 45/128 for finding disjoint paths
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 45/36 Backward learning
• CPC Class Codes: H04W 40/28 for reactive routing

Abstract

A method for establishing a path between nodes in a wireless network system. A source node broadcasts a route request (RREQ) packet for a destination node. A mobile node between the source node and the destination node, upon receiving the RREQ packet, appends a redundancy degree with respect to an adjacent node to the RREQ packet and broadcasts the RREQ packet. The destination node selects an optimal path by checking the redundancy degree received along each path when the RREQ packet is received along multiple paths, and the destination node establishes an optimal path to the source node by transmitting a route reply (RREP) packet along the optimal path. Accordingly, the path is established suitable for the quality of service of data to be transmitted and a lost path is promptly recoverable by reference to information stored at each mobile node identifying redundant paths available to the mobile node.

Claims

1. A method of establishing a communication path between nodes in a wireless network system comprising a plurality of nodes, one of which operates as a source node, one or more of which operate as mobile nodes, and another of which operates as a destination node receiving a message from the source node, the method comprising:

broadcasting a route request (RREQ) packet from the source node for the destination node;

receiving the RREQ packet at one or more of the mobile nodes, appending a redundancy degree with respect to an adjacent node to the RREQ packet at each mobile node and broadcasting the RREQ packet from each mobile node for the destination node along one or more paths;

selecting an optimal path at the destination node by checking the redundancy degree contained in the RREQ packet received along each path when the RREQ packet is received along at least one path; and

establishing the communication path to the source node by transmitting a route reply (RREP) packet along the optimal path.

2. The method of claim 1, further comprising:

calculating the redundancy degree at each mobile node by checking a temporal association, a spatial association, and a mobility with respect to an adjacent node of the respective mobile node.

3. The method of claim 1, wherein the receiving of the RREQ packet at each mobile node comprises:

determining a redundant reception of the RREQ packet by the mobile node receiving the RREQ packet;

registering the adjacent node transmitting the RREQ packet as an upstream node when the RREQ packet is not received redundantly; and

appending the calculated redundancy degree in relation to the registered upstream node to the RREQ packet.

4. The method of claim 3, wherein the receiving of the RREQ packet at each mobile node further comprises:

registering the adjacent node transmitting the RREQ packet as a redundant upstream node when the RREQ packet is received redundantly; and

dropping the redundantly received RREQ packet.

5. The method of claim 4, wherein the establishing of the communication path comprises:

transmitting the RREP packet from the destination node for the source node along the selected path;

registering the node transmitting the RREP packet as a downstream node when a first mobile node on the selected path receives the RREP packet; and

forwarding the RREP packet from the first mobile node to a registered upstream node if the first mobile node is not the source node.

6. The method of claim 5, wherein the establishing of the communication path further comprises:

determining whether there is a registered redundant upstream node relative to the first mobile node; and

transmitting a redundant route reply (RRR) packet to the redundant upstream node if there is the redundant upstream node.

7. The method of claim 1, further comprising:

including a quality of service (QoS) information required for data transferred from the source node in the RREQ packet.

8. The method of claim 7, wherein the selecting of the optimal path at the destination node comprises:

receiving at least one RREQ packet at the destination node over a certain standby time;

checking the QoS information and the redundancy degree with respect to each received RREQ packet at the destination node; and

selecting the optimal path among the paths of the RREQ packet transmission based on the QoS information and the redundancy degree in each received RREQ packet.

9. The method of claim 8, wherein the selecting of the optimal path further comprises:

setting the standby time by checking the QoS information contained in the RREQ packet first received at the destination node.

10. The method of claim 1, further comprising:

detecting disconnection of a second mobile node and a registered downstream node on the path between the source node and the destination node;

determining, at the second mobile node, whether there is a redundant path to the downstream node by checking the redundancy degree of the second mobile node; and

recovering the path between the source node and the destination node using the redundant path when there is the redundant path.

11. The method of claim 10, further comprising:

transmitting to a failure notification (FN) packet from the second mobile node to a registered upstream node indicating the path loss when it is determined that there is no redundant path; and

recovering the lost path at the upstream node using the redundant path when there is the redundant path by checking the redundancy degree.

12. The method of claim 11, wherein further comprising:

determining whether the FN packet is transmitted from a node being used when the FN packet is received; and

deleting the redundancy degree for a node when the FN packet is transmitted from the node not being used.

13. The method of claim 1, further comprising:

calculating the redundancy degree in accordance with the following equation;

Rd(i,j)=|{kε

{Mr(i)∩

Sr(i)}|T_link(i,j)^e≦

T_link(i,k)^e},

wherein i, j, and k respectively are the mobile nodes, Rd(i,j) is the redundancy degree between nodes i and j, Mr(i) is an adjacent node moving toward the node i, Sr(i) is an adjacent node having a spatial association with the node i, and T_link(i,j)^e is an expected time of the path establishment between the node i and the node j.

14. The method of claim 13, further comprising:

selecting the optimal path in accordance with the following equations;

$\mathrm{Redundancy}\left(p\right)=\underset{\mathrm{link}<br><br>\left(i,j\right)\in <br><br>\mathrm{path}<br><br>\left(p\right)}{\overset{{\mathrm{argmax}}_{\mathrm{path}<br><br>\left(p\right)\in <br><br>\mathrm{paths}<br><br>\left(\mathrm{src},\mathrm{dst}\right)}<br><br>\left\{\mathrm{Redundancy}<br><br>\left(p\right)\right\}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left\{\min <br><br>\left\{\mathrm{Rd}<br><br>\left(i,j\right),\mathrm{UpperLimit}\right\}\right\},$

wherein Redundancy(p) is a redundancy degree of a path p, arg max is a function for selecting a path having a largest Redundancy(p) among paths between the source node src and the destination node dst, UpperLimit is a maximum value of the redundancy degree, and Rd(i,j) is a redundancy degree between the node i and the node j.

15. The method of claim 11, wherein the recovering of the lost path at the upstream node comprises:

selecting an optimal redundant path among redundant paths in accordance with the following equations;

$\begin{array}{c}{\mathrm{Rd}}_n<br><br>\left(p\right)=<br><br>\frac{\underset{\mathrm{link}<br><br>\left(i,j\right)⋐<br><br>p}{\overset{\text{\hspace{1em}<br><br>}}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{Rd}}_r<br><br>\left(i,j\right)}{<br><br>p<br><br>}\\ {\mathrm{Rd}}_r<br><br>\left(i,j\right)=<br><br>\mathrm{\alpha <br><br>}\times <br><br>{\mathrm{Tr}}_r<br><br>\left(i,j\right)+\mathrm{\beta <br><br>}\times <br><br>{\mathrm{Mr}}_r<br><br>\left(i,j\right)\\ {\mathrm{Tr}}_r<br><br>\left(i,j\right)=<br><br>\min <br><br>\left\{\frac{T_{\mathrm{link}<br><br>\left(i,j\right)}^e}{T_{\mathrm{data}<br><br>\left(i\right)}^e},1\right\}\\ {\mathrm{Mr}}_r<br><br>\left(i,j\right)=<br><br>{\mathrm{e<br><br>}}^{-<br><br>v_{i,j}<br><br>}\times <br><br>I_{\mathrm{mr}<br><br>\left(i,j\right)},\end{array}$

wherein Rd_r is a redundancy degree of the redundant paths excluding a main path, |p| is a total number of links on the path p, Rd_n(p) is a generalized value of Rd_r, Mr_r(i,j) and Tr_r(i,j) respectively are functions for calculating a mobile scale and a temporal association scale of a link between the node i and the node j, I_mr(i,j) is a mobile scale function of the nodes i and j, and α and

β

respectively are weight functions for the temporal association and the mobility.

16. A mobile node for establishing a communication path between a source node and a destination node, the mobile node comprising:

a calculator to calculate a redundancy degree for the mobile node with respect to at least one node adjacent to the mobile node;

a packet receiver to receive a route request (RREQ) packet transmitted by the source node or another mobile node;

a controller to register the transmitting node as an upstream node and append the redundancy degree to the RREQ packet; and

a packet transmitter to broadcast the RREQ packet having the appended redundancy degree for the destination node.

17. The mobile node of claim 16, further comprising a storage to store the redundancy degree and information on the registered upstream node.

18. The mobile node of claim 17, wherein the controller registers the transmitting node as a redundant upstream node where the RREQ packet is redundantly received by the mobile node.

19. The mobile node of claim 18, wherein the controller:

compares a node ID of the mobile node with a destination node ID contained in the received RREQ packet, and

recognizes the mobile node as the destination node if the mobile node ID and the destination node ID are identical.

20. The mobile node of claim 19, wherein:

where the receiving node is recognized as the destination node and the destination node receives the RREQ packet via a plurality of paths, the controller selects an optimal path from among the plurality of paths by checking a quality of service (QoS) information and the redundancy degree contained in the respective RREQ packets.

21. The mobile node of claim 20, wherein:

where the receiving node is the destination node, the packet transmitter transmits a route reply (RREP) packet to a registered upstream node on the selected optimal path.

22. The mobile node of claim 18, wherein:

the packet receiver receives a route reply (RREP) transmitted by the destination node or yet another node; and

the controller registers the node transmitting the (RREP) packet as a downstream node and controls the packet transmitter to transmits the RREP packet to the registered upstream node.

23. The mobile node of claim 22, wherein the controller controls the packet transmitter to transmit a redundant route reply (RRR) packet to the redundant upstream node when the redundant upstream node is registered by the mobile node.

24. The mobile node of claim 23, wherein the controller registers the node transmitting the RRR packet as a downstream node, appends the redundancy degree to the RRR packet, and controls the packet transmitter to transmit the RRR packet to the upstream node.

25. A wireless network system comprising:

a source node to broadcast a route request (RREQ) packet for path establishment;

at least one mobile node to calculate and store a redundancy degree with respect to an adjacent node, append the redundancy degree to the RREQ packet when the RREQ packet is received, and broadcast the RREQ packet; and

a destination node to receive the RREQ packet via a plurality of paths and select an optimal path from among the plurality of paths by checking the redundancy degree of the RREQ packet received via at least one of the plurality of paths and to transmit a route reply (RREP) packet to the source node along the optimal path.

26. The wireless network system of claim 25, wherein the mobile node determines whether the RREQ packet is received redundantly, and if the RREQ packet is not redundantly received, the mobile node registers an adjacent node transmitting the RREQ packet as an upstream node and broadcasts the RREQ packet for the destination node.

27. The wireless network system of claim 26, wherein the mobile node registers the adjacent node transmitting the RREQ packet as a redundant upstream node and drops the RREQ packet when the RREQ packet is received redundantly.

28. The wireless network system of claim 27, wherein the destination node sets a standby time by checking a quality of service (QoS) information contained in the RREQ packet first received, and selects the optimal path from the paths of the RREQ packet transmission within the standby time.

29. The wireless network system of claim 27, wherein the mobile node registers an adjacent node transmitting the RREP packet as a downstream node and forwards the RREP packet to a registered upstream node.

30. The wireless network system of claim 29, wherein the mobile node transmits a redundant route reply (RRR) packet to a redundant upstream node when there is the registered redundant upstream node.

31. The wireless network system of claim 30, wherein, when the mobile node detects a lost path to the downstream node, the mobile node recovers the lost path using a redundant path to the adjacent node by checking the redundancy degree.

32. The wireless network system of claim 31, wherein the mobile node transmits to the registered upstream node a failure notification (FN) packet indicating the path loss when there is no redundant path.

33. A packet transceiver comprising:

a calculator which calculates a redundancy degree based on a temporal association, a spatial association and a mobility association of the packet transceiver with respect to a node which transmits a route request (RREQ) packet having a packet ID, a destination ID and a quality of service (QoS) information;

a controller which registers the transmitting node as an upstream node, and appends the calculated redundancy degree to the RREQ packet; and

a packet transmitter which transmits the RREQ packet having the appended redundancy degree.

34. The packet transceiver of claim 33, wherein:

if the RREQ packet is received from the transmitting node and another node, the controller registers the node from which the RREQ packet is first received as a primary upstream node, registers a node from which the RREQ packet is later received as a redundant upstream node, and transmits the first received RREQ packet.

35. A packet transceiver, comprising:

a packet receiver which receives one or a plurality of route request (RREQ) packets, each RREQ packet having a packet ID, a destination ID, a quality of service (QoS) information and an appended redundancy degree based on respective temporal, spatial and mobility associations of other packet transceivers which forward the RREQ packets;

a controller which;

checks whether a node ID of the receiving packet transceiver corresponds to the destination ID, and

determines an optimal communication path based on the appended redundancy degree and the QoS information, if the node ID corresponds to the destination ID; and

a packet transmitter which transmits a route reply (RREP) packet on the optimal communication path, if the node ID corresponds to the destination ID.

36. The packet transceiver of claim 35, wherein the controller:

determines the optimum communication path as a path having a smallest number of intermediate nodes where the QoS information indicates a swift communication is required; and

determines the optimum communication path as a path having a greatest number of redundant paths where the QoS information indicates that a stable communication is required.

37. A packet transceiver which operates as one of a plurality of nodes in a wireless system, the packet transceiver comprising:

a storage which stores respective redundancy degrees based on respective temporal associations, spatial associations and mobility associations of the packet transceiver with respect to other nodes which transmits a route request (RREQ) packet having a packet ID and a quality of service (QoS) information via the packet transceiver in route to a destination node; and

a controller which uses the stored redundancy degree to complete a communication path in response to a reply route (RREP) packet transmitted from the destination node toward a source node, wherein, where a main route to one of the other nodes, which main route is specified in the RREP packet based on the QoS information, is lost, the controller selects a redundant route based on the stored redundancy degree.

38. A method of establishing a communication path between a first mobile node operating as a source node and a second mobile node operating as a destination node, the communication path established through one or more mobile nodes operating as intermediate nodes, the method comprising:

forwarding a route request (RREQ) packet from the source node to the destination node via one or a plurality of the intermediate nodes, the RREQ packet having a packet ID and a quality of service (QoS) information;

appending a redundancy degree to the RREQ packet at each intermediate node;

storing information at each intermediate node indicating other nodes from which the RREQ packet is received;

determining an optimal communication path at the destination node based on the respective appended redundancy degrees of the RREQ packets received at the destination node and the QoS information; and

transmitting a route reply (RREP) packet identified to the packet ID on the optimal communication path.

39. The method of claim 38, further comprising:

determining the optimal communication path as a path having a smallest number of intermediate nodes where the QoS information indicates a swift communication is required; and

determining the optimal communication path as a path having a greatest number of redundant paths where the QoS information indicates that a stable communication is required.

40. The method of claim 38, further comprising:

basing the redundancy degree on respective temporal, spatial and mobility associations of the intermediate nodes which forward the RREQ packet toward the destination node.

41. The method of claim 38, further comprising:

forwarding the RREP from the intermediate nodes toward the source node based on the information stored at each intermediate node identifying the other nodes from which the RREQ packet corresponding to the packet ID was received in route to the destination node.