Methods and Systems for a Wireless Routing Architecture and Protocol

Abstract

The present invention provides a method for generating routing paths in a multi-hop network. The multi-hop network includes a base station, at least one relay station, and at least one non-relay mobile station. The routing paths are paths between the base station and the at least one non-relay mobile station via the at least one relay station. The base station broadcasts a path discovery message (PDM) including a path list with a starting point of the path list being the base station. Each of the relay stations receives the PDM and updates the PDM by adding their own respective node identifier to the path list and broadcasting the updated PDM. The PDMs eventually reach the non-relay mobile station. The non-relay mobile stations reply to the base station by sending the base station the updated path list between the base station and the non-relay mobile station. In some embodiments the base station or the at least one non-relay mobile station acting as a source node sends a dynamic service (DSx) message including an end-to-end path list to an end of path destination. The relay stations use the path list to forward the message between the source node and the end of path destination. In some implementations the multi-hop network operates in a manner that is consistent with any one of: IEEE 802.16, IEEE 802.16d, and IEEE 802.16e.

1 .- 36 . (canceled) 
     
     
         37 . A node of a network, comprising:
 a receiver;   a transmitter; and   a processor communicatively coupled to the transmitter and receiver;   wherein the node is configured to:
 receive, from a first neighboring node, a broadcast path discovery message over a first hop, wherein the broadcast path discovery message includes a path list and a broadcast connection identifier; 
 append a node identifier associated with the node to the path list, generating a first updated path list; 
 broadcast, to one or more second neighboring nodes, the first updated path list over a second hop; 
 receive, from at least one second neighboring node of the one or more second neighboring nodes, a second updated path list including a node identifier associated with the second neighboring node; and 
 send, to the first neighboring node, a third updated path list, wherein the third updated path list includes the node identifier associated with the node and the node identifier for at least one second neighboring node. 
   
     
     
         38 . The node of  claim 37 ,
 wherein the broadcast connection identifier identifies the at least one second neighboring node.   
     
     
         39 . The node of  claim 37 ,
 wherein the second updated path list includes a node identifier corresponding to a third neighboring node, where the third neighboring node is at least two hops from the node.   
     
     
         40 . The node of  claim 39 ,
 wherein the broadcast connection identifier identifies the at least one second neighboring node and the third neighboring node.   
     
     
         41 . The node of  claim 37 ,
 wherein the node is further configured to:
 receive a service flow request message broadcast over a preceding hop; and 
 send the service flow request message over a next hop based on the third updated path list and a management connection identifier. 
   
     
     
         42 . The node of  claim 41 ,
 wherein the service flow request message comprises a media access control protocol data unit (MAC PDU).   
     
     
         43 . The node of  claim 37 ,
 wherein the node is further configured to:
 periodically send a request message to the first node; and 
 receive a response message from the first node indicating that a connection between the node and the first node is valid. 
   
     
     
         44 . A method for identifying nodes in a network, comprising:
 receiving, at a node, a path discovery message from a first node over a first hop, wherein the path discovery message includes a path list and a broadcast connection identifier;   determining a group of neighboring nodes one hop from the node based on the broadcast connection identifier;   broadcasting a first updated path list to the group of neighboring nodes, wherein the updated path list includes a first node identifier corresponding to the node;   receiving a second updated path list from a neighboring node of the group of neighboring nodes;   generating a third updated path list, wherein the third updated path list includes the first node identifier and a node identifier corresponding to the neighboring node; and   sending the third updated path list to the first node.   
     
     
         45 . The method of  claim 44 , further comprising:
 appending the node identifier of the node to the path list to generate the first updated path list.   
     
     
         46 . The method of  claim 44 ,
 wherein the second updated path list includes node identifiers corresponding to a third neighboring node, where the third neighboring node is at least two hops from the node.   
     
     
         47 . The method of  claim 46 ,
 wherein the broadcast connection identifier identifies the third neighboring node.   
     
     
         48 . The method of  claim 44 , further comprising:
 receiving a service flow request message broadcast over a preceding hop; and   sending the service flow request message over a next hop based on the third updated path list and a management connection identifier.   
     
     
         49 . The method of  claim 48 ,
 wherein the service flow request message a media comprises access control protocol data unit (MAC PDU).   
     
     
         50 . The method of  claim 44 , further comprising:
 periodically sending a request message to the first node; and   receiving a response message from the first node indicating that a connection between the node and the first node is valid.   
     
     
         51 . A node of a network, comprising:
 a receiver;   a transmitter; and   a processor coupled to the transmitter and receiver;   wherein the node is configured to:
 broadcast to a group of first neighboring nodes, a broadcast path discovery message over a first hop, wherein the broadcast path discovery message includes a path list and broadcast connection identifier; 
 receive, from a first neighboring node, an updated path list, wherein the updated path list includes a node identifier corresponding to a neighboring node and a neighboring node identifier corresponding to a second neighboring node, wherein the second neighboring node is at least two hops from the node; and 
 compile a route list to nodes identified in the updated path list, wherein the route list indicates a shortest route to each node. 
   
     
     
         52 . The node of  claim 51 ,
 wherein the broadcast connection identifier indicates the second neighboring node.   
     
     
         53 . The node of  claim 51 ,
 wherein the updated path list includes node identifiers corresponding to a third neighboring node, wherein the third neighboring node is at least three hops from the node.   
     
     
         54 . The node of  claim 53 ,
 wherein the broadcast connection identifier identifies the second neighboring node and the third neighboring node.   
     
     
         55 . The node of  claim 51 ,
 wherein the node is further configured to:
 send a service flow request message based on the route list and a management connection identifier. 
   
     
     
         56 . The node of  claim 55 ,
 wherein the node is further configured to:
 receive a request message from at least one node of the group of first neighboring nodes; and 
 send a response message to the at least one node indicating that a connection between the node and the at least one node is valid.