Field of Invention The present invention relates generally to wireless mesh networks, more particularly to a multi-hop routing in wireless mesh network.

Background of the Invention

Wireless mesh networks have become increasingly popular nowadays. The path creation in the existing centralized multi- hop relay system is usually subject to the constraints of tree topology such as for example a relay station shall have only one super-ordinate station and other constraints such as the availability of radio resource, radio quality of the link, load condition of an RS, Quality-of-Service (Qos) of each connection, etc. Therefore, due to various requirements and constraints, one particular mode of operation may be better than another at a particular time. Other considerations also exist, such as a best path for routing a communication to maximize system capacity and reduce cost.

In a distributed multi-hop relay system, the routing for each mobile station (MS) is decided by the base station (BS) or the relay stations (RSs) , based on the configuration, before transmitting the data packets. To facilitate routing information between mesh nodes/relay stations for both the uplink and downlink direction in mesh fashion, the topology information should be obtained from topology discovery or update process so that each mesh node or relay station detects and forwards the packets to the appropriate destination.

Accordingly, new methods and systems for creating and maintaining a mesh routing structure in a wireless network are required.

In one aspect of the present invention, an embedded path management method for mesh nodes or relay stations to maintain routing structure is presented. In another aspect of the present invention, the network topology is embedded into systematic connection identification (CID) structure to help mesh nodes to find routing paths without storing all CIDs of subordinate nodes in the routing table. When the embedded path management is used, the superordinate shall systematically assign CIDs to its subordinate stations such that the CIDs allocated to all subordinate nodes of any given station is a subset of the allocated CIDs for that station.

Other objects of this invention will become apparent on the reading of this entire disclosure. Summary of -the Invention

In one embodiment of the present invention, a method for embedded mesh path management in a wireless multi-hop relay network comprising a base station, at least one relay station and a mobile station, the method comprising assigning a connection identifier (CID) by said base station as a super- ordinate station to said at least one relay station as subordinate station with specified routing path of the connection based on said assigned CID, changing the unique assigned identifier of one of the relay stations upon connection to the another one of the at least one relay stations, and performing data transmission to said relay stations which are connected in mesh topology in accordance to the routing information embedded in said assigned connection identifier.

Preferably the step of changing the unique assigned identifier includes left shifting the CID of said super-ordinate by 2- bits and filling the right most 2-bits of the first joined subordinate station with 00 and increasing the value of the right 2-bits by 1.

Preferably the method further comprising the step of obtaining the CID of the super-ordinate station by any subordinate station for uplink communication by right shifting its CID by 2-bits.

A system for embedded mesh path management in a wireless multi-hop relay network comprising a base station, at least one relay station and a mobile station, the system comprising a processor, and a memory in communications with said processor, wherein said memory including program code executable by said processor to perform the following steps assigning a connection identifier (CID) by said base station as a super-ordinate station to said at least one relay stations as subordinate station with specified routing path of the connection based on said assigned CID, changing the unique assigned identifier of one of the relay stations upon connection to the another one of the at least one relay stations, and performing data transmission to said relay stations which are connected in mesh topology in accordance to the routing information embedded in said assigned connection identifier.

Brief Description of the Drawings

Other objects, features, and advantages of the invention will be apparent from the following description when read with reference to the accompanying drawings. In the drawings, wherein like reference numerals denote corresponding parts throughout the several views :

Figure 1 shows a diagram illustrating bit partition assignment for the existing multi-hop relay tree topology;

Figure 2 is a diagram showing the bit partition assignment for the multi-hop relay when the stations are connected as mesh topology of the present invention;

Figure 3 depicts a detailed systematic CID assignment by MR-BS for joined relay stations in mesh topology for example of 7- nodes illustrating different scenarios of the present invention;

Figure 4 is a flowchart illustrating how super-ordinate station assigns CID to newly joined subordinate station for downlink communication; and Figure 5 is a flowchart of extracting the original super- ordinate CID from the subordinate CID for uplink communication . Detailed Description of the Preferred Embodiments

In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the invention. However, it will be understood by those of ordinary skill in the art that the invention may ^¬ be practiced without these specific details. In other instances, well-known methods, procedures and/or components have not been described in detail so as not to obscure the invention. Reference will now be made in detail to the preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings.

A wireless multi-hop relay network (10) is described herein. In a multi-hop relay network (10), the network (10) includes a base station (BS) , at least one relay station (RS) and a mobile station (MS) . The connection between the base station

(BS) and relay station (RS) or between two relay stations or between the base station (BS) and mobile station (MS) is identified by a connection identifier (CID) . In the path management of this multi-hop relay network (10), a super- ordinate station which is a multi-hop relay-base station (MR-

BS) will systematically assign the connection identifiers

(CIDs) to its subordinate stations which are other relay stations (RSs) . Figure 1 is a schematic diagram of the existing method for CID assignment as given by the draft IEEE Std P802.16J/D8, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems: Multihop Relay Specification. As shown in the figure, the assignment method is targeted mainly for tree topology and in hierarchical manner. The CIDs are assigned systematically using bit partitioning assignment. Bit partition assignment shall only be used to allocate node (for example: a relay station (RS) in IEEE 802.16j) primary management CID or RS basic CID. In the bit partition assignment, a parameter, k, is configured to specify the maximum number of direct subordinate nodes (for example: RSs) that a super-ordinate node (for example: multi-hop relay-base station MR-BS) (11) could serve is 2 to the power k. The value of this parameter is the same within the wireless cell (e.g. MR cell) . The super-ordinate node sets the k least significant bits (LSBs) in ascending order to the nodes directly associated to the super-ordinate. For other level-n nodes, which need n hops to reach the super-ordinate, the super- ordinate node left shifts k bits of its parent CID and sets the k LSBs according to the arriving sequence of the node. When the network topology changes, the super-ordinate node can inform related nodes of updated value of k and n in the appropriate message (for example: CID_ALLOC-REQ message in IEEE 802.16j wireless standard). In the systematic CID assignment of the present invention, the super-ordinate station (12) will specify the relay routing path of the connection based on the assigned CIDs to its subordinate stations (13) and the CID assignment is mainly for mesh topology as shown in Figure 2. The super-ordinate station

(12) does not require to provide end-to-end signaling for the purpose of routing table creation. For example, there are total of seven stations connected as mesh topology. With CID information contained in MAP-IE or MAC header, any RS

(13) can perform data forwarding to its subordinate RSs (13) which are connected in mesh topology. When a new subordinate station which is a mobile station (MS) moves to the coverage area of another RS connecting to the same MR-BS (12), its previously assigned systematic CID may not correspond to the routing path implied by the systematic CID assignment of the present invention. In such case, the MR-BS (12) may update the systematic CID for the MS according to its new routing path. Alternatively, the MR-BS (12) tunnels all the packets for the MS to the RS using the systematic CID assigned to RS.

In order to find the CID of the super-ordinate station (12) in the mesh topology, the subordinate station will right shift 2- bits for the previous hop and in order to find the CID of the subordinate station (13), the super-ordinate station will left shift 2-bits for the next hop. The assignment of the CIDs for the stations are shown in the last column of the table of Figure 3 and based on the two routing structures. The CID assignment depends on the hop count, the configuration of network and the topology type whether tree or mesh.

When a network station joins (21) the super-ordinate station (12), this new subordinate station will get it CID from the super-ordinate station (12) systematically as shown in Figure 4. The system will first get the CID (22) of the super- ordinate station (12) . Then new subordinate station will be checked (23) whether it is a first joined station for this super-ordinate station (12) . If it is the first joined station (24), the super-ordinate station (12) will left shift its CID by 2-bits (26) and fill the right most 2-bits with 00 for the first joined station. If it is not the first joined station (25), the super-ordinate will increase the value of the right 2-bits of the joined station by 1 (27) which is by filling the right most 2-bits with 01 for the second joined station, with 10 for the third joined station, with 11 for the fourth joined station and so on based on the number of joined stations.

Any subordinate station can get the CID of its original super- ordinate station as shown in Figure 5. The system will first get the CID of the subordinate station (31) . Then station will be checked on whether it is the main super-ordinate station (32). If it is the main super-ordinate station (33), the CID is extracted. If it is not the main super-ordinate station (34) the subordinate will right shift its CID by 2-bits (35) to get the super-ordinate CID. The system includes a processor (41) and a memory in communication with the processor (41) where the memory- includes program code (42) which is executable by the processor (41) . The base station of the system creates a cache of connection identifiers (CIDs) and routing information (43) and transmits it to the relay station (RS) . The RS detects and forwards the packets in accordance with the cache. The system will also forward the packet to another relay station when the content of the identifier in the packet matches with the assigned values for the one of the relay stations and discarding the packet when there is no match. The system will change the unique identifier of the one of the relay stations upon connection to the another one of the relay stations to be an exclusive subset of the identifiers assigned to the station and then remove the assignment of unique identifiers from the one of the relay stations to which the another one of the relay stations is no longer connected.

The system can also operate to assign a first set of connections IDs (CID) to the RSs (for example RSl, RS3 and RS4 in figure 2 in first come first serve) connected to the BS one hope distance and to assign a subset of the first set of CIDs to a second RS that is connected to the first set of RSs two hopes away (for example RS2, RS5 and RS6) as shown in figure 2 and so on. As will be readily apparent to those skilled in the art, the present invention may easily be produced in other specific forms without departing from its essential characteristics. The present embodiments is, therefore, to be considered as merely illustrative and not restrictive, the scope of the invention being indicated by the claims rather than the foregoing description, and all changes which come within therefore intended to be embraced therein.