Routing method for a wireless multi-hop network

• US 8,693,322 B2
• Filed: 02/21/2012
• Issued: 04/08/2014
• Est. Priority Date: 02/21/2012
• Status: Expired due to Fees

• Current Assignee: Yikun Zhang
• Original Assignee: Yikun Zhang
• Inventors: Zhang, Yikun
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): DUDA, ADAM K
• Application Number:
  US13/400,802
• Publication Number:
  US 20130215739A1
• Time in Patent Office: 777 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/235, 370/236, 709/231, 709/238, 709/239, 709/240
• US Class Current: 370/229
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04W 28/00 Network traffic management; Network resource management
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0289 Congestion control load shedding arrangements in network planning H04W16/08; performing reselection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/34 Modification of an existing route

Abstract

Disclosed is a routing method named lock routing for a wireless multi-hop network, which can be based on next-hop routing and source routing and named next-hop lock routing and source lock routing respectively. The routing method utilizes traffic packets to monitor the link quality and utilizes local broadcast to help a source node keep track of the varying network topology in order to update a route path to a destination node. In local broadcast, routing control messages can be forwarded by path nodes and neighbors of an old route path, which reduces the routing control overhead and enhances the network scalability. A route update process can be triggered by the link quality and the path node state and is used to maintain ongoing traffic flows and extend the network lifetime.

Claims

1. A method based on next-hop routing for nodes in a wireless multi-hop network, the network comprising a plurality of nodes that function as routers or hosts or both of them, the method comprising:

delivering traffic packets from a source node to a destination node through a old route path;

local broadcast of routing control messages is used to discover a new route path;

the routing control messages include route update messages;

a route update message contains an identification of the old route path, if the route update message is used to update the entire route path from the source node to the destination node;

the destination node local broadcast a route update message to the source node;

path nodes of the old route path, path neighbors of the old route path, and neighbors of the destination node are qualified for forwarding the route update message.

4. A method according to claim 1 or 2, wherein whether to trigger a route update process depends on route update parameters that include the link quality and the path node state;

a path node detects the link quality of the previous hop and its state during forwarding traffic packets, while the destination node detects the link quality of the last hop during receiving traffic packets;

if a route update parameter exceeds a threshold, a route update process can be triggered;

a path node checks the route update parameters to decide whether to trigger a route update process, or forwards the route update parameters to downstream nodes for the route update decision;

the destination node checks the link quality of the last hop for the route update decision;

within a period of time no more than one route update process from a initiator to a target node is launched.

5. A method according to claim 4, wherein the neighbor relationship with the destination node is set up by listening routing control messages sent by the destination node;

the neighbor relationship with the source node and path nodes is set up by overhearing traffic packets;

the neighbor relationship with the route path is set up by overhearing traffic packets on the route path;

the neighbor relationship is restricted by a valid neighbor duration or the link quality;

if a network node'"'"'s state exceeds a threshold, the node discards received route update messages that are triggered due to the path node state;

when a network node forwards a route update message, the network node updates the parameters related to the new route path in the route update message and its routing table;

the target node of route update messages depends on the latest route update message to update its routing table;

if multiple copies of the latest route update message arrive, the target node compares metrics of these new route paths to selectively update its routing table.

6. A method according to claim 1 or 2, wherein the routing control messages include local route request messages;

a local route request process comprising;

when a path node finds a broken link, the path node sends a route error message to the source node;

upon receiving the route error message, the source node broadcast a local route request message to the destination node;

path nodes of the old route path, path neighbors of the old route path, and neighbors of the destination node are qualified for forwarding the local route request message;

the neighbor relationship with the old route path is set up by overhearing traffic packets on the route path, while the neighbor relationship with the destination node is set up by listening routing control messages by the destination node;

the neighbor relationship is restricted by a valid neighbor duration;

upon receiving the local route request message, the destination node sends a route reply message back to the source node.

10. A method according to claim 1 or 2 or 3, wherein the source node sends dummy packets to the destination node if a time gap between two traffic packets in a traffic flow exceeds a threshold.

2. A method based on next-hop routing for nodes in a wireless multi-hop network, the network comprising a plurality of nodes that function as routers or hosts or both of them, the method comprising:

delivering traffic packets from a source node to a destination node through a old route path;

local broadcast of routing control messages is used to discover a new route path;

the routing control messages include route update messages;

a route update message contains a route update node list that indicates a part of the old route path to be updated, if the route update message is used to update a part of the old route path;

when a downstream path node detects a part of the old route path needs update, and makes sure a route update process has no overlap with other simultaneous route update processes initiated by other nodes, the path node initiates the route update process, in which the target node of the route update message is the most-upstream node in the route update node list;

the path nodes between the target node and the initiator and neighbors of the nodes in the route update node list are qualified for forwarding the route update message.

3. A method based on source routing for nodes in a wireless multi-hop network, the network comprising a plurality of nodes that function as routers or hosts or both of them, the method comprising:

delivering traffic packets from a source node to a destination node through a old route path;

local broadcast of routing control messages is used to discover a new route path;

the routing control messages include route update messages;

(a) a route update message is used to update the entire route path from the source node to the destination node, and contains an identification of the old route path;

the destination node local broadcast a route update message to the source node;

path nodes of the old route path, path neighbors of the old route path, and neighbors of the destination node are qualified for forwarding the route update message;

or

(b) a route update message is used to update a part of the old route path, and contains a route update node list that indicates a part of the old route path to be updated;

(b1) when the destination node finds a part of the old route path needs update and decides to update the part of the old route path, the destination node local broadcast a route update message to the source node;

path nodes of the old route path and neighbors of the nodes in the route update node list are qualified for forwarding the route update message;

(b2) when a path node finds a part of the old route path needs update and decides to update the part of the old route path, the path node local broadcast a route update message to the source node;

upstream path nodes and neighbors of the nodes in the route update node list are qualified for forwarding the route update message.

7. A method according to claim 3, wherein whether to trigger a route update process depends on route update parameters that include the link quality and the path node state;

a path node detects the link quality of the previous hop and its state during forwarding traffic packets, while the destination node detects the link quality of the last hop during receiving traffic packets;

if a route update parameter exceeds a threshold, a route update process can be triggered;

a path node checks the route update parameters to decide whether to trigger a route update process, or forwards the route update parameters to downstream nodes for the route update decision;

the destination node checks the link quality of the last hop for the route update decision;

within a period of time no more than one route update process from a initiator to a target node is launched.

8. A method according to claim 7, wherein the neighbor relationship with the destination node is set up by listening routing control messages sent by the destination node;

the neighbor relationship with the source node and path nodes is set up by overhearing traffic packets;

the neighbor relationship with the route path is set up by overhearing traffic packets on the route path;

the neighbor relationship is restricted by a valid neighbor duration or the link quality;

if a network node'"'"'s state exceeds a threshold, the node discards received route update messages that are triggered due to the path node state;

when a network node forwards a route update message, the network node updates the parameters related to the new route path in the route update message;

the source node depends on the latest route update message to update its routing table;

if multiple copies of the latest route update message arrive, the source node compares metrics of these new route paths to selectively update its routing table.

9. A method according to claim 3, wherein the routing control messages include local route request messages;

a local route request process comprising;

when a path node finds a broken link, the path node sends a route error message to the source node;

upon receiving the route error, the source node broadcast a local route request message to the destination node;

path nodes of the old route path, path neighbors of the old route path, and neighbors of the destination node are qualified for forwarding the local route request message;

the neighbor relationship with the old route path is set up by overhearing traffic packets on the route path, while the neighbor relationship with the destination node is set up by listening routing control messages by the destination node;

the neighbor relationship is restricted by a valid neighbor duration;

upon receiving the local route request message, the destination node sends a route reply message back to the source node.