METHODS AND SYSTEMS FOR A WIRELESS ROUTING ARCHITECTURE AND PROTOCOL

• US 20110182231A1
• Filed: 04/01/2011
• Published: 07/28/2011
• Est. Priority Date: 10/27/2005
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: WANG, GUO QIANG, WU, SHIQUAN
• Application Number:
  US13/078,562
• Publication Number:
  US 20110182231A1
• Time in Patent Office: Days
• US Class Current: 370/315
• 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 of operating a base station in a multi-hop network, comprising:

broadcasting a path discovery message (PDM) comprising;

a path list comprising a node identifier for the base station; and

a broadcast connection identifier (CID) identifying that the PDM is broadcast for any non-relay station served by the base station; and

receiving a reply message from at least one non-relay station served by the base station, the reply message comprising;

a path list comprising node identifiers of the non-relay station and all stations in a routing path between the base station and the non-relay station; and

a management connection identifier (CID) identifying a management connection between the non-relay station and the base station defined by the routing path.

2. The method as defined in claim 1, wherein the step of receiving a reply message comprises receiving the reply message via relay stations identified in the path list.

3. The method as defined in claim 1, further comprising sending a service flow message comprising an end-to-end path list and the management CID that defines a connection between the base station and the non-relay station.

4. The method as defined in claim 3, wherein the end-to-end path list comprises a list of entries, each entry being one of a node identifier and a link identifier.

5. The method as defined in claim 1, further comprising:

receiving a request message from one of a relay station and a non-relay station; and

responsive to the request message, sending a response message if a routing path to the non-relay station is still valid.

6. The method as defined in claim 1, further comprising allocating transmission resources for at least one relay station coupled to the base station by a first hop.

7. The method as defined in claim 1, wherein the base station operates in a manner consistent with any of:

IEEE 802.16;

IEEE 802.16d; and

IEEE 802.16e.

8. A method of operating a relay station in a multi-hop network, comprising:

receiving a path discovery message (PDM), the PDM comprising;

a path list, the path list comprising;

a node identifier for a base station; and

node identifiers for any relay stations between the base station and the relay station; and

a broadcast connection identifier (CID) identifying that the PDM is broadcast for any non-relay station served by the base station;

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

broadcasting a PDM including the updated path list.

9. The method as defined in claim 8, further comprising determining whether a generated routing path is valid by:

periodically sending a request message to the base station; and

receiving a response message indicating that the routing path is still valid.

10. The method as defined in claim 8, further comprising:

receiving a service flow request message comprising an end-to-end path list and a management connection identifier (CID) that defines a connection between the base station and a non-relay station;

determining whether the service flow message is to be forwarded or dropped based on the path list and the management CID; and

if the message is to be forwarded, forwarding the message based on the path list and the management CID.

11. The method as defined in claim 10, wherein the end-to-end path list comprises a list of entries, each entry being one of a node identifier and a link identifier.

12. The method as defined in claim 8, wherein the relay station operates in a manner consistent with any of:

IEEE 802.16;

IEEE 802.16d; and

IEEE 802.16e.

13. A method of operating a non-relay station in a multi-hop network, comprising:

receiving at least one path discovery message (PDM), the PDM comprising;

a path list, the path list comprising;

a node identifier for a base station; and

node identifiers for any relay stations between the base station and the non-relay station; and

a broadcast connection identifier (CID) identifying that the PDM is broadcast for any non-relay station served by the base station; and

sending a reply message to the base station, the reply message comprising;

a path list comprising node identifiers of the non-relay station and all stations in a routing path between the base station and the non-relay station; and

a management connection identifier (CID) identifying a management connection between the non-relay station and the base station defined by the routing path.

14. The method as defined in claim 13, wherein the step of receiving at least one PDM comprises receiving multiple PDMs, each having a different path list, from multiple relay stations, the method further comprising:

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 station.

15. The method as defined in claim 14, wherein the at least one criterion is selected from a group consisting of:

shortest path between the base station and the non-relay station;

best determined radio performance between the base station and the non-relay station;

preferred value for at least one quality of service (QoS) parameter; and

lowest power consumption for a link between the base station and the non-relay station over the path.

16. The method as defined in claim 13, further comprising determining whether a generated routing path is valid by:

periodically sending a request message to the base station; and

receiving a response message indicating that the routing path is still valid.

17. The method as defined in claim 13, wherein the end-to-end path list comprises a list of entries, each entry being one of a node identifier and a link identifier.

18. The method as defined in claim 13, wherein the non-relay station operates in a manner consistent with any of:

IEEE 802.16;

IEEE 802.16d; and

IEEE 802.16e.

19. A base station for use in a multi-hop network, comprising:

a transmitter operable to broadcast a path discovery message (PDM) comprising;

a path list comprising a node identifier for the base station; and

a broadcast connection identifier (CID) identifying that the PDM is broadcast for any non-relay station served by the base station; and

a receiver operable to receive a reply message from at least one non-relay station served by the base station, the reply message comprising;

a path list comprising node identifiers of the non-relay station and all stations in a routing path between the base station and the non-relay station; and

a management connection identifier (CID) identifying a management connection between the non-relay station and the base station defined by the routing path.

20. The base station as defined in claim 19, wherein the receiver is operable to receive a reply message by receiving the reply message via relay stations identified in the path list.

21. The base station as defined in claim 19, wherein the transmitter is further operable to send a service flow message comprising an end-to-end path list and the management CID that defines a connection between the base station and the non-relay station.

22. The base station as defined in claim 21, wherein the end-to-end path list comprises a list of entries, each entry being one of a node identifier and a link identifier.

23. The base station as defined in claim 19, wherein:

the receiver is operable to receive a request message from one of a relay station and a non-relay station; and

the transmitter is operable, responsive to the request message, to send a response message if a routing path to the non-relay station is still valid.

24. The base station as defined in claim 19, further comprising a transmission resource allocator operable to allocate transmission resources for at least one relay station coupled to the base station by a first hop.

25. The base station as defined in claim 19, wherein the base station operates in a manner consistent with any of:

IEEE 802.16;

IEEE 802.16d; and

IEEE 802.16e.

26. A relay station for a multi-hop network, comprising:

a receiver operable to receive a path discovery message (PDM), the PDM comprising;

a path list, the path list comprising;

a node identifier for a base station; and

node identifiers for any relay stations between the base station and the relay station; and

a broadcast connection identifier (CID) identifying that the PDM is broadcast for any non-relay station served by the base station;

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

a transmitter operable to broadcast a PDM including the updated path list.

27. The relay station as defined in claim 26, further operable to determine whether a generated routing path is valid by:

periodically sending a request message to the base station; and

receiving a response message indicating that the routing path is still valid.

28. The relay station as defined in claim 26, wherein:

the receiver is operable to receive a service flow request message comprising an end-to-end path list and a management connection identifier (CID) that defines a connection between the base station and a non-relay station;

the path list processor is operable to determine whether the service flow message is to be forwarded or dropped based on the path list and the management CID; and

the transmitter is operable, if the message is to be forwarded, to forward the message based on the path list and the management CID.

29. The relay station as defined in claim 28, wherein the end-to-end path list comprises a list of entries, each entry being one of a node identifier and a link identifier.

30. The relay station as defined in claim 26, wherein the relay station operates in a manner consistent with any of:

IEEE 802.16;

IEEE 802.16d; and

IEEE 802.16e.

31. A non-relay station for a multi-hop network, comprising:

a receiver operable to receive at least one path discovery message (PDM), the PDM comprising;

a path list, the path list comprising;

a node identifier for a base station; and

node identifiers for any relay stations between the base station and the non-relay station; and

a broadcast connection identifier (CID) identifying that the PDM is broadcast for any non-relay station served by the base station; and

a transmitter operable to send a reply message to the base station, the reply message comprising;

a path list comprising node identifiers of the non-relay station and all stations in a routing path between the base station and the non-relay station; and

a management connection identifier (CID) identifying a management connection between the non-relay station and the base station defined by the routing path.

32. The non-relay station as defined in claim 31, wherein the receiver is operable to receive multiple PDMs, each having a different path list, from multiple relay stations, the non-relay station further comprising a path list processor operable to:

determine 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

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

33. The non-relay station as defined in claim 32, wherein the at least one criterion is selected from a group consisting of:

shortest path between the base station and the non-relay station;

best determined radio performance between the base station and the non-relay station;

preferred value for at least one quality of service (QoS) parameter; and

lowest power consumption for a link between the base station and the non-relay station over the path.

34. The non-relay station as defined in claim 31, further operable to determine whether a generated routing path is valid by:

periodically sending a request message to the base station; and

receiving a response message indicating that the routing path is still valid.

35. The non-relay station as defined in claim 31, wherein the end-to-end path list comprises a list of entries, each entry being one of a node identifier and a link identifier.

36. The non-relay station as defined in claim 31, wherein the non-relay station operates in a manner consistent with any of:

IEEE 802.16;

IEEE 802.16d; and

IEEE 802.16e.