Patent Description:
Further, computing system functionality can be enhanced by a computing system's ability to be interconnected to other computing systems via network connections. Network connections may include, but are not limited to, connections via wired or wireless Ethernet, cellular connections, or even computer to computer connections through serial, parallel, USB, or other connections. The connections allow a computing system to access services at other computing systems and to quickly and efficiently receive application data from other computing systems.

Some computing systems communicate using ad-hoc mesh networks, which are typically wireless decentralized networks where the various nodes in the mesh network identify neighbor nodes to add to the network. One example of such a network is a code division multiple access (CDMA) mobile ad-hoc network (MANET).

Some MANETs are made up of smaller subnetworks (sometimes referred to as subnets). Often there are disjoint subnets, or even subnets made up of a single individual node, that exist where it is desirable to join the disjoint subnets into the same MANET. For any node that is outside of the MANET range to join the MANET, information is exchanged. Thus, there is typically some type of a side channel used for node discovery purposes. In particular, whenever the MANET increases its range to bring in another node or subnet, it must increase its power and/or decrease its rate, and thus communication indicating power and/or rate changes are needed. Increasing the power has a negative consequence for network interference in a CDMA MANET. Further, reducing the rate results in a slower network, meaning that latency is higher.

New neighbors being added to a mesh network are outside of the current range of a data-bearing transmission. In some systems, a distant neighbor discovery technique is achieved using a multi-channel waveform implementation, where one channel (referred to herein as the traffic channel) is used to convey user data (i.e., data for use of users of nodes in a network) and the second channel (referred to herein as the probe channel) is used to facilitate acquisition of new neighbors. Power and rate (PAR) information with respect to channels can be exchanged in messages between nodes. For example, a node can indicate to other nodes power levels and data rates at which data is being sent and/or received. Further, messages can be provided between nodes where a node can indicate the signal to noise ratio for received data for the node.

The coverage area of the network probe channel is limited to the operational power of the individual nodes. General practice in a CDMA MANET is to minimize transmit power while still achieving network objectives in order to keep CDMA interference low. This may be problematic as nodes in subnets may be orders of magnitudes further away from nodes in other subnets than they are from nodes in their current subnet. This results in many individual nodes needing to transmit at high power and/or low data rates to communicate with nodes in other subnets to couple individual subnets. Many nodes transmitting at higher power creates interference problems for a CDMA MANET.

Prior art can be found in <CIT> which generally relates to a method for facilitating communication between nodes belonging to different wireless networks.

<CIT> relates to determining whether there is a frequency overlap between two ad-hoc networks after the merging of said networks.

<CIT> relates to inter-gateway interference and admission control in a CDMA satellite system, wherein a gateway receives return link signals from connected user terminals.

According to a first aspect, we describe a method of joining a first subnet and a second subnet in a mobile ad-hoc network, MANET, wherein the joining of the first subnet and the second subnet causes a new subnet to be created, the method comprising a first gateway node performing the following: based on SNR, power and data rate information between the first gateway node for a first subnet and a second gateway node for a second subnet, determining, by the first gateway node, a rate at which the second gateway node connect to the first gateway node if nodes in the first subnet reduce a signal transmit rate to a predetermined level; and as a result of determining that the determined rate meets or exceeds a predetermined threshold, then joining, by the first gateway node, the first and second subnets via the first and second gateway nodes and causing, by the first gateway node, nodes in the first subnet to reduce the signal transmit rate to the predetermined level.

Embodiments illustrated herein join disjoint subnets by causing gateway nodes in different subnets to communicate with each other to determine achievable rates between the gateway nodes (rather than requiring each of the individual nodes in different subnets to communicate with each other to join subnets), and if the rates are sufficient, then to join the subnets. In particular, gateway nodes are elected to search for disjoint subnets. When another subnet is discovered, the local gateway node determines whether or not the forward and return link to the remote gateway can be made at a suitable rate. If the rate is below the acceptable threshold, the local gateway does not sacrifice performance in its subnetwork to accommodate a remote gateway that is out of effective range. Embodiments can determine that the local gateway node can increase the rate received by the remote gateway node. Further, embodiments can determine if a forward link (local to remote) has a high enough potential rate to be useful. Further embodiments can determine if a return link (remote to local) has a high enough potential rate to be useful.

Thus, embodiments are implemented where gateway nodes can estimate the achievable rate between gateway nodes in the subnets. Rates are estimated both for forward (data sent from a first gateway to a second gateway) and return (data received by the first gateway from the second gateway) links. In some embodiments, it is assumed that the gateway nodes have exchanged messages providing information about signal power and/or data rate between nodes, and signal to noise ratio (sometimes expressed as Eb/N<NUM>, which is energy per bit divided by noise power spectral density) feedback, as described in more detail below. Note that in other embodiments, other signal to noise ratios may be used, such as Es/N<NUM>, which is based on the energy per symbol instead of the energy per bit. In some embodiments all signal to noise ratio feedback will be treated as traffic signal to noise ratio except for the gateway's signal.

In some embodiments, the potential rates are calculated with the assumption that each gateway will command neighboring nodes in their respective subnets to turn down to some predefined minimum acceptable rate (e.g. <NUM> kbps).

In some embodiments, one piece of information used for estimating rate is the total power measured after filtering. The total power is usually a value that is only measured locally, but for the calculations illustrated herein, it is assumed that the maximum total power value (i.e., the total power that the node is allowed to transmit) is being transmitted via an appropriate message. This maximum total power value is communicated inasmuch as it could be different from node to node. The value could also vary in time, so it is updated periodically. As another option, the gateway could transmit an equivalent parameter or set of parameters could be transmitted that would allow the maximum total power to be calculated. For example, once such parameter might be power headroom or the potential rate. In some embodiments, the rate may be expressed using a processing gain index (PGI) where supported rates are indexed aganst an index number. In such systems, fewer bits can be sent in the message by sending only the index number as opposed to the actual rate value.

Referring now to <FIG>, in the topology <NUM>, nodes 104G1 and 104G2 are gateway nodes, for different subnets <NUM>-<NUM> and <NUM>-<NUM> respectively. Both of nodes 104G1 and 104G2 have neighbors in their respective subnets, but only the neighbor connections relevant to these potential rate calculations are represented, which are the neighbors that are transmitting at the same center frequency as the remote gateway node and have a direct connection with the local gateway node. Node 104G1 transmits at the center frequency represented by the squares and node 104G2 transmits at the center frequency represented by the triangles. Node 104G1 has neighbor nodes 104D, 104E, and 104F that are also transmitting at the triangle center frequency. Node 104G2 has neighbor nodes 104A, 104B, and 104C that are transmitting in the square center frequency. Node 104G1 receives a message from node 104G2 with signal to noise ratio and rate information for nodes 104G1, 104A, 104B, and 104C.

Gateway link management controls the acquisition and maintenance of links between disjoint subnets within a MANET. As illustrated, one gateway node is selected, such as by example by performing a node election, from each subnet to reach out beyond the subnet in search of disjoint subnets. Connectivity between disjoint subnets is managed between selected gateway nodes.

A local gateway node can throttle the rate of nodes, in its subnet, transmitting at the same center frequency as the remote gateway in order to improve the potential rate of the return link. Once the local gateway hears a remote gateway (usually through the probe channel), it estimates the traffic channel rate that the remote gateway would be able to transmit, assuming that the local gateway throttles the rate of the local subnet nodes that would interfere with the remote gateway. This estimated remote transmit rate is sent to the remote gateway. Thus, for example, gateway node 104G1 may be the local gateway node, and can throttle the data rates of nodes 104D, 104E, and 104F. Gateway node 104G2 (which in this example is the remote gateway node) may send a probe message which is received by gateway node 104G1. Gateway node 104G1 can then estimate the traffic channel rate for the traffic channel <NUM>. This estimated rate is sent from gateway node 104G1 to gateway node 104G2. Note that the traffic channel estimated rate returned by 104G1 is only for 104G2 to 104G1. There is a separate rate that goes in the opposite direction 104G1 to 104G2 that can be determined in a similar fashion.

After the traffic channel rates are estimated and exchanged, gateway nodes will check if both sides can operate above the predetermined threshold rate. If so, the gateway nodes elect to form a link and proceed to throttle local (with respect to each gateway) nodes and modify their own power and rate (PAR).

Once the gateway link is established, the gateway node manages the maximum rate of its subnet neighbors that are transmitting on the remote gateway's transmit frequency such that they do not exceed the rate achieved by the incoming gateway link. This management process continues until the gateway link can no longer achieve the threshold rate or the disjoint subnets merge.

In the example illustrated in <FIG>, nodes 104G1 and 104G2 are gateway nodes for different disjoint subnets <NUM>-<NUM> and <NUM>-<NUM>.

Nodes 104G1 and 104G2 have exchanged initial messages <NUM> with data sufficient to determine SNR (signal to noise ratio), power (and in some cases maximum power) and data rate information and are evaluating the link <NUM>, which as discussed previously includes two directions where each direction is evaluated separately using the principles illustrated herein, as they are not identical. In particular, Node 104G1 can send a message with data sufficient to determine SNR, power and data rate information indicating the SNR and rate for the data channel for data received by node 104G1 from node 104G2. Similarly, node 104G2 can send an SNR message indicating the SNR for the data channels for data received by node 104G2 from node 104G1.

Node 104G1 is transmitting at the same center frequency as nodes 104A, 104B, and 104C in subnet <NUM>-<NUM>.

Node 104G2 is transmitting on a different center frequency than node 104G1 (hence the triangle instead of the square). Node 104G2 may have neighbors at another center frequency as well, but they are not of interest in this example because they do not interfere with the signal coming from node 104G1. Node 104G2 calculates the data rate that it could receive data (at some threshold SNR) from node 104G1 if nodes 104A, 104B, and 104C were throttled back to some minimum acceptable rate. It is preferable that node 104G2 does not throttle the rates back until node 104G1 is actually in range because, otherwise this would degrade network performance. The following now illustrates calculations that can be performed on node 104G2 (or in some embodiments, node 104G1, or some other alternate processor, and results passed to node 104G2). The following illustrates computations that can be performed.

For node 104G1, this value can easily be adapted as follows (using an assumed probe Eb/N<NUM>):
<MAT>.

Xsum is calculated and used to estimate the noise-plus-interference spectral density (N<NUM> +J<NUM>).

Define Xsum as the sum of all Xi values. Note that Xsum is the ratio of total received signal power to total received power.

The sum of the noise power spectral density and the interference power spectral density is computed as
<MAT>.

The power received from node 104G1 is
<MAT>.

In general, the power received from node i is given by
<MAT>.

The potential rate is then calculated based on the info received from node 104G1 and the anticipated back-off (Δi) associated with interfering nodes.

This equation is sufficient for an iterative search for Rpot, since PBOTr,G<NUM> depends on Rpot. The PBO depends upon the traffic rate due to the fact that the probe channel rate stays constant and embodiments set the power backoff of each channel such that they have the same range. The iterative procedure would start with PBOTr,G<NUM> being set to unity (ideal case). The resulting value of Rpot after flooring to the next valid rate will then map to a new value of PBOTr,G<NUM>. Rpot is computed again with the new value of PBOTr,G<NUM>. This process continues until the new value of Rpot after flooring is equal to the previous value of Rpot after flooring. Since successive values of Rpot should be lower in value, the algorithm can stop if the calculated Rpot is ever greater than the previous value (when oscillation between two close values occurs, either of the two values is acceptable) or less than the minimum PGI rate (indicating that there is no valid solution).

The following illustrates a derivation of the preceding principles.

The potential rate (or forward rate) that node 104G1 can achieve is computed using equations derived below, and as discussed above. The derivation has the following steps: (<NUM>) use the reported Eb/N<NUM> (or other signal to noise ratio) values to solve for the sum of the noise power density plus the unknown interference power density (i.e. N<NUM> + J<NUM>); (<NUM>) assume that all neighbors will be throttled to the same rate achievable from the remote node and calculate the potential rate. Note that this estimate of the potential rate is conservative because there could likely be nodes that are not power-control neighbors to node 104G2, which are causing unknown interference, but their power will turn down once their rate is commanded down to the minimum acceptable rate, Rmin.

(<NUM>) Express the measured Eb/N<NUM> for each identified neighbor of node 104G2, including node 104G1 (adjustments will need to be made to use the probe Eb/N<NUM> from node 104G1), and then solve for N<NUM> + J<NUM>: <MAT>
where, <MAT> <MAT> <MAT> <MAT> <MAT>.

Define Xi as the ratio of power from the ith emitter to the total received power. <MAT> <MAT>.

For node 104G1, this value can easily be adapted as follows (assuming probe Eb/N<NUM>): <MAT>.

Express the total signal power as the sum of the power from each emitter. <MAT> <MAT> <MAT>.

Define Xsum as the sum of all Xi values. Note that Xsum is the ratio of total received signal power to total received power. <MAT> <MAT> <MAT> <MAT> <MAT>.

It can be shown that PT = (RSSI)Xsum, where RSSI is the total measured power at the receiver after filtering. This results in the following expression for N<NUM> + J<NUM>: <MAT>.

(<NUM>) Calculate the new potential rate for node 104G1, assuming that node 104G2 will command all nodes to reduce their rate to the same rate achievable by node <NUM> <NUM>.

As noted previously, this equation is sufficient for an iterative search for Rpot, since PBOTr,G<NUM> depends on Rpot. The iterative procedure would start with PBOTr,G<NUM> being set to unity (ideal case). The resulting value of Rpot after flooring to the next valid rate (based on PGI) will then map to a new value of PBOTr,G<NUM>. Rpot is computed again with the new value of PBOTr,G<NUM>. This process continues until the new value of Rpot after flooring is equal to the previous value of Rpot after flooring. Since successive values of Rpot should be lower in value, the algorithm is stopped if the calculated Rpot is greater than the previous value (oscillation between two close values-either is acceptable) or less than the minimum PGI rate (no valid solution).

In order to use the same framework already described, the analysis focuses on node 104G2's calculation of node 104G1's return rate. This calculation uses the same equations as shown for the potential rate because potential rate and return rate are the same in this case, given the assumption that gateway nodes are transmitting at their maximum power. The difference in the return rate calculation is that the RSSI value is known through measurement, but the power received when node 104G1 is transmitting at maximum power, Prcvd,G<NUM>, is reported, either directly or indirectly, through messaging.

After the gateway traffic connection is established, the local gateway node (node 104G2 in the current framework) will continue to calculate the noise plus interference power density as before. In addition, the local gateway node will calculate the achievable rate for the nodes on the remote gateway's transmit frequency. As the rate changes, updates will be sent via control messages. If the achievable rate drops below the minimum allowed rate, then the minimum allowed rate should still be commanded until the gateway connection times out. After that point, the nodes resume normal operation.

After the gateway link has been established, the local gateway can gradually increase the rate of the intra-subnet neighbors until the rate is equal to the potential rate of the remote gateway. This may be achieved by a dampened response, since increasing the rate usually results in a larger increase in power due to CDMA interference. The following procedure can be performed for all gateway rate tracking, whether increasing or decreasing the rate. It should be noted that some minimum number of intervals of exchanged power and rate and/or signal to noise ratio (where each interval comprises sending power and rate information and/or signal to noise ratio information, and adjusting power and rate as appropriate) may be implemented between steps to allow nodes to settle. Any appropriate number of intervals can be implemented. The following procedure can be performed:.

The advantage to this method is that it still allows each node to make connectivity decisions as it normally would. The disadvantage of this method is that the intra-subnet nodes (i.e., node in a particular subnet) drop all the way down to the minimum acceptable rate before they can be adjusted to a steady-state value. However, if subnets are converging, the minimum acceptable rate may be the starting point for the intra-subnet nodes anyway.

The elevated latency rate is chosen as a value that will allow the subnet to meet its latency requirements. It is also selected as an achievable rate under normal operating conditions. A topology manager, which may be implemented on one of the nodes or at an external entity, tries to keep connectivity well-pruned such that nodes do not attempt to connect with every node in the subnet. Each of the nodes implements a greedy algorithm that seeks to establish its link at the desired rate at the expense of others. Due to CDMA interference, a limit on the power step size will be imposed on PAR based on the impact that the power step will cause on the node's neighbors. For instance, the maximum power step will be calculated that will cause no more than <NUM> dB of degradation to the neighboring nodes' receivers. The resulting power step value will be greater than or equal to <NUM> dB for single antenna operation.

One indicator that subnets are ready to be merged is that both gateway nodes are operating at the elevated latency rate. If this is the case, the gateway nodes would stop restricting the power control decisions of neighboring nodes, and allow connections to form in a normal manner. Each gateway node (or some other outside entity) informs its own subnet of the change, by sending a control message to add the other subnet into the node list of the local subnet. After the new subnet is formed, the gateway nodes will decide which node will remain as a gateway. This can be performed by a node election process. In some embodiments, only the original gateway nodes will be allowed to be elected. In other embodiments, the node election can select from other nodes as well.

Subnets are usually split based on command (i.e. directed by an administrative authority, such as a mission commander when each node represents military personnel). Alternatively, subnets may be split based on some external algorithm. Alternatively still, there could be cases where nodes are separated from other nodes in their subnet due to attrition. If this is the case, those nodes can form a subnet and elect a gateway node, whose responsibility it would be to reach out to other nodes.

Referring now to <FIG>, a method <NUM> is illustrated. The <NUM> includes acts for joining subnets in a mobile ad-hoc network (MANET). The method includes performing the following acts at a first gateway node. For example, the acts are performed by the gateway node 104G1 illustrated in <FIG>.

The method <NUM> includes, based on SNR, power and data rate information between a first gateway node for a first subnet and a second gateway node for a second subnet, determining a rate at which the first and the second subnets connect if nodes in the first subnet reduce signal transmit rate to a predetermined level (act <NUM>). For example, SNR, power and data rate information may be received at the gateway node 104G1 from node 104G2 for the node 104G1 and the nodes in the subnet <NUM>-<NUM> that are neighbors to node 104G2 and transmitting at the same center frequency as node 104G1. The power and rate information can be used to determine if node 104G1 can establish a traffic link to node 104G2 at the target Eb/N<NUM> with a sufficient data rate.

As a result of determining that the determined rate meets or exceeds a predetermined threshold, the method <NUM> further includes, then joining the first and second subnets by joining the first and second subnets via the first and second gateway nodes and causing nodes in the first subnet to reduce signal transmit rate to the predetermined level (act <NUM>). Thus, the subnets <NUM>-<NUM> and <NUM>-<NUM> can be joined if the sufficient rate can be achieved.

The method <NUM> may be practiced where determining the rate at which the first and second subnets can connect comprises obtaining at least a portion of the SNR, power and data rate information from the second gateway node and computing the rate at which the first and second subnets can connect. For example, the gateway node 104G2 can provide power and rate information for itself, as well as other nodes in the subnet <NUM>-<NUM>.

The method <NUM> may be practiced where determining the rate at which the first and second subnets can connect comprises obtaining the rate at which the first and second subnets can connect from the second gateway node as a result of the second gateway node computing the rate at which the first and second subnets can connect using the SNR, power and data rate information. Thus, the gateway node 104G2 can calculate the rate at which the subnets can connect based on power and rate information measured or received at the gateway node 104G2 and provide that information to the gateway node 104G1, which can then make the determination as to whether or not the subnets should join.

The method <NUM> is practiced where joining the first and second subnets causes a new subnet to be created, the method further comprising nodes in the new subnet electing a new gateway node. Thus, for example, once subnets <NUM>-<NUM> and <NUM>-<NUM> join to form a new subnet, a new gateway node can be chosen. In some embodiments, the new gateway node is only selected from existing gateway nodes. This may be done to reuse configuration already applied to the gateway node or for other reasons of efficiency. Alternatively, a new gateway node may be selected from among a set of nodes including nodes other than the gateway nodes.

The method <NUM> may be practiced where determining a rate at which the first and second subnets can connect comprises determining data rates from the first gateway node to the second gateway node and the second gateway node to the first gateway node. That is, as described above, both forward and return rates can be determined.

The method <NUM> may be practiced where the SNR, power and data rate information between the first gateway node and the second gateway node is obtained from messages transmitted on a probe channel in a multi-channel system comprising the probe channel used for identifying new neighbor nodes and a traffic channel for transmitting user data.

The method <NUM> may be practiced where determining a rate at which the first and second subnets can connect comprises performing an iterative process to identify a minimum rate.

The method <NUM> may further include, after joining the first and second subnets, the first gateway node gradually increasing the rate of the nodes in the first subnet while maintaining the threshold rate between the first and second gateway nodes. In some embodiments, this may involve the first gateway node gradually decreasing its own data rate while gradually increasing the data rates of the nodes in the first subnet. Eventually, the data rate of the first gateway may be at or around the data rates of the nodes in the first subnet.

Non-claimed embodiments within the scope of the present invention also include physical and other computer-readable media for carrying or storing computer-executable instructions and/or data structures. Thus, by way of example, and not limitation, non-claimed embodiments of the invention can comprise at least two distinctly different kinds of computer-readable media: physical computer-readable storage media and transmission computer-readable media.

When information is transferred or provided over a network or another communications connection (either hardwired, wireless, or a combination of hardwired or wireless) to a computer, the computer properly views the connection as a transmission medium. Transmissions media can include a network and/or data links which can be used to carry desired program code means in the form of computer-executable instructions or data structures and which can be accessed by a general purpose or special purpose computer.

Claim 1:
A method (<NUM>) of joining a first subnet and a second subnet in a mobile ad-hoc network, MANET, wherein the joining of the first subnet and the second subnet causes a new subnet to be created, the method comprising a first gateway node performing the following:
based on SNR, power and data rate information between the first gateway node for the first subnet and a second gateway node for the second subnet, determining (<NUM>), by the first gateway node, a rate at which the second gateway node connects to the first gateway node if nodes in the first subnet reduce a signal transmit rate to a predetermined level;
and
as a result of determining that the determined rate meets or exceeds a predetermined threshold, then joining (<NUM>), by the first gateway node, the first and second subnets via the first and second gateway nodes and causing, by the first gateway node, nodes in the first subnet to reduce the signal transmit rate to the predetermined level.