Thereof

Field Of Invention

The present invention relates to a method of routing a data packet from a destination to a source through one of many paths available in a mesh network. Particularly, the disclosed method improves the delivery process by computing and comparing link costs of each possible path to determine the best path to carry out the packet forwarding. Moreover, the present invention also includes a network system capable of implementing the disclosed method.

Background Of The Invention

With great advancement made in the radio technology, establishment of rapid and inexpensive wireless local area network become feasible and easier especially following the advent of wireless mesh network (WMN). The WMN is a wireless ad hoc network generally constituted of mobile computing device like smartphones, tablets, laptop and the like. These devices function as interconnecting and intercommunicating nodes in a dynamic fashion for delivering data packet from a source, particularly a gateway or router, to a destination or client, such as a laptop or smartphone instead of using fixed router in the process of packet forwarding. Each of the nodes in the WMN discovers the neighboring connecting nodes to form a route or path to forward the packet. The rate or speed of the packet being forwarded in the WMN largely relies on the condition of the path or route, more precisely, collective condition of the nodes of the used path. Though the WMN shows great advantages in terms of cost and deployment, its capability in packet forwarding has been detrimentally affected by its very own structures. For instance, nodes in the WMN are normally set to transmit and receive data simultaneously over a given radio frequency that such unorganized transmission always lead to high error rate in the data transmitted and requires re-forwarding of the data packet. Moreover, the frequently re-transmission processes in the WMN drain unnecessary power from the battery-operated resulting in inefficient energy management in the WMN system. Having the shortcoming unavoidably inherited in the WMN, effort has been put into developing better protocol or modules to run the WMN to attain better data transmission. For example, United States patent application no. 7554998 claims a method of selecting route by firstly determining interference energy over each node in multiple routes and combining interference energy for each hop to produce combined interference energy for each route then finally selecting the route based on the combined interference energy in additionally taking size of the packet and the like into consideration. Nokia Siemens Network filed another United States patent application no. 796568 ldescribing another approach to select the best route through calculating link cost for each path and the calculate link cost is further broadcasted using a beacon frame to the connected node via a central point. Particularly, the link cost in the mentioned application is correlated to error rate of the transmission in each node. Qualcomm Incorporated discloses another method, as in United States patent application no. 8089881, to manage communication resource in mesh network, which only perform transmission after determining transmission activity in the overall mesh network and the expected carrier-to-interference ratio of a listened channel satisfied a predetermined condition. The above mentioned prior arts may have offered better approach to administer mesh network yet there are room for further enhancement considering efficiency of the overall mesh network can be affected by multiple factors. Thus, a more comprehensive approach or module to regulate packet forwarding in the dynamic mesh network is welcome. Summary Of The Invention

The present invention aims to disclose a method to enhance efficiency of packet forwarding in a wireless mesh network by selecting and utilizing the best possible route or path in the given network. Preferably, the disclosed method takes into consideration of various factors affecting the condition of the transmitting nodes and paths in performing the route selection.

Further object of the present invention is to disclose a method to firstly derive a node cost for each of the nodes in the formed paths and later compute a link cost for the each of the path by averaging the total node cost of that specific path. The disclosed method allows the path selection become more comprehensive in contrast to the conventional approach to forward the pack using the shortest path without taking into account of others factors such as bandwidth of the node, inter and intra network interference, condition of the neighboring node and the like.

Another object of the present invention is to offer a wireless mesh network featuring better integration in between the network and machine layers. Particularly, the disclosed system possesses mesh node capable of self-calculating node cost based on a set of given equations and exchanging the calculated node cost to the neighboring nodes to have the calculate node cost stored in the routing table. At least one of the preceding objects is met, in whole or in part, by the present invention, in which one of the embodiments of the present invention is a method of spectrum aware routing for data packet delivery from a source to a destination in a wireless mesh network comprising the steps of initializing the mesh network, having a plurality of interconnected multi-interface nodes, by discovering peering in between the nodes that a plurality of paths are formed through linking neighboring nodes to deliver the data packet; selecting a channel meeting a predetermined requirement from a plurality of accessible channels; computing node cost for each node based on radio condition, channel quality and network utilization of the respective node; computing link cost by accumulating or averaging node costs of each path; and routing the data packet through the path with lowest computed link cost or any of the path w h computed link cost lower than a preset threshold.

In one embodiment, the selecting step is ranking the accessible channels according to interference value of the channels and selecting the channel with minimal interference value by measuring signal strength of the neighboring nodes in the proviso of all accessible channels are occupied.

In one embodiment, the selecting step further comprises the step of advertising selected channel to neighboring nodes and utilizing the selected channel upon determining the selected channel having matrix lower than a preset value. In one embodiment, the selecting step further comprises the step of advertising selected channel to neighboring nodes and re-selecting the channel with second minimal interference value in the presence of co-channel interference and utilizing the re-selected channel upon determining the re-selected channel having matrix lower than a preset value.

Still, in one embodiment, the disclosed method further includes the step of establishing a routing table, in each node, storing information regarding the link cost of each path. Preferably, the routing table are periodically updated following re-calculating of the node cost of each node and link cost at a predetermined frequency. More preferably, the step of re- calculating the node cost of the node and related link cost are triggered upon detecting losing or introducing of a neighboring node.

In one embodiment, the node cost is calculated from an equation of

Node cost = a[f(radio)] + P[f(channel)] +χ ^network)]

that f(radio) is a function to derive a first value related to radio condition of the node; f(channel) is a function to derive a second value related to channel quality of the node; f( network) is a function to derive a third value related to network utilization of the node; and α, β and χ are numerical values. Preferably, the derived first value is conversely related to signal strength of the neighboring nodes and inversely related to relative interference quality from the surrounding nodes while the derived second value is conversely related to packet error rate of the channel of the node and inversely related to delay spread and fading condition of the channel of the node. Likewise, the derived third value is conversely related to available capacity and largest available capacity of the neighboring node and the traffic type.

According to another preferred embodiment, the disclosed invention is a wireless mesh network for routing a data packet from a source to a destination comprising a plurality of interconnected mu i- interface nodes configured to initialize the mesh network by discovering peering in between the nodes that a plurality of paths are formed through linking neighboring nodes to deliver the data packet, select a channel meeting a predetermined requirement from a plurality of accessible channels, compute a node cost for individual node based on radio condition and channel quality as well as network utilization of the respective node, compute a link cost to for each path and route the data packet through the path with lowest computed link cost or any of the paths with computed link cost lower than a preset threshold characterized in that the link cost is computed by averaging node costs of each path. Preferably, the node cost is calculated from an equation of

Node cost = a[f(radio)] + [f(channel)] +χ ^network)]

that f(radio) is a function to derive a first value related to radio condition of the node; f(channel) is a function to derive a second value related to channel quality of the node; f(network) is a function to derive a third value related to network utilization of the node; and α, β and χ are numerical values.

In one embodiment, the node ranks the accessible channels according to interference value of the channels and selects the channel with minimal interference value by measuring signal strength of the neighboring nodes in the proviso of all accessible channels are occupied. In addition, the node also advertises the selected channel to neighboring nodes and utilizes the selected channel upon determining the selected channel having matrix lower than a preset value. In one embodiment, the node advertises selected channel to neighboring nodes and re-selects the channel with second minimal interference value in the presence of co-channel interference and utilizes the re-selected channel upon determining the re-selected channel having matrix lower than a preset value. In one embodiment, the node establishes a routing table for storing information regarding the node cost of neighboring nodes.

Brief Description Of The Drawings

Figure 1 is a flowchart generally showing the step carried out in the disclosed method; Figure 2 is a block diagram further detailing one embodiment of step (A) shown in figure 1 ;

Figure 3 is a block diagram further detailing one embodiment of step (B) shown in figure 1 ;

Figure 4 is a block diagram further detailing one embodiment of step (C) shown in figure 1; Figure 5 shows the improved integration of the network and machine layer in the one embodiment of the node in the disclosed system; and

Figure 6 shows one embodiment of the present invention in selecting route with lowest link cost.

Detailed Description Of The Invention

One skilled in the art will readily appreciate that the present invention is well adapted to carry out the objects and obtain the ends and advantages mentioned, as well as those inherent therein. The embodiment describes herein is not intended as limitations on the scope of the invention.

The term "neighboring node" used herein throughout of the specification refers to adjacent node surrounding and capable of communicating with a given node in a mesh network. Preferably, the disclosed invention is applicable for both wired and wireless network.

The present invention discloses a method of spectrum aware routing for data packet delivery from a source to a destination, as shown in figure 1, in a wireless mesh network comprising the steps of initializing the mesh network (10), having a plurality of interconnected multi- interface nodes, by discovering peering in between the nodes that a plurality of paths are formed through linking neighboring nodes to deliver the data packet; selecting a channel meeting a predetermined requirement from a plurality of accessible channels (20); computing node cost (34) for each node based on radio condition, channel quality and network utilization of the respective node; computing link cost (30) by accumulating node costs of each path; and routing the data packet (50) through the path with lowest computed link cost or any of the path with computed link cost lower than a preset threshold. In another embodiment, the disclosed method may involve additional processing approach at the link cost computing through accumulating node costs of each potential path followed by dividing the accumulated node cost of each path with the number of involved nodes in the respective path to better reflect the actual link cost incurred by the path. Still, in another embodiment, the link cost is acquired though firstly calculating the cost, hop cost, involved in a single hop between two neighboring nodes. The disclosed method averages the respective node cost of the two neighboring nodes to derive the hop cost. Further, the link cost is derived by accumulating all the hop costs of each single possible path to determine the best route to have the packet data transmitted as shown in figure 6. For example, in figure 6, the gateway has three different neighboring nodes, namely node C, node D and node E, for transmission of a packet data that the hop cost of each connection respectively has a value of 6, 3 and 10. Further, the packet data can be delivered using three different routes Gateway— >C→B→A→AP, Gate way→D→B→A→AP and Gateway→E→A→AP. Implementation of the disclosed method in the route selection shall render the mesh network to opt the route of Gateway→D→B→A→AP involving three hops with the lowest cost of 1 1 though route Gateway→E→A→AP only requires two hops having relatively higher link cost of 13. Prior to routing the packet data, the disclosed method is configured to select the best available path based on the computed link cost (40). In order to continuously optimize the data transmission, the disclosed method also carries out the necessary steps of maintain the best route selection by re-selection of the channel and re-calculation of the link cost at a predetermined interval (60).

The muhi-interface node of the disclosed method is equipped with multiple communication modules to enable communication with the neighboring node or a gateway via different wireless protocols. Preferably, the node possesses 802.1 Is radio aware module which permits the node to function in both station mode and access point mode in packet forwarding. As in setting forth, the disclosed method may have the nodes and wireless gateway to discover available surrounding nodes (10) in the mesh network to from the needed paths for forwarding the data packet from the source to the destination. It is important to be noted that the receiving node accepted the forwarded packet turn from a destination node to a source node to further forward the packet to the subsequent neighboring node, the next destination node, until the packet reaches the client. Preferably, no calculation or analysis is conducted at the peering stage but solely finding or scanning the potential nodes (21) can be used to forward the packet. Having the neighboring nodes discovered, the disclosed method begins with channel allocation and selection (20) that the best available channel for transmitting the packet is chosen at this stage. Specifically, the multi- interface nodes in the disclosed method are able to communicate through different transmission interfaces or channels distributed in different radio spectrum. With such capabilities, the nodes of the present invention can flexibly allocate the transmission to the best or second best available accessible channel to effectively forward the packet. Referring to figure 2, the disclosed method starts to locate idle channel or radio spectrum without transmitting any data. Once the idle accessible channel is found available, the selecting step (25) in the disclosed method prompts the involved node to advertise (26) the selected channel to neighboring nodes and utilizes the selected channel upon determining the selected channel having matrix lower than a preset value (28) to ensure the packet data can be encoded and delivered through the channel free from substantial problems. Preferably, the channel matrix of the present invention is derived from channel quality indicator (CQI) in the wireless mesh network.

In the condition where no idle channel or all accessible channels are occupied, the selecting step begins to rank the accessible channels (23) according to interference value of the channels and selecting the channel with minimal interference value by measuring signal strength of the neighboring nodes. Particularly, the nodes have to determine the best available occupied channel to perform the packet forwarding in the presence of other transmission being carried out in the same channel by other nodes. Preferably, the disclosed method determines quality of each occupied channel and their respective interference to compute an interference value for each occupied channel. Then the disclosed method sorts or ranks (23) the occupied channels in accordance with the respective computed interference value and further allocates or selects (24) the channel ranked with the minimal interference value for transmission of the packet followed by advertising as well as matrix determining. Due to time varying nature of wireless channel, the channel quality and interference value will fluctuate. For instance, Channel 1 may have channel quality value of lOdB and interference value of 5dB; Channel 3 may have channel quality value of 8dB and interference value of lOdB. Thus Channel 1 will be selected and it has higher rank compared to Channel 3. More preferably, the disclosed method may compel the involved node to utilize the second best occupied channel instead the best occupied channel once detecting existence of unresolvable conflict in the transmission using the best occupied channel owing to co-channel interference. In short, the selecting step may further comprises the step of advertising selected channel (26) to neighboring nodes and re-selecting the channel with second minimal interference value in the presence of co-channel interference (27) and utilizing the re-selected channel (29) upon determining the re-selected channel having matrix lower than a preset value (28). This is important to coordinate with neighboring nodes to achieve overall network optimization by selecting second best channel for the purpose of avoiding co-channel interference with its nearest neighbors.

After finishing in finding the best or second best available channel, the disclosed method proceeds to link cost calculation (30) to identify the best path from the plurality of available paths (40) to forward the packet from the involved node. The disclosed method preferably computes node cost (34) for each of the nodes forming the plurality of path and derives the link cost (35) of each path by accumulating the node costs of the nodes of one path. With the involved source node surrounded by multiple neighboring nodes, link cost for each potential single hop is calculated and the hop or path with the lowest link cost is utilized to forward the packet. In another embodiment, the disclosed method may involve additional processing approach at the link cost computing through accumulating node costs of each potential path followed by dividing the accumulated node cost of each path with the number of involved nodes in the respective path to better reflect the actual link cost incurred by the path. Still, in another embodiment, the link cost is acquired though firstly calculating the cost, hop cost, involved in a single hop between two neighboring nodes. The disclosed method averages the respective node cost of the two neighboring nodes to derive the hop cost. Further, the link cost is derived by accumulating all the hop costs of each single possible path to determine the best route to have the packet data transmitted as shown in figure 6. For example, in figure 6, the gateway has three different neighboring nodes, namely node C, node D and node E, for transmission of a packet data that the hop cost of each connection respectively has a value of 6, 3 and 10. Further, the packet data can be delivered using three different routes Gateway→C→B→A→AP, Gateway→D→B-→A→AP and Gateway→E→A→AP. Implementation of the disclosed method in the route selection shall render the mesh network to opt the route of Gateway→D→B→A→AP involving three hops with the lowest cost of 11 though route Gateway→E→A→AP only requires two hops having relatively higher link cost of 13. Showing in figure 3 is the process flow to compute the node and link costs. The disclosed method preferably computes the node cost (34) in regards to three different aspects affecting performance of a node namely the ratio condition, the channel quality, and the network utilization. Though figure 3 shows the disclosed method begins the node cost computation by evaluating the radio condition (31) followed with channel quality (32) and network utilization (33), the sequence of the evaluation can be arbitrarily arranged in other embodiments of the present invention. Preferably, the node cost is calculated from an equation of

Node cost = <x[f(radio)] + P[f(channel)] +χ ^network)] , wherein the f(radio) is a function to derive a first value related to radio condition of the node (31); f(channel) is a function to derive a second value related to channel quality of the node

(32) ; f(network) is a function to derive a third value related to network utilization of the node

(33) ; and α, β and χ are numerical value. In more specific, the first value is derived from an equation of f(radio) = (Signal_Strength_dBm/Signal_Strength REF) - SUM (Intf n/Intf REF) X n that the derived first value is conversely related to signal strength of the neighboring nodes and inversely related to relative interference quality from the surrounding nodes. Similarly, the second value is calculated using an equation of f(channel) = Packet_Error_Rate - (Delay Spread dB/Delay_Spread_REF) - Fading that the derived second value is conversely related to packet error rate of the channel of the node and inversely related to delay spread and fading condition of the channel of the node. Still, the third value can be calculated using the following equation of f(network) =(Available_Capacity+Best_Neighbour_Capacity/ Total_Capacity)+Traffic_Type that the derived third value is conversely related to available capacity and largest available capacity of the neighboring node and the traffic type. Typically, traffic types of the present invention can be classified as real time, non-real time and best effort, whereby the requirement for latency and throughput are different.

Upon acquiring the node costs and link costs, the disclosed method preferably has each node in the mesh network to establish or update a routing table storing the routing information (41). The routing table in the present invention is fashioned to store the calculated nodes costs of the neighboring nodes and also link costs to forward the packet to each neighboring node. Particularly, the disclosed method additionally has the step of establishing a routing table, in each node, storing information regarding the link cost of each path. The nodes may share the parameter information regarding node costs and link costs stored with other neighboring nodes for joint optimization in the routing the packet (42). Having the routing table established, the disclosed method proceeds to determine the lowest link cost by comparing the parameters (43), or summarized parameters in the form of node or hop costs in the more preferred embodiment, of the involved mesh node in the network. With the comparison performed, the disclosed method may select the best route from each possible node and establish the multi-hop path transmission from the source to destination (44). The best route of each possible transmitting mesh node may be determined relying on the cost, hop cost, involved in a single hop between two neighboring nodes as mentioned above. The hop cost is obtained through averaging node costs of two neighboring node forming a link of single hop. According to one preferred embodiment, the present method may further comprise the step of updating routing table at a predetermined frequency (45). The disclosed method is set to periodically re-compute the node and link cost even in the absence of substantial change in the structures of the mesh network that re-calculating the node cost of each node and link cost is performed at a predetermined frequency. More preferably, the re-calculating step may be initiated in line with changes in the mesh network. For example, the disclosed method recalculates the node cost of the node and related link cost upon detecting losing or introducing of a neighboring node or even disconnection of a path.

Pursuant to another preferred embodiment, the present invention includes A wireless mesh network for routing a data packet from a source to a destination comprising a plurality of interconnected multi-interface nodes configured to initialize the mesh network by discovering peering in between the nodes that a plurality of paths are formed through linking neighboring nodes to deliver the data packet, select a channel meeting a predetermined requirement from a plurality of accessible channels, compute a node cost for individual node based on radio condition and channel quality as well as network utilization of the respective node, compute a link cost to for each path and route the data packet through the path with lowest computed link cost or any of the paths with computed link cost lower than a preset threshold characterized in that the link cost is computed by averaging node costs of each path. In accordance with another embodiment, the disclosed network may have the link cost computed through accumulating node costs of each potential path followed by dividing the accumulated node cost of each path with the number of involved nodes in the respective path to better reflect the actual link cost incurred by the path. Still, in another embodiment, the link cost can be acquired though firstly calculating the cost, hop cost, involved in a single hop between two neighboring nodes and averaging the respective node cost of the two neighboring nodes to derive the hop cost. Further, the link cost is derived by accumulating all the hop costs of each single possible path to determine the best route to have the packet data transmitted

Like in the foregoing, the node ranks the accessible channels according to interference value of the channels and selects the channel with minimal interference value by measuring signal strength of the neighboring nodes in the proviso of all accessible channels are occupied in one of the embodiments. The best available occupied channel is thus shared to forward the packet. Moreover, in the case of persisted unresolvable co-channel interference in the shared best available channel, the node in the disclosed system is prompted to utilize the second best available occupied channel. The second best available channel will be shared by two or more nodes for transmission in such scenario. Specifically, the node advertises selected channel to neighboring nodes and re-selects the channel with second minimal interference value in the presence of co-channel interference and utilizes the re-selected channel upon determining the re-selected channel having matrix lower than a preset value. More preferably, the channel selected is scanned for its compliance in regards to transmitting encoded information that the matrix of the selected channel has to fall within an acceptable range to enable the transmission. Thus, in one embodiment, the node advertises the selected channel to neighboring nodes and utilizes the selected channel upon determining the selected channel having matrix lower than a preset value.

As in setting forth, the node cost is calculated from a formula of

Node cost = a[f(radio)] + β[ί( channel)] +χ f(network)]

that f(radio) is a function to derive a first value related to radio condition of the node; f(channel) is a function to derive a second value related to channel quality of the node; f( network) is a Sanction to derive a third value related to network utilization of the node; and α, β and χ are numerical values. Having the node costs and link costs computed, the disclosed system preferably establishes or updates a routing table in each node of the mesh network. Preferably, the routing table in the present invention is fashioned to store the calculated nodes costs of the neighboring nodes and also link costs to forward the packet to each neighboring node. Particularly, the node establishes a routing table for storing information regarding the node cost of neighboring nodes. The nodes in the present system may share the information regarding node costs and link costs stored with other neighboring nodes for joint optimization in the routing the packet. According to one preferred embodiment, the node updates the routing table at a predetermined frequency even without of substantial change in the structures of the mesh network. The nodes re-calculate the node cost and link cost at a predetermined frequency. More preferably, the nodes may be initiated to perform the re-calculation following changes in the mesh network. The changes can be losing or introducing of a neighboring node or even disconnection of a path.

It is to be understood that the present invention may be embodied in other specific forms and is not limited to the sole embodiment described above. However modification and equivalents of the disclosed concepts such as those which readily occur to one skilled in the art are intended to be included within the scope of the claims which are appended thereto.