Methods and systems for a wireless routing architecture and protocol

• US 20070097945A1
• Filed: 07/07/2006
• Published: 05/03/2007
• Est. Priority Date: 10/27/2005
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Rockstar Bidco LP (Rockstar Consortium Inc.)
• Inventors: Wu, Shiquan, Wang, Guo
• Granted Patent: US 7,933,236 B2
• Time in Patent Office: Days
• US Class Current: 370/349
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/30 for proactive routing
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user
• CPC Class Codes: Y02D 30/70 in wireless communication networks

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.

Claims

1. A method for execution in a multi-hop network comprising a base station and at least one relay station for generating routing paths between the base station and at least one non-relay mobile station, the method comprising:

the base station broadcasting over a first hop a path discovery message (PDM) including a path list comprising a node identifier for the base station;

each relay station of the at least one relay station;

receiving the PDM that was broadcast over a preceding hop, the PDM including the path list defining all preceding hops;

adding a node identifier of the relay station to generate an updated path list in the PDM; and

broadcasting a PDM including the updated path list over a subsequent hop;

the base station receiving a reply from a given one of the at least one non-relay mobile station, the reply comprising a respective path list including node identifiers of all stations in a routing path between the base station and the non-relay mobile station inclusive, the reply being routed via relay stations identified in the respective path list.

2. The method of claim 1, wherein when a non-relay mobile station of the at least one non-relay mobile station receives multiple PDMs, each having a different path list, from different relay stations, the at least one non-relay mobile station:

determining which one of the multiple PDMs has a preferred path list based on at least one criterion characterizing the path lists of the multiple PDMs; and

selecting the PDM with the preferred path list to use as a routing path between the base station and the non-relay mobile station.

3. The method of claim 2, wherein the at least one criterion is selected from a group consisting of:

the shortest path between the base station and the at least one non-relay mobile station;

the best determined radio performance between the base station and the at least one non-relay mobile station;

a quality of service (QoS) value, and least-power-consumed link between the base station and the at least one non-relay mobile station.

4. The method of claim 1, wherein at least one relay station or at least one non-relay mobile station determines whether a generated routing path is valid by:

periodically sending a request message to the base station; and

receiving a response message to the request message if the routing path is still valid.

5. The method of claim 1 further comprising:

the base station or a non-relay mobile station of the at least one non-relay mobile station sending over a first hop a service flow request message including an end-to-end path list and a connection identifier (CID) that defines the connection between the base station and the non-relay mobile station;

each relay station of the at least one relay station;

receiving the service flow request message that was broadcast over a preceding hop; and

determining whether the message is to be forwarded over a subsequent hop or dropped based on the path list and the CID;

if the message is to be forwarded, forwarding the message over a subsequent hop based on the contents of the path list and the CID.

6. The method of claim 5, wherein the method is applied to a wireless network operating in a manner that is consistent with any one of:

IEEE 802.16, IEEE 802.16d, and IEEE 802.16e.

7. The method of claim 5, wherein the base station allocates transmission resources for at least one relay station coupled to the BS by the first hop, and relay stations coupled by subsequent hops allocate transmission resources to subordinate relay stations.

8. The method of claim 5, wherein the end-to-end path list is comprised of a list of entries, the entries each being one of node identifiers or link identifiers.

9. The method of claim 1 wherein broadcasting a PDM by the base station or a respective relay station further comprises broadcasting an air-link-descriptor for each respective hop.

10. A method for execution in a multi-hop network comprising a base station and at least one relay station for message forwarding based on known routing paths between the base station and at least one non-relay mobile station, the method comprising:

the base station or a non-relay mobile station of the at least one non-relay mobile station sending over a first hop a service flow request message including an end-to-end path list and a connection identifier (CID) that defines the connection between the base station and the non-relay mobile station;

each relay station of the at least one relay station;

receiving the service flow request message that was broadcast over a preceding hop; and

determining whether the message is to be forwarded over a subsequent hop or dropped based on the path list and the CID;

if the message is to be forwarded, forwarding the message over a subsequent hop based on the contents of the path list and the CID.

11. The method of claim 10, wherein the service flow request message further comprises a transport CID identifying a connection between two stations over a single hop that can be used to create an entry in a forwarding table for a respective relay station to forward messages between the base station and the non-relay mobile station.

12. The method of claim 11, wherein when the at least one relay station receives a service flow MAC PDU (media access control protocol data unit) from the direction of the base station, the relay station uses a CID associated with the MAC PDU to look up the forwarding table to determine whether to further broadcast the MAC PDU in the direction of the non-relay mobile station or drop the MAC PDU.

13. The method of claim 11, wherein when the at least one relay station receives a management flow MAC PDU from the direction of the base station, the relay station checks the ownership of the CID in the forwarding table to determine whether to process the MAC PDU, further broadcast the MAC PDU in the direction of the non-relay mobile station, or drop the MAC PDU.

14. The method of claim 10, wherein sending the service flow message comprises including a node ID list which is a path list that consists of all the stations along a selected path between the base station and at least one relay station and/or the non-relay mobile station.

15. The method of claim 14 wherein sending the node ID list comprises sending the node ID list in a MAC sub-header.

16. The method of claim 15 further comprising including at least one of a CID stack, a priority class identifier, a sequence number and an air-link-descriptor in the MAC sub-header for the first and subsequent hops.

17. A multi-hop network adapted for communication with at least one non-relay mobile station, the network comprising:

a base station; and

at least one relay station adapted to receive and forward transmissions between the base station and the at least one non-relay mobile station;

wherein;

the base station being adapted to broadcast over a first hop a path discovery message (PDM) including a path list with a starting point of the path list being the base station;

each relay station of the at least one relay station being adapted to;

receive the PDM that was broadcast over a preceding hop, the PDM including the path list defining all preceding hops;

add a node identifier of the relay station to generate an updated path list in the PDM; and

broadcast a PDM including the updated path list over a subsequent hop; and

the base station being further adapted to receive a reply from each of the at least one non-relay mobile station, the reply comprising a respective path list including the node identifiers of all stations in the routing path between the base station and the non-relay mobile station, the reply being routed via relay stations identified in the respective path list.

18. The multi-hop network of claim 17 wherein:

the base station or a non-relay mobile station of the at least one non-relay mobile station sends over a first hop a service flow request message including an end-to-end path list and a connection identifier (CID) that defines the connection between the base station and the non-relay mobile station;

each relay station of the at least one relay station;

receives the service flow request message that was broadcast over a preceding hop; and

determines whether the message is to be forwarded over a subsequent hop or dropped based on the path list and the CID;

forwards the message over a subsequent hop based on the contents of the path list and the CID, if it is determined that the message is to be forwarded.

19. The multi-hop network of claim 17, wherein at each relay station a priority class identifier associated with a MAC PDU is used by the relay station to prioritize transmission order of the MAC PDU.

20. The multi-hop network of claim 17, wherein 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.