Routing in a mesh network

[0001] The present invention relates generally to telecommunications, and in particular to routing in a mesh network.

BACKGROUND [0002] Wireless communication systems, access networks are generally used to connect any number of access terminals to a wide area network (WAN), such as the Internet or a public switched telephone network (PSTN). These access networks are usually implemented with multiple wireless access points scattered in the geographical area. Each of these access points provides a wired return connection to the gateway for

WAN.

[0003] The mesh network differs from the traditional solution mentioned above in that any number of access points can jointly join the connection of access terminals with the gate. The principle is similar to how data is routed on the Internet. In principle, data in the mesh network is routed from one access point to another until it reaches its destination. The throughput of the mesh network depends on the routes established by the access points to transfer data. Thus, it would be beneficial to be able to dynamically determine the optimal routing in the mesh network.

[0004] Choosing the optimal data transmission path in a mesh network is not a simple task. Changing wireless transmission conditions and the availability of multiple paths in a mesh network pose various challenges. Also, wireless links between access points do not have fixed data rates. As a result, a traditional approach, based on determination

The connections with the shortest paths between access points are not always optimal if other combinations can provide higher data rates or reduce delay. Accordingly, there is a need in the art for optimizing data routing in a mesh network to increase throughput.

For example, patent application WO 2005/117348 describes a processing system configured to establish connections to any of a plurality of access points in a mesh network, each access point providing a different data transmission path in the mesh network to the device, wherein the processing system is further configured to calculating the metric of each data path and selecting, based on said metric, one of the access points to establish a connection with it. In addition, WO 02/25969 describes a processing system configured to broadcast a message on a network and receive one or more responses containing information relating to data path link links and calculating metrics for data paths based thereon.

SUMMARY OF THE INVENTION [0005] According to one aspect of the invention, the device comprises a processing system configured to establish connection to any of a plurality of access points in a mesh network, each access point providing a different data transmission path in the mesh network to the device, wherein the processing system is further configured to calculate the metric for each data transmission path and select, based on the metric, one of the access points, to establish a connection with him.

[0006] According to another aspect of the invention, the device is configured to operate in a mesh network having many

The access points include a processing system configured to calculate, for each access point, a metric for each of the plurality of data transmission paths supported by the given access point and to establish connections between the access points based on the metric.

[0007] According to yet another aspect of the invention, the method of establishing connections to any of a plurality of access points in a mesh network, each access point providing a different data transmission path in the mesh network, includes calculating a metric for each of the data transmission paths and selecting based on the metric of one of the access points to establish a connection with it.

[0008] According to another aspect of the invention, a method of operating in a mesh network having multiple access points includes calculating, for each of the access points, metrics for each of the multiple data transmission paths served by that access point and establishing connections between access points based on about the records.

[0009] According to yet another aspect of the invention, the device comprises means for establishing connection with any of a plurality of access points in the mesh network, each access point providing a different data transmission path in the mesh network for the device, calculation means for calculating a metric for each path data transmission and selecting means, for selecting one of the access points, in order to establish connection with it based on metrics.

[0010] According to yet another aspect of the invention, the device configured to operate in a mesh network having a plurality of access points, includes calculation means for calculating, for each of the access points, metrics for each of the plurality of data transmission paths supported by the given access point and means to establish connections between access points based on metrics.

[0011] According to yet another aspect of the invention, the access point comprises a processing system configured to establish connection to any of a plurality of access points in the mesh network, each access point providing a different data transmission path in the mesh network to the device, wherein the processing system is further configured to calculate the metric for each data transmission path and select one of the access points, to establish a connection with it, based on the metrics, and a transceiver configured to support the connection between the processing system and the selected access point.

[0012] According to yet another aspect of the invention, the device configured to operate in a mesh network having a plurality of access points comprises a processing system configured to calculate, for each of the access points, metrics for each of the plurality of data transmission paths served by the access point and establishing connections between access points based on metrics and a transceiver system configured to broadcast information to access points, the information relates to connections established by the processing system.

[0013] According to another aspect of the invention, the computer program product enabling the device to operate in a mesh network includes a computer readable medium. The computer-readable medium contains a code for establishing a connection to any of the many access points in the mesh network, each access point providing different data transmission paths in the mesh network for the device, a code for calculating the metrics for each of the data transmission paths, and a code for selecting one of the access points to establish a connection to, based on the metrics.

[0014] According to yet another aspect of the invention, a computer program product that allows the device to operate

53 / 55P27323EN00 in a mesh network having multiple access points includes a computer readable medium. The computer-readable medium includes a code for calculating, for each of the access points, metrics for each of the many data transmission paths supported by that access point, and a code for establishing connections between access points based on the metrics.

[0015] It will be appreciated that other aspects of the present invention will become apparent to those skilled in the art upon reviewing the following detailed description, in which only the various aspects of the invention are shown and described in the form of an example. As can be seen, the invention may include other and different aspects and several of its details may be modified in various other respects without departing from the scope of the present invention. Accordingly, the drawings and detailed description should be regarded as illustrative rather than limiting the scope of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS [0016] Various aspects of the wireless communication system are illustrated by way of example and not as a limitation of the scope of the invention, in the accompanying drawings in which:

[0017] Fig. 1 is a schematic block diagram illustrating an example of a mesh network;

[0018] Fig. 2 is a schematic block diagram illustrating an example of an access point that attempts to access the mesh network of Fig. 1;

[0019] Fig. 3 is a flowchart illustrating an example of an algorithm that can be used by a central server to optimize data transmission paths in a mesh network;

[0020] Fig. 4A is a block diagram illustrating an example of access point functionality;

[0021] Fig. 4B is a block diagram illustrating another example of access point functionality;

[0022] Fig. 5A is a flowchart illustrating an example of a method of establishing connection to any of a plurality of access points in a mesh network;

[0023] Fig. 5B is a flowchart illustrating another example of the method of Fig. 5A, and [0024] Fig. 5C is a flowchart illustrating an example of a method of establishing connections in a centralized mesh network.

DETAILED DESCRIPTION [0025] The detailed description below with reference to the accompanying drawings should be regarded as a description of various aspects which is not intended to represent the only aspects that can be implemented. The detailed description includes specific details to enable an accurate understanding of the invention. However, it will be apparent to those skilled in the art that the invention may be implemented without these specific details. In some cases, well-known structures and components are shown in block diagram to avoid that the ideas of the invention are incomprehensible.

[0026] In the following detailed description, various ideas will be described in the context of a mesh network. Although these ideas are well suited to this application, those skilled in the art will readily recognize that these ideas can be applied similarly to other access networks. For example, different ideas can be used in an ad-hoc mobile network in this description. Accordingly, all references to the mesh network should be regarded only as illustrations of these ideas, understanding that such ideas have a wide range of applications.

[0027] Fig. 1 is a schematic block diagram illustrating an example of a mesh network. The mesh network 100 includes a plurality of mesh network access points (MAP) 1021-1025 connected to each other to connect one or more access terminals (not shown) to the WAN 106, such as the Internet. In this example, one of the MAP 1021 points has a wired reverse connection to WAN 106, and therefore this MAP 1021 is sometimes called the Root Access Point (RAP).

[0028] The mesh network 100 is formed by establishing radio links between MAP 1021-1025. In the example shown in Fig. 1, RAP 1021 has a radio connection with MAP 1022 that supports rate R1 MAP 1022 has a radio connection with which supports R2 data rate and other radio connection to MAP 1024, which supports R3 data rate. The MAP 1023 has a radio link to MAP 1025 that supports the R4 data rate.

[0029] Radio connections can be made using any wireless communication protocol, including, for example, IEEE 802.11 (Wi-Fi), IEEE 802.20 (Wi-MAx), Bluetooth, Ultra Wideband (UWB), or any other communication protocol. wireless appropriate air interface. aerial include multi-access data transmission. MAP 1023, having any

Examples of orthogonal frequency division (OFDMA) interfaces, broadband split access

In addition, different ideas can be extended using different code (W-CDMA) and the like. wide area computer networks described herein, wireless communication protocols, including, for example, CDMA2000, global mobile communication system (GSM), Ultra Mobile Broadband (UMB), Enhanced Data rates for GSM Evolution (EDGE), etc. Specific communication protocol wireless, used

53 / 55P27323EN00 in any mesh network will vary depending on the particular application and general construction restrictions imposed on the entire system.

[0030] Fig. 2 is a schematic block diagram illustrating an example where MAP 1026 attempts to access the mesh network 100 of Fig. 1. When MAP 1026 attempts to access, it determines how it should send data to the RAP 1021. In this example, there are three adjacent MAPs: 1023, 1024 and 1025, with which MAP 1026 can establish communication and each of the neighboring MAPs: 1023, 1024, 1025 can route data through different data transmission paths in the mesh network 100. They will now metrics for several possible connections, to select the optimal MAP point to connect to.

[0031] The first link metric to be presented will be called a bottleneck rate metric. Using this metric, MAP 1026 calculates the metric for each available data path and then selects the path that provides the maximum value for the metric. The metric is determined by dividing the bottleneck link capacity (i.e. the minimum data rate along the path to RAP 1021) by the number of hops. For example, the metric for the path passing through MAP 1025 is calculated as follows:

min (r1, R4, R2, R1) A) 'where r1 is the data rate that can be served by the radio link between MAP 1026 and MAP 1025. The metric is calculated in this way for the other two data paths (i.e. through points MAP 1023 and

53 / 55P27323PL00

1024), and then the path that provides the highest metric value is selected, as follows:

Zmin (r1, R4, R2, R1) min (r2, R2, R1) min (r3, R3, R1 'arg max I-4 -, - 3-, -3 where r2 is the data rate that the radio link can handle between MAP 1026 and MAP 1023, and r3 is the data rate that the radio link between MAP 1026 and MAP 1024 can support.

[0032] The metric based on the bottleneck data rate is used to optimize the data rate in the mesh network 100, but does not include delay. The second link metric to be presented takes into account the latency in the mesh network 100. This metric may be called the harmonic mean metric. Using this metric, MAP 1026 calculates the harmonic average data rate available along each path and selects the path that offers the maximum harmonic average data rate. For example, the harmonic average metric for the path through MAP 1025 is calculated as follows:

_k r1 + R4 + R2 + R1 _s [0033] The harmonic metric is calculated in this way for the other two paths (i.e. by MAP points 1023 and 1024) and then the path is chosen that provides the maximum value of the harmonic mean metric:

arg max r1

R4

R2

R1 r2

R2

R1 r3

R3

R1

[0034] It should be noted that the above calculation is somewhat different from the traditional concept of harmonic mean. The strict definition of the harmonic mean of N variables 1 / r1, ..., 1 / rN is as follows: N / (1 / r1 + ... + 1 / rN). The above harmonic mean calculation method is modified so that the N component is removed from the meter. The term "harmonic mean" as used herein refers to the above calculation method.

[0035] Another link metric that will be presented may be referred to as a time metric. The time metric is based on the time needed to send the L size frame along the given data transmission path in the mesh network. Instead of using data rates, this metric calculates the time it takes to send the frame along each available path, and then selects the path that requires the least time. The time metric may be appropriate for applications that support frames with significant administrative overhead. For example, the frame transmission time in IEEE 802.11 is given as follows:

L + H

Tframe = To + r where To refers to fixed administrative overhead such as preamble and TPLCP, and H represents the MAC header. The metric for the example above is as follows:

arg max (_

4To + (L + H)

V ___i_

111 1 V (111 λ r1 + R4 + R2 + R1 ^{J 3 It} + ^(L+^H) V r2 + R2 + R1 ^J _1_ (1 1 1 λ ^3Tat +^(L+^{H) (} r3 + R3 + R1) [0036] When MAP 1026 tries to access network 100, it can apply various techniques to obtain

53 / 55P27323EN00 information needed to calculate the metric. In one configuration, MAP 1026 connects to mesh network 100 by broadcasting a message. Each MAP in mesh network 100 that may hear a broadcast message will send a response indicating the number of hops to RAP 1021 and the metric. The MAP 1026 can then calculate its own metric by each MAP that responded to the broadcast. Basically, for each corresponding MAP, MAP 1026 calculates its own metric, using the data rate that the corresponding MAP can handle and information in response from the corresponding MAP (i.e. the number of jumps to RAP 1021 and the metric). MAP 1026 then selects the MAP that provides the maximum value of its own metric. MAP 1026 can constantly update its path to RAP 1021 by broadcasting a message and making any necessary modifications to obtain the maximum value of its metric.

[0037] The mesh network 100 may be decentralized (without a central server), or centralized (with a central server). In centralized applications, a central server can be used to dynamically configure data transmission paths through a mesh network. The central server may be a separate unit (not shown), integrated with the RAP 1021, or distributed along one or more access points (i.e., MAP and / or RAP) in mesh network 100.

[0038] An example of an algorithm that can be implemented by a central server to optimize data transmission paths through the mesh network 100 will now be presented with reference to Fig. 3. In this example the following symbols will be used:

MAPi = the 1st MAP point in the mesh network; MAP1 = RAP

53 / 55P27323PL00

Li = level of the MAPi point (i.e. the number of jumps from the MAPi point to RAP);

Mi = MAPi point record;

Ni = adjacent MAP point for MAPi.

[0039] In step 302, variables are initialized. In this example, L1 is set to 0, Li is set to 1 for all MAPi points, where i> 1, and Mi is set to the metric value for direct connection to the RAP point (i.e. one jump). The Mi metric can be zero for any MAPi point that is too far from the RAP point to handle the connection.

[0040] After the initialization of the variables, the algorithm may start calculating the metrics. The calculation starts in step 304. For each MAPn point, the Mn, k metric is determined for each k, at Lk = j, where Mn, k is the nth MAP metric for the path passing through k at level j. Then, in at step 306, the metric for each MAP point is maximized by determining whether max (Mn, k: all kz Lk = j)> Mn. If the expression is met, then Mn is set in step 308 to the max value (Mn, k: all kz Lk = j). Otherwise, the stage is skipped.

[0041] At step 310, it is determined whether Ln is equal to the maximum mesh depth (i.e. the maximum number of hops between MAP and RAP). If Ln is less than the maximum mesh depth, the level is increased by setting Ln = j + 1 in step 312. The algorithm then returns to step 304 to start the next calculation of the metrics. If, on the other hand, Ln is equal to the maximum mesh depth, then the optimal path to the RAP point is selected for each MAP in step 314 by establishing a connection to the neighboring MAP that provides the maximum value of the metric as follows: Nn = arg max (Mn, k: all kz Lk = j).

[0042] Figs. 4A and 4B are block diagrams illustrating examples of MAP point functionality. The MAP 102 includes a transceiver 404 that provides an air interface with other MAP points in the mesh network. The MAP 102 also includes a processing circuit 402 that is shown with functional blocks to illustrate its functionality. These functional blocks can be made with a processing system including hardware, software, firmware, software and hardware means, microcode, hardware description languages, or any combination thereof. For example, functional blocks can be made with a processing system that uses program code running on a microprocessor, digital signal processor (DSP), or any other suitable platform. The processing system may also include a computer readable medium for storing the program code. A computer-readable medium may include one or more memory devices, including, for example, RAM, flash memory, ROM, EPROM, EEPROM, registers, hard disk, removable disk, CD-ROM, or any other form of storage medium known from the state of the art. The computer-readable medium may also contain a carrier wave that encodes a data signal.

[0043] Alternatively, or in addition, functional blocks of the processing system can be implemented by means of an integrated circuit for specific applications (ASIC), controller, microcontroller, state machine, programmable logic gate matrix (FPGA) or other programmable logic component, discrete logic gate or transistor hardware components

These circuits may or may not use any discrete combination code.

a program that is saved on a computer readable medium.

for

[0044] Those skilled in the art will recognize the interchangeability of hardware, firmware and software configurations under these conditions and the best way to implement the described functionalities in a particular application.

[0045] In Fig. 4A, processing system 402 includes a module 406A for establishing connection to any of a plurality of MAP points in a mesh network, each of the MAP points providing different data transmission paths in a mesh network. The processing circuit 402 also includes a module 408A for calculating the metrics for each of the data transmission paths and a module 410A for selecting one of the access points to establish a connection to it based on the metrics. [0046] In Fig. 4B, the processing circuit 402 includes a module 406B for calculating, for each MAP in a mesh network, a metric for each of the plurality of data paths served by a given MAP and a module 408B for establishing connections between access points based on the metrics.

[0047] Fig. 5A is a flowchart illustrating an example of a method for establishing connection to any of a plurality of MAPs in a mesh network, each MAP providing a different data transmission path in the mesh network. In step 502A, a metric is calculated for each data transmission path, and in step 504A one of the access points is selected based on the metrics to establish a connection to it. Calculation of metrics can be done in various ways. One way is to divide the minimum data rate supported at one or more hops in the appropriate data transmission path by the number of hops in that path, whereby the data transmission path passing through the selected access point has the maximum metric. Another way to calculate a metric is to calculate the harmonic average of the data rate provided with one or

53 / 55P27323EN00 more jumps in the respective data transmission path, wherein the data transmission path through the selected access point has the maximum harmonic average of the data rate. In yet another method, the calculation of the metrics can be performed by calculating each of the metrics based on the time it takes to send the data frame through the respective data transmission path, wherein the data transmission path through the selected access point has a minimum transmission time. In particular, the calculation of the metrics can be performed by calculating each metric based on the harmonic average of the data rates provided at one or more hops through the respective data path and the amount of administrative overhead in the frame.

[0048] According to Fig. 5B, the method of Fig. 5A may also include broadcasting a meshed network message in step 506B, receiving one or more responses containing information related to the reverse portion of the data path in step 508B, and using this information to calculate records in step 502A. Information, in combination with its own metric relative to neighboring MAP points, can be used to calculate each metric for the respective data paths.

[0049] Fig. 5C is a flowchart illustrating an example of a method of operating a mesh network having a plurality of access points. At step 502C, for each MAP, a metric is calculated for each of the multiple data paths served by the given MAP. At step 504C, based on the metrics, connections between MAPs are established. The calculation can be performed by calculating, for each MAP, metrics for each data transmission path supported by this MAP, having j jumps through the mesh network, increasing jo one and repeating the calculation for each of the MAP points. Calculations can be made for each of the MAP points for each of the jumps in the mesh network, where j

53 / 55P27323EN00 varies from one to the maximum depth of the mesh network. An example of one algorithm has been previously described with reference to Fig. 3.

[0050] The above description has been presented to enable any person skilled in the art to implement the various aspects described herein. Various modifications to these aspects will be clearly apparent to those skilled in the art, and the general principles set out herein may be applied to other aspects.