Mobile access node routing selections through a mesh network

FIELD OF THE INVENTION

0001The invention relates generally to wireless communications. More particularly, the invention relates to a method and apparatus of mobile access node routing selections through a mesh network.

BACKGROUND OF THE INVENTION

0002Packet networking is a form of data communication in which data packets are routed from a source device to a destination device. Packets can be networked directly between a source node and a destination node, or the packets can be relayed through a number of intermediate nodes.

0003A wireless network can include a wireless device being connected to a network through a base station that is wired to the network. The wireless device can transmit data packets that are received by the base station and then routed through the network. The wireless network can include many base stations that are each wired to the network.

0004<figref idref="DRAWINGS">FIG. 1</figref> shows a prior art mesh network that includes a gateway <b>110</b> connecting a client device <b>140</b> to a network (internet) <b>100</b> through fixed access nodes <b>120</b>, <b>130</b>. The connections between the gateway <b>110</b> and the access nodes <b>120</b>, <b>130</b> can be wireless. Additionally, the connection between the access nodes <b>120</b>, <b>130</b> and the client <b>140</b> can be wireless. Wireless connections typically are subject to conditions that can make the connections unreliable. Such conditions include fading, multi-path and signal interference.

0005Each of the access nodes of the mesh network can have several possible paths to a gateway. Each access node must select a route which desirably is the best possible route to a gateway.

0006Some mesh networks can additionally include mobile access nodes. Mobile access nodes add another layer of complexity because typically optimal routes continually change for mobile access nodes. Therefore, the routing selection for a mobile access node is more complex than the routing selection for a fixed access node.

0007Mobile access nodes are generally engineered to be mounted inside automotive vehicles and draw power from the battery of the vehicle. They are also engineered to meet environmental and thermal specifications relevant to the automotive environments. By contrast, fixed access nodes are typically engineered to be mounted on streetlights, utility poles, cable strands and the like and to accept a wide variety of AC and DC voltages. They are typically engineered to meet a different set of environmental specifications including different thermal requirements, wind-loading, lightning- and surge-protection, etc.

0008It is desirable to have a wireless mesh network that includes fixed and mobile access nodes, that continually analyzes the quality of routing paths through the wireless mesh network, and selects an optimal path from among all available routing paths.

SUMMARY OF THE INVENTION The invention includes systems and methods of mobile node routing through a mesh network.

0009An embodiment includes a method of a mobile access node selecting a routing path through a mesh network. The method includes receiving routing packets from at least one upstream access node, the routing packets including information of at least one upstream access node along a path to a gateway access node. A weight is assigned to each received routing packet, wherein the weight is dependent on how recently the routing packet is received. A packet success rate is calculated for each upstream access node by summing routing packets weights over a period of time for each upstream access node. The mobile node selecting the routing path through one of the at least one upstream access node based upon the packet success rate of routing packets received from each upstream access node.

0010Another embodiment includes a method of selecting routing paths through a wireless mesh network comprising fixed access nodes and mobile access nodes. The method includes at least one gateway access node originating routing packets at a predetermined rate. Each fixed access nodes selects an upstream route through an upstream fixed access node based upon a packet success rate of routing packets received from at least one upstream access node. Each mobile access nodes assigns a weight to each received routing packet, wherein the weight is dependent on how recently the routing packet is received. The mobile nodes calculate a packet success rate for each upstream access node by summing routing packets weights over a period of time for each upstream access node. The mobile nodes select the routing path through one of the at least one upstream access node based upon the packet success rate of routing packets received from each upstream access node.

0011Other aspects and advantages of the present invention will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the invention.

BRIEF DESCRIPTION OF THE DRAWINGS

0012<figref idref="DRAWINGS">FIG. 1</figref> shows a prior art mesh network.

0013<figref idref="DRAWINGS">FIG. 2</figref> shows a wireless network that includes fixed access nodes and mobile access nodes.

0014<figref idref="DRAWINGS">FIG. 3</figref> is a flow chart that includes steps of an exemplary method for mobile access node routing selection through a mesh network.

0015<figref idref="DRAWINGS">FIG. 4</figref> shows a wireless network that includes possible routing selections that can be made between clients and gateways.

0016<figref idref="DRAWINGS">FIG. 5</figref> is a flow chart showing an exemplary method of selecting routing paths through a wireless mesh network that includes fixed access nodes and mobile access nodes.

Detailed Description

0017As shown in the drawings for purposes of illustration, the invention is embodied in an apparatus and method for mobile access nodes analyzing a quality of routing paths of a wireless network that includes fixed access nodes and mobile access nodes, and selecting an optimal path from among all available routing paths.

0018Mobile access nodes can be used to extend the coverage area afforded by the fixed access nodes. In addition, mobile access nodes can also provide network connectivity to client devices which are either wireless-enabled or are directly plugged into an Ethernet port on the mobile access node. Mobile access nodes can connect wirelessly to the mesh network and join it through fixed or mobile access nodes.

0019Fixed access nodes are typically mounted on streetlights, utility poles, cable strands and the like. An embodiment of mobile access nodes are designed to be mounted inside an automobile, typically in the trunk, and drawing power from the battery of the automobile. Fixed access nodes can connect together wirelessly to form a mesh network that provides coverage to wireless client devices such as laptops or PDAs equipped with wireless radios. A fraction of the fixed access nodes can have provisioned backhaul over fiber or Ethernet or WiMax or other point-to-point or point-to-multipoint wireless backhaul.

0020<figref idref="DRAWINGS">FIG. 2</figref> shows a wireless mesh network that includes fixed access nodes and mobile access node. The wireless mesh network includes gateways <b>220</b>, <b>222</b>. The gateways <b>220</b>, <b>222</b> are connected to a wired network <b>210</b>. The gateways <b>220</b>, <b>222</b> can be either wired or wirelessly connected to the wired network <b>210</b>. The wired network <b>210</b> can be the internet, or can be connected to the internet. As will be described later, the gateways originate routing beacons (packets) at a predetermined rate, such as, four routing beacons per second.

0021The mesh network further includes access nodes <b>230</b>, <b>232</b>, <b>234</b>, <b>236</b>, <b>240</b>, <b>242</b>. The access nodes can include fixed access nodes <b>230</b>, <b>234</b> and mobile access nodes <b>232</b>, <b>236</b>, <b>240</b>, <b>242</b>. The fixed access nodes <b>230</b>, <b>234</b> remain in a relatively stable location with respect to the rest of the network. The mobile access nodes <b>232</b>, <b>236</b>, <b>240</b>, <b>242</b> can move their locations with respect to the rest of the network.

0022Clients <b>250</b>, <b>252</b>, <b>254</b> can be wired or wirelessly connected to the access nodes <b>230</b>, <b>232</b>, <b>234</b>, <b>236</b>, <b>240</b>, <b>242</b>. A shown in <figref idref="DRAWINGS">FIG. 2</figref>, a first client <b>250</b> is wirelessly connected to the fixed access node <b>230</b>, a second client <b>252</b> is wirelessly connected to the mobile access node <b>232</b>, and a third client <b>254</b> is wired connected to the mobile access node <b>240</b>.

0023Allowing mobile access nodes to move relative to the rest of the mesh network requires the mesh network to be dynamic. The routing selections between gateways and clients should be continually monitored and reselected. Additionally, mobile access nodes and clients should be able to move within the network without the clients being required to carry special hardware or software.

0024<figref idref="DRAWINGS">FIG. 3</figref> is a flow chart the shows an exemplary method of mobile access node routing through a mesh network. A first step <b>310</b> includes receiving routing packets from at least one upstream access node, the routing packets including information of at least one upstream access node along a path to a gateway access node. A second step <b>320</b> includes assigning a weight to each received routing packet, wherein the weight is dependent on how recently the routing packet is received. A third step <b>330</b> includes calculating a time-weighted packet success rate for each upstream access node by summing routing packets weights over a period of time for each upstream access node. A fourth step <b>340</b> includes the mobile node selecting the routing path through one of the at least one upstream access node based upon the packet success rate of routing packets received from each upstream access node.

0025Gateways broadcast routing packets at a predetermined rate. Access nodes (other than gateway access nodes) rebroadcast routing packets at a rate at which routing packets are received from selected upstream access nodes. Since access nodes only rebroadcast routing packets that are successfully received from the selected upstream access node, any node further downstream receive these routing packets at a rate that effectively incorporates the quality of the path from the receiving node back to the gateway (end to end path quality). In one embodiment, four routing packets are broadcast every second. Generally, the most recently received routing packet is assigned a greatest weight. The packet success rate can be calculated by summing the weights and dividing by a maximum possible value of the summed packet weights over a predetermined amount of time. The routing packets are broadcast by a gateway at a predetermined rate. Knowing the predetermined rate at the gateway enables calculation of the packet success rate by comparing the number of routing packets received over an interval to the maximum number of routing packets that could have been received over that interval of time given the predetermined rate. As will be described, routing selections are preferably through upstream fixed access nodes, but can be through upstream mobile access nodes. Generally, an upstream mobile access node will only be selected if the packet success rate of the upstream mobile access node is a predetermined amount greater than the packet success rate of all upstream fixed access nodes. Persistence tests can include a short persistence test for checking that a link is alive, and a long persistence test for selecting a route. Generally, the persistence test intervals for mobile access node are shorter than a comparable persistence test intervals used by fixed access nodes of the mesh network.

0026During an access node route selection, a default next-hop access node (also referred to as default gateway) is selected. The route corresponding to the default next-hop access node is advertised by the access node making the selection by modifying the received routing beacons of the selected route, and re-broadcasting the modified routing beacons. The mobile node can modify the routing packets to include at least one of an IP address of the mobile node, a MAC address of the mobile node, an indication that the routing packet is being re-broadcast by a mobile access node, a current packet success rate, and/or a reverse link success rate. An access node can additionally determine and use reverse link qualities for path selections. The reverse link qualities can be determined through routing packet persistence tests as well. For mobile access nodes, the persistence test can include determining a reverse packet success rate.

0027When an access node or gateway receives a data packet, it inspects the destination IP address and look up the IP address in the route table of the access node. If an entry for the IP address does not exist, the access node or gateway forwards the data packet to its default gateway, also referred to as a default next hop access node.

0028A router, such as an access node, typically maintains a route table which is a list of route entries. The router (access node) performs route table lookups to determine the forwarding path for received data packets. The route table may also include a default route.

0029<figref idref="DRAWINGS">FIG. 4</figref> shows a wireless network that includes possible routing selections (both mobile access node and fixed access node) that can be made between clients and gateways. The wireless network includes gateways <b>420</b>, <b>422</b> which are coupled to the wired network <b>410</b>. The gateways <b>420</b>, <b>422</b> typically include high bandwidth connections <b>415</b> to the wired network <b>410</b> which can be wired or wireless. A gateway is an access node that can originate routing beacons, as will be described.

0030Routing Selections

0031Access nodes <b>430</b>, <b>432</b>, <b>434</b>, <b>436</b>, <b>440</b> (both fixed access nodes and mobile access nodes) are coupled either directly or indirectly to the gateways <b>420</b>, <b>422</b>. That is, each access node is either directly connected to an upstream gateway <b>420</b>, <b>422</b>, or indirectly connected through another access node to at least one of the upstream gateways <b>420</b>, <b>422</b>. The decision of which access nodes or gateways each access node is connected, can include many factors. The network of <figref idref="DRAWINGS">FIG. 4</figref> can include any number of additional gateways and access nodes. As shown in <figref idref="DRAWINGS">FIG. 4</figref>, a client <b>450</b> can obtain access to the network by establishing a connection to an available access node, such as, any of access nodes <b>430</b>, <b>432</b>, <b>440</b>.

0032Gateways <b>420</b>, <b>422</b> broadcast routing packets (beacons), which can be used to determine routing between access nodes <b>430</b>-<b>440</b> and gateways <b>420</b>, <b>422</b> of the network. The beacons are received by all first-level access nodes (for example, fixed and mobile access nodes <b>430</b>, <b>432</b>, <b>434</b>), which are access nodes that are able to receive gateway transmitted beacons, and directly route data through to a gateway. For an exemplary embodiment, the beacons originate at the gateways <b>420</b>, <b>422</b> at a predetermined rate. For example, <figref idref="DRAWINGS">FIG. 4</figref> depicts routing beacons being originated at the gateway <b>420</b> at a rate of 4 routing beacons per second. The first-level access nodes can measure the quality of the link between them and the gateways by comparing the number of routing beacons received over a period of time with the total number of beacons transmitted over the period of time. For example, the first-level access nodes can count the number of beacons received over a ten second period. This number can be compared with the number transmitted (40) over the ten second period to determine the quality of the link between the first-level access node and the transmitting gateway.

0033The beacons are used to establish a route from each access node to a gateway. The first-level access nodes re-broadcast the routing beacons, attaching their own information to the routing beacons. The first-level access nodes maintain the routing beacon transmission rate as determined by the gateways. That is, the gateways transmit the routing beacons at a rate of four per second, and the first-level access nodes re-broadcast the modified routing beacons at the same rate at which routing beacons are successfully received by the access nodes. This allows the second-level access nodes to measure the path quality between them and the gateways. The first level access nodes re-broadcast the beacons after adding first level access node information, such as the address of the first level access node. First level access nodes can be fixed access nodes or mobile access nodes. It is to be understood that there can be any number of mobile and fixed access nodes any number of hops away from a gateway.

0034Mobile Node Routing Selections

0035Due to their mobility, the transmission links of mobile access nodes are likely to change more rapidly than the transmission links of fixed access nodes. Therefore, the quality of selected routes (and non-selected routes) is likely to change more rapidly than fixed access nodes. As a result, the routing selections of the mobile access nodes should occur more often, and place a greater weight on routing beacons most recently received.

0036An example of how a mobile access node selects an upstream routing path includes the mobile access nodes receiving routing packets (routing beacons) from at least one upstream access node. As described, the routing packets including information of at least one upstream access node along a path to a gateway access node. The mobile node assigns a weight to each received routing packet, in which the weight is dependent on how recently the routing packet is received. The mobile node calculates a packet success rate for each upstream link by summing routing packets weights over a period of time for each upstream link. The mobile node selects a routing path through at least one upstream access node based upon the packet success rate of routing packets received from each upstream access node.

0037An additional packet success rate calculation can include dividing the summed routing packet weight by a maximum possible number possible for the sum.

0038The routing selections can be based at least in part upon short and long routing packet success rates. For example, a short test can be used to determine whether a link is alive. A long test can include beacons received over a longer period of time, and aid in the routing selections. For example, the short test can buffer (receive and store) ten seconds worth of received routing beacons, and a long test can buffer additional routing beacons for a total time of 40 seconds. The maximum number of beacons that can be received is set by the rate (for example, four routing beacons per second) and the period of time of reception. For fixed nodes, a routing selection typically includes counting the number of routing packets received through each upstream link, and determining the best link based on this number. As described, mobile nodes weight the routing beacons to additionally influence the routing selections based upon when the beacons were received. Typically, the mobile access nodes perform the long and short test more frequently than the fixed access node because of their mobility.

0039As will be described, mobile nodes prefers to select an upstream route through a fixed access node, but will select an upstream route through another mobile access node if the upstream mobile access node has a link quality a predetermined amount greater than the link quality of any fixed access node.

0040Due to the potential mobility of mobile access nodes, an embodiment includes preventing fixed nodes from ever selecting a link through an upstream mobile node. That is, fixed access nodes only select links and routing paths through upstream fixed nodes.

0041As previously described, the beacons are used to establish a route from each access node to a gateway. The first level access nodes re-broadcast the beacon data, attaching their own information to the beacon. The information indicates to the second level access nodes that the path to the gateway includes the first level access node. As each access node rebroadcasts the beacons, each access node adds additional information. The rebroadcast information can include the addresses of all upstream access nodes along the path to the gateway access node. That is, an embodiment includes each access node that receives routing beacons, modifying the routing beacons of a selected route by attaching an address of the access node, and re-broadcasting the modified beacons. The address can be an IP address of the access node or a MAC address of the access node. Other information can include an indication that the routing packet is being re-broadcast by a mobile access node, a current packet success rate, or a reverse link success rate.

0042For one embodiment, the link quality of the beacon received determines whether that beacon is rebroadcast by the access node. If the quality of the beacon is the best of all received beacons, it is rebroadcast. The beacons can be used to determine the quality of the link in both an upstream (towards a gateway) direction, and in a downstream (away from a gateway) direction. The upstream and the downstream link qualities can be used by each access node to select the best data routing path to a gateway. The link qualities can be influenced by other wireless transmission factors such as interference, noise and fading. Typically, the link qualities vary more for mobile access nodes than for fixed access nodes. The link qualities can be determined be calculating the percentage of beacons that are transmitted and successfully received. The link qualities can alternatively be determined by measuring a PER, BER or SNR of received routing beacons.

0043The first level access nodes <b>430</b>, <b>432</b>, <b>434</b> include upstream links in an uplink direction, and upstream links in a downlink direction to the gateways <b>420</b>, <b>422</b>. As shown in <figref idref="DRAWINGS">FIG. 4</figref>, fixed access node <b>430</b> includes a upstream link in downlink direction <b>461</b>A and an upstream link in the uplink direction <b>461</b>B with the gateway <b>420</b>, mobile access node <b>432</b> includes a upstream link in the downlink direction <b>462</b>A and an upstream link in the uplink direction <b>462</b>B with the gateway <b>420</b>, and fixed access node <b>434</b> includes a upstream link in the downlink direction <b>463</b>A and an upstream link in the uplink direction <b>463</b>B with the gateway <b>422</b>. The quality of a downlink direction link can be different than the quality of the corresponding uplink direction link. For example, the quality of the upstream link in the downlink direction <b>461</b>A can be different than the quality of the upstream link in the uplink direction <b>461</b>B, the quality of the upstream link in the downlink direction <b>462</b>A can be different than the quality of the upstream link in the uplink direction <b>462</b>B, and the quality of the upstream link <b>463</b>A in the downlink direction can be different than the quality of the upstream link in the uplink direction <b>463</b>B. Link asymmetries can arise because of differences in transmit power levels at each end of the link, or due to environmental effects or signal interference.

0044The asymmetrical characteristics of the links between access nodes (fixed and mobile) and the gateways can lead to non-optimal routing selections if, for example, the quality of the upstream links in the uplink direction is not included in routing decisions by access nodes (fixed and mobile) to gateways. Each gateway and access node transmits beacons. All access nodes and gateways that receive the beacons can make an estimate of the quality of the link based upon the reception of the beacons. The estimates can include upstream link quality in the uplink direction and in the downlink direction. Once each access node has the uplink direction and downlink direction link qualities within every possible data path to a gateway, the access node can make a selection of the best available data path.

0045As shown in <figref idref="DRAWINGS">FIG. 4</figref>, the first level mobile access node <b>432</b> routes data through the gateway <b>420</b>. However, the mobile access node <b>432</b> could have selected the gateway <b>422</b> to route data. A possible link between the mobile access node <b>432</b> and the gateway <b>422</b> includes the downlink <b>464</b>A and the uplink <b>464</b>B. The mobile access node <b>432</b> selects the gateway to route data by selecting the best combination of uplinks and downlinks. If the mobile access node <b>432</b> determines that the downlink <b>464</b>A/uplink <b>464</b>B combination of the gateway <b>422</b> is better than the downlink <b>462</b>A/uplink <b>462</b>B combination of the gateway <b>420</b>, then the mobile access node <b>432</b> can select to route date through the gateway <b>422</b>.

0046Each access node has at least one upstream node, and may have a plurality of downstream nodes. Upstream nodes are the nodes that are between the access node and the gateway. For a level one access node, there is only one upstream node, the gateway. For a level four access node, there are four upstream nodes, which define the access node's path to the gateway. Downstream nodes are nodes that receive the beacon from a particular access node, and define their path to the gateway through that access node.

0047<figref idref="DRAWINGS">FIG. 4</figref> also includes a second level mobile access node <b>440</b>. As shown, the mobile access node <b>440</b> can select a data path through mobile access node <b>432</b> (through downlink <b>465</b>A and an uplink <b>465</b>B), through fixed access node <b>434</b> (through downlink <b>467</b>A and an uplink <b>467</b>B), or through gateway <b>422</b> (through downlink <b>466</b>A and uplink <b>466</b>B). The mobile access node <b>440</b> makes a data path routing selection based upon the best quality combination of the links (downstream and upstream) and whether the upstream node broadcasting the received beacon is a fixed access node or mobile access node.

0048Routing Selections Based on Downstream and Upstream Link Qualities

0049As has been described, downstream link qualities can be determined by measuring a persistence of the routing beacons transmitted from an upstream node. For a mobile node, the beacons are weighted in which the most recently received beacon is assigned the greatest weight.

0050Upstream link qualities in the uplink direction can also be measured by persistence of routing beacons in the opposite (upstream) direction. For example, the first level access nodes <b>430</b>, <b>432</b>, <b>434</b> can transmit routing beacons at a predetermined rate which are received by upstream gateways <b>420</b>, <b>422</b>. The gateways count the received upstream beacons, and therefore, can perform a persistence test because the beacons were transmitted at a predetermined rate. The gateways can then include this upstream persistence information in their routing beacons. This way, the first level access nodes <b>430</b>, <b>432</b>, <b>434</b> can obtain information of both the downstream and the upstream link qualities. That is, the uplink information is included within the downstream link routing beacons, and the downstream link information can be determined by measuring the persistence of the downstream link routing beacons. This information (uplink quality and downlink quality) provides for a more intelligent link selection. The upstream devices that perform the upstream link persistence test can be either gateways as described, or other upstream access nodes.

0051For mobile nodes, the upstream persistence test can include a weighting of the routing beacons in which the most recently received beacons get the greatest weight. That is, an upstream device performs a packet success rate in a way that is dependent upon whether the downstream access node is a mobile access node or a fixed access node. As previously stated, the device (gateway or access node) that is upstream from the mobile access node determines the weighted packet success rate, and then includes this information within its own broadcast routing beacons, allowing the downstream mobile access node to determine link qualities of both the upstream and downstream directions of the link.

0052Beacon Selection - Fixed Access Node versus Mobile Access Node

0053Routing selections can be dependent upon whether the upstream access node is a fixed access node or a mobile access node. In one embodiment, the route selection protocol of a fixed access node can limit the fixed access node to only select a route through an upstream fixed access node, rather than through an upstream mobile access node. In another embodiment, the route selection protocol on a fixed access node can include a preference for routes through an upstream fixed access node, with a route through an upstream mobile access node only being chosen if it has a path quality that is better than any route through a fixed access node by at least a predefined margin. This behavior is desirable because routes through mobile access nodes can be inherently unstable because of the mobility of the mobile access nodes and less preferable than routes through fixed access nodes. Additionally, mobile nodes can be allowed to select routes that include both mobile access nodes and fixed access nodes upstream. Additionally, a mobile access node's routing protocol can include a preference for paths through a fixed access node as the next hop upstream router as opposed to choosing a path through an upstream mobile access node. Other routing selection protocols allow fixed access nodes to route through both upstream fixed access nodes and mobile access nodes.

0054The routing packets can be designated as beacons, and include routing information. The wireless links can utilize the 802.11 protocol, but the routing beacons are distinct from 802.11 beacons. Routing beacon originating gateways can also be access nodes.

0055<figref idref="DRAWINGS">FIG. 5</figref> is a flow chart showing an exemplary method of selecting routing paths through a wireless mesh network that includes fixed access nodes and mobile access nodes. A first step <b>510</b> includes at least one gateway access node originating routing packets at a predetermined rate. A second step <b>520</b> includes each fixed access nodes selecting an upstream route through an upstream fixed access node based upon a packet success rate of routing packets received from at least one upstream access node. A third step <b>530</b> includes each mobile access nodes assigning a weight to each received routing packet, wherein the weight is dependent on how recently the routing packet is received. A fourth step <b>540</b> includes the mobile nodes calculating a packet success rate for each upstream access node by summing routing packets weights over a period of time for each upstream access node. A fifth step <b>550</b> includes the mobile nodes selecting the routing path through one of the at least one upstream access node based upon the packet success rate of routing packets received from each upstream access node.

0056The routing selection can be performed by software operating within the access nodes. The software can be programmed to assign a weight to each routing packet received by the mobile access node, wherein the weight is dependent on how recently the routing packet is received. A packet success rate is calculated for each upstream access node by summing routing packets weights over a period of time for each upstream access node. The mobile node selects the routing path through one of the at least one upstream access node based upon the packet success rate of routing packets received from each upstream access node. Generally, the selection includes a preference for routing paths having the best (greatest) packet success rate.

0057Although specific embodiments of the invention have been described and illustrated, the invention is not to be limited to the specific forms or arrangements of parts so described and illustrated. The invention is limited only by the appended claims.