Abstract:
The present invention, in illustrative embodiments, includes methods and devices for operation of a MANET system. In an illustrative embodiment, a method includes steps of analyzing and predicting performance of a MANET node by the use of a multiple model estimation technique. Another illustrative embodiment optimizes operation of a MANET node by the use of a model developed using a multiple model estimation technique. An illustrative device makes use of a multiple model estimation technique to estimate its own performance. In a further embodiment, the illustrative device may optimize its own performance by the use of a model developed using a multiple model estimation technique.

Description:
FIELD  
       [0001]     The present invention is related to the field of wireless communication. More specifically, the present invention relates to modeling operations within an ad-hoc network.  
       BACKGROUND  
       [0002]     Mobile ad-hoc networks (MANET) are intended to operate in highly dynamic environments whose characteristics are hard to predict a priori. Typically, the nodes in the network are configured by a human expert and remain static throughout a mission. This limits the ability of the network and its individual devices to respond to changing physical and network environments. Providing a model of operation can be one step towards building not only improved static solutions/configurations, but also toward finding viable dynamic solutions or configurations.  
       SUMMARY  
       [0003]     The present invention, in illustrative embodiments, includes methods and devices for operation of a MANET system. In an illustrative embodiment, a method includes steps of analyzing and predicting performance of a MANET node by the use of a multiple model estimation technique, which is further explained below. Another illustrative embodiment optimizes operation of a MANET node by the use of a model developed using a multiple model estimation technique. An illustrative device makes use of a multiple model estimation technique to estimate its own performance. In a further embodiment, the illustrative device may optimize its own performance by the use of a model developed using a multiple model estimation technique. 
     
    
     BRIEF DESCRIPTION OF THE FIGURES  
       [0004]      FIG. 1A  is an illustration of a mobile ad-hoc network;  
         [0005]      FIG. 1B  illustrates, in block form, a node for the network of  FIG. 1A ;  
         [0006]      FIG. 2A  is a block diagram for building a model by the use of a learning method;  
         [0007]      FIG. 2B  illustrates, in a simplified form, throughput as a function of inputs for a wireless communication device;  
         [0008]      FIG. 3  illustrates a mapping of system observables onto performance results;  
         [0009]      FIG. 4A  shows an attempt at regression on a data set;  
         [0010]      FIG. 4B  shows multiple model regression for the data set of  FIG. 4A ;  
         [0011]      FIG. 4C  shows multiple model regression for another data set;  
         [0012]      FIG. 4D  shows a complex single model regression;  
         [0013]      FIG. 5  illustrates a weighted multiple model regression;  
         [0014]      FIG. 6  shows a complex weighted, multiple model regression;  
         [0015]      FIGS. 7A-7B  illustrate observation of a new data point and updating of a multiple model regression in light of a plurality of data points;  
         [0016]      FIG. 8  shows in block form an illustrative method;  
         [0017]      FIGS. 9A-9B  show in block form another illustrative method;  
         [0018]      FIG. 10  shows in block form yet another illustrative method; and  
         [0019]      FIG. 11  shows another illustrative embodiment in which a first device indicates an operating parameter to second device.  
     
    
     DETAILED DESCRIPTION  
       [0020]     The following detailed description should be read with reference to the drawings. The drawings, which are not necessarily to scale, depict illustrative embodiments, and are not intended to limit the scope of the invention.  
         [0021]      FIG. 1A  is an illustration of a MANET system. The network is shown having a number of nodes N, X, Y. In a MANET system, a message sent by X may reach Y by “hopping” through other nodes N. This data transmission form is used at least in part because device X has a limited transmission range, and intermediate nodes are needed to reach the destination. The network may include one or more mobile devices, for example, device X is shown moving from a first location  10  to a second location  12 . As device X moves, it is no longer closest to the nodes that were part of the initial path  14  from X to Y. As a result, the MANET system directs a message from X to Y along a different path  16 .  
         [0022]     A gateway or base node may be provided for the MANET system as well. For example, a MANET system may comprise a number of mobile robots used to enter a battlefield and provide a sensor network within the field. The mobile robots would be represented by nodes such as node X, which send data back to a base node, such as node Y, via other mobile robots. While different nodes may have different functionality from one another, it is expected that in some applications, several nodes will operate as routers and as end hosts.  
         [0023]     Narrowing the view from the network to the individual device, a single node is shown in  FIG. 1B . The individual node  18  may include, physically, the elements shown, including, a controller, memory, a power supply (often, but not necessarily, a battery), some sort of mobility apparatus, and communications components. Other components may be shown, and not all of these components are required. Using the open-systems-interconnection networking model, there are parameters within each of seven layers that can be used by the node to monitor and/or modify its operation. The plethora of available parameters may include such items as transmission power level, packet size, etc.  
         [0024]     For each node, it is possible to capture a great variety of statistics related to node and network operation. Some node statistics may include velocity, packet size, total route requests sent, total route replies sent, total route errors sent, route discovery time, traffic received and sent (possibly in bits/unit time), and delay. Additional statistics may relate to the communications/radio, such as bit errors per packet, utilization, throughput (likely in bits/unit time), packet loss ratio, busy time, and collision status. Local area network statistics may also be kept, for example, including control traffic received and/or sent (both in bits/unit time), dropped data packets, retransmission attempts, etc. These statistics and parameters are merely examples, and are not meant to be limiting. Relative data may be observed as well, for example, a given node may generate a received signal strength indicator (RSSI) for each node with which it is in communication range, and may also receive data from other nodes regarding its RSSI as recorded by those nodes.  
         [0025]     For a given node, there are a number of observable factors, which may include past parameters such as power level and packet size that can be controlled by changing a setting of the node. The statistics kept at the node are also considered observables. Anything that can be observed by the node is considered to be an observable. Observables may include parameters that control operation of the network, result from operation of the network, or result from operations within a node, including the above noted statistics and control variables.  
         [0026]     Because there are so many observables, it is unlikely that every observable can be monitored simultaneously in a manner that allows improved control. The number of observables that can be monitored is also limited by the likelihood that some MANET devices will be energy constrained devices having limited power output (such as solar powered devices) or limited power capacity (such as battery powered devices). Rather than trying to capture and monitor all observables, one goal of modeling the system from the nodal perspective is to provide an estimate of operation given a reduced set of observables. Such a model may facilitate control decisions that change controllable parameters to improve operation.  
         [0027]     It should be understood that “improving” operation may have many meanings, but most likely will mean causing a change to at least one measurable statistic or observable that will achieve, or take a step toward achieving, a desired level of operation. For example, steps that increase data throughput may be considered as improving operation.  
         [0028]      FIG. 2A  is a block diagram for building a model by the use of a learning method. A learning system may include a learning step, shown at  20 . A number of training data  22  are used to perform simulations  24 . Various statistical analyses may be performed to generate a model by the use of the training data  22 , via simulation. Once built, the model  26  is then tested using test data  28 . If the model  26  predicts outcomes from the test data  28  that match those associated with the test data  28 , then the model  26  is verified. A match may occur when the model models the data with an amount of error. Rather than simulation, some embodiments instead make use of data collected from a “real” or operating environment of a network, which may be a MANET network.  
         [0029]     The illustrative embodiments shown herein are, for illustrative purposes, greatly simplified. Those of skill in the art will understand that extrapolation to a particular number of observables and/or controllables will be a matter of design expertise. For example, it is expected that a well-reduced model for control operation, as measured by node throughput, may show throughput as being a function of more than three or four variables. For example, as shown in  FIG. 2B , variables  35 A,  35 B, out to variable  35 N, may each be relevant to the operation of a device X  37 , yielding an output  39 .  
         [0030]      FIG. 3  illustrates a mapping of system observables onto performance results. One aspect of performance for MANET devices is that the environment is quite dynamic, and various aspects of operation can be difficult to predict. Thus, a mapping from the N-dimensional observables onto any given performance metric (single or multi-dimensional) is unlikely to be a one-to-one mapping. Moreover, there may be too many observables to allow each possible observable to be monitored, such that the N-dimensional set of observables may include an M-dimensional set of monitored observables, and a K-dimensioned set of non-monitored observables. As such, it is also possible that the mapping from the M-dimensioned set of monitored observables to a performance metric will not define a function, because a given observable data point, O M , may map to several performance data points, P A , P B  . . . , due to the influence of non-observed factors. Since there are unknown and/or unmonitored observables present in the system, direct mapping may be difficult, though it is not necessarily impossible.  
         [0031]     Performance may be measured by a number of parameters. For simplicity, performance may be considered herein as a single-dimension result. For example, performance may be a single-node measurement such as data throughput. Alternatively, performance may be a network based measure, for example, a sum of latencies across a network, an average latency, or maximum latency. Indeed, with latency, depending upon the aims of a particular system, there are several formulations for network-wide performance characteristics. Multi-dimensional performance metrics can also be considered, for example, a two-dimensional performance metric may include average node latency and average route length measured in the average number of hops. The present invention is less concerned with the actual performance metric that is to be optimized, and focuses instead on how a performance metric may be modeled as a result of a plurality of inputs.  
         [0032]      FIG. 4A  shows an attempt at regression on a data set. The data set is generally shown in an X-Y configuration, assuming that Y=f(X). A function is created and represented as line  40 , but does not correlate to the data particularly well and is rather complex. In contrast,  FIG. 4B  shows multiple model regression for the same data set of  FIG. 4A . In the multiple model regression, two functions result, shown as straight lines  42 ,  44 . The two lines  42 ,  44  correlate better to the data and are also relatively simple results. The available data may be partitioned among the models. As shown by the Xs in  FIG. 4B , some data may correspond to the model represented by line  42 , and other data, shown by the triangles, may correspond to the model represented by line  44 . It is not necessary that all data be modeled, for example, as shown by the circles, some data is identified as outlier data.  
         [0033]     A multiple model regression, in an illustrative example, is achieved by a multi-step process. First, known dimension reducing methods are applied to reduce the number of variables under consideration. Next, a multiple model estimation procedure is undertaken.  
         [0034]     In the multiple model estimation procedure, a major model is estimated and applied to the available data. Various modeling techniques (e.g. linear regression, neural networks, support vector machines, etc.) are applied until a model that, relative to the others attempted, describes the largest proportion of the available data, is identified. This is considered the dominant model. Next, the available data is partitioned into two subsets, a first subset being described by the dominant model, and a second subset which is not described by the dominant model. The first subset is then removed from the available data to allow subsequent iterations. The steps of estimating and identifying a dominant model, and partitioning the data, are repeated in iterations until a threshold percentage of the available data is described. For example, iterations may be performed until 95% of the available data has been partitioned and less than 5% of the available data remains.  
         [0035]     The use of multiple model regression allows functions to result as shown in  FIGS. 4C and 4D .  FIG. 4C  illustrates a data set in which a first regression  46  and a second regression  48  result. A single function describing both  46  and  48  would poorly correlate to the pattern which, at least in the two dimensions shown, shows two almost orthogonal functions.  FIG. 4D  illustrates another manner of partitioning, this time with multiple, simple segments  50 A- 50 F. The multiple models and/or segments allow better characterization of the available data by the resulting complex model.  
         [0036]     The multiple model regression begins with the assumption that a response value is generated from inputs according to several models. In short: 
 
 y=t   m ( x )+δ m   , x∈X   m  
 
         [0037]     Where δ m  is a random error or noise having zero mean, and unknown models are represented as target functions t m (x), m=1 . . . M. The assumption is that the number of models is small, but generally unkown. Generalizing to a greater number of dimensions, the functions may also be given as: 
 
 y=t   m ( w   m   , x )+δ m   , x∈X   m  
 
         [0038]     In this case, the w m  represents the input of a plurality of other parameters. It should be noted that w m  may represent any and/or all past values of any selected observable value(s). In some instances, w m  includes one or more previous values for x and y. The use of the x variable in these equations is provided as indicating that, in a given instance, x is the variable that may be adjusted (such as power, packet length, etc.) to predictably cause a change in the parameter, y, that is modeled.  
         [0039]     Additional details of the multiple model regression are explained by Cherkassky et al., MULTIPLE MODEL REGRESSION ESTIMATION, IEEE Transactions on Neural Networks, Vol. 16, No. 4, July 2005, which is incorporated herein by reference. The references cited by Cherkassky et al. provide additional explanation, and are also incorporated herein by reference.  
         [0040]     Some illustrative embodiments go farther than just finding the model, and move into making control decisions based upon predicted performance from the model. In an illustrative example, given the identified multiple models, a first manner of addressing a control problem is to construct a predictive outcome model. For example, given a state of a MANET device, as described by the observables, the method seeks to improve the performance outcome, y, by modifying x, a controllable parameter. An illustrative method uses a weighted multiple model regression approach. This provides an output from parameters as follows: 
 
 y=c   1   f   1 ( w   1   , x )+ . . . + c   m   f   m ( w   m   , x ) 
 
         [0041]     Where the {c 1 , . . . c m } are the proportions of data, from the training samples or training data, that are described by each of the models f i (w i , x). For example, if there are 100 training samples, and three functions f 1 , f 2 , f 3  describe 97/100, the above methodology would stop after identifying the three functions f 1 , f 2 , f 3 , since less than 5% of the samples would remain. If 52 of those 97 are described by f 1 , then c 1  would be 52/97=0.536; if 31 of those 97 are described by f 2 , then c 2  would be 31/97=0.320, and the remaining 14 of 97 are described by f 3 , then c 3  would be 14/97=0.144.  
         [0042]     By use of this approach, the variable x may be modified to improve function of an individual device or an overall system. A more generalized approach is as follows: 
 
 y=c   1   f   1 ( w   1   , x   1    . . . x   i )+ . . . + c   m   f   m ( w   m   , x   1    . . . x   i ) 
 
         [0043]     In this more general approach, the variables x 1  . . . x i  represent a plurality of controllable factors. The predicted outcome y may be a future outcome. Then, an illustrative method includes manipulation of the controllable factors x 1  . . . x i , in light of the observable factors w 1  . . . w m , to improve the predicted outcome, y.  
         [0044]      FIG. 5  illustrates a weighted multiple model regression. The example shows a first regression model  90 , which is treated as the dominant model and, as indicated, comprises 70% of available data samples. A second regression model  92  comprises the other 30% of available data samples. The predictive outcomes, then, are shown along line  94  which combines the predicted outcomes from each of model  90 ,  92  by using weights associated with each model. Line  94  is characterized by this formula: 
   y= 0.7( f   1 ( w   1   , x ))+0.3( f   2 ( w   2   , x ))  
         [0045]     In some embodiments, the functions f 1  . . . f m  are selected as simple linear regressions. This can be a beneficial approach insofar as it keeps the functions simple. For example, when performing predictive analysis at the node level, simpler analysis can mean a savings of power. However, the accuracy of the predictive methods may be further improved by adding simple calculations to the weighting factors.  
         [0046]      FIG. 6  shows a complex weight multiple model regression. The upper portion of  FIG. 6  shows a first function  100  and a second function  102 . First function  100  carries a greater weight, as there are more points associated with it than with second function  102 . It can be seen that the majority of points for first function  100  are to the right of the majority of points for second function  102 .  
         [0047]     The lower portion of  FIG. 6  illustrates the weight functions used in association with functions  100 ,  102 . Weight  104  is applied to first function  100 , while weight  106  is applied to second function  102 . There are generally three zones to the weight functions: zone  108 , in which the major factor of predictive analysis is second function  102 , zone  110  in which both functions  100 ,  102  are given relative weights, and zone  112  in which the major factor of predictive analysis is first function  100 . In this formulation, the resulting formula may take the form of: 
 
 y=c   1 ( x ) f   1 ( w   1   , x )+ . . . + c   m ( x ) f   m ( w   m   , x ) 
 
         [0048]     Generation of the weight formulas, c 1 (x) . . . c m (x) may be undertaken by any suitable method.  
         [0049]      FIGS. 7A-7B  illustrate observation of a new data point and updating of a multiple model regression in light of a plurality of data points. In the illustrative embodiment, the past data (which may be testing and/or training data) has been characterized by first function  110  and second function  112 . At this point, the method/device operates in a predictive mode, and has finished the initial learning and testing steps discussed with reference to  FIG. 2 . Data is captured by the device and a new data point  114  is shown in relation to the functions  110 ,  112 .  
         [0050]     In an illustrative example, when the new data point  114  is captured, it may then be associated with one of the available models. The step of associating new data with an existing model may include, for example, a determination of the nearest model to the new data. If the new data is not “close” to one of the existing models, it may be marked as aberrant, for example. “Close” may be determined, for example, by the use of a number of standard deviations.  
         [0051]     If it is determined that the new data  114  should be associated with one of the existing models, several steps may follow. In some embodiments, the association of new data  114  with one of the multiple models may be used to inform a predictive step. For example, rather than considering each of several models in making a prediction of future performance, only the model associated with the new data  114  may be used.  
         [0052]      FIG. 7B  illustrates two additional steps that may follow a determination that new data  114  is associated with one or the other of the available models  110 ,  112 . As shown in  FIG. 7B , first model  110  has an initial weight C 1 , and second model  112  has an initial weight C 2 . When new data is captured and associated with one or the other of the models  110 ,  112 , new weights C 1 ′ and C 2 ′ may be calculated. In an illustrative example, the weights may be adaptive over time. Adaptive calculation of the weights C 1 , C 2 , C 1 ′, C 2 ′ may include a first-in, first-out calculation where only the last N samples are used to provide weights.  
         [0053]     Another adaptive step may include the changing of the second function  112 . As shown, several new data points  114  are captured and lie along a line that is close to, but are consistently different from the second function  112 . Given the new data points  114 , the second function  112  may be modified to reflect the new data, yielding a new second function  116 .  
         [0054]      FIG. 8  shows in block form an illustrative method. As shown in  FIG. 8 , a first step is to establish the model, which may be a multiple model regression, as shown at  140 . Next, the method identifies observable values, as shown at  142 , either for an individual node or across several devices that make up a system. Using the model and the observables, one or more controllable factors are set, as shown at  144 . The step of setting a controllable factor may include changing the controllable factor or leaving the controllable factor at the same state or variable as it was previously. The method then includes allowing operations to occur, as shown at  146 . The method then iterates back to identifying observable values at  142 .  
         [0055]      FIGS. 9A and 9B  show, in block form, another illustrative method. Referring to  FIG. 9A , in this example, the model is established at  160 . Observables are identified, as shown at  162 , controllables are set as shown at  164 , and the method allows operations to occur, as shown at  166 . To this point, the method is not unlike that of  FIG. 8 . Next, however, the model may be updated, as shown at  168 , prior to returning to step  162 .  
         [0056]      FIG. 9B  highlights several ways in which the model can be updated. From block  180 , there are two general manners of performing an update. A portion of the model may be updated, as indicated at  182 . This may include adjusting the model weights, as shown at  184 . Updating a portion  182  may also include modifying the function values, as shown at  186 . In some embodiments, rather than updating a portion of the model  182 , the method may instead seek to reestablish the set of models, as shown at  188 . Reestablishment  188  may occur periodically or occasionally, depending upon system needs. The step of reestablishing the model  188  may be performed by invoking a learning routine, and/or by the use of training, test, and/or operating data.  
         [0057]     In some embodiments, a determination may be made regarding whether to update the model. For example, data analysis may be performed on at least selected observable data to determine whether one of the identified multiple models is being followed over time. If it is found that there is consistent, non-zero-mean error, then one or more of the models may need refinement. If, instead, there are consistent observable data that do not correspond to any of the identified models, a reestablishment of the model may be in order.  
         [0058]      FIG. 10  shows in block form yet another illustrative method. In this method, an established multiple model estimation is presumed. The method begins by capturing observables, as shown at  200 . Next, from the observables, the appropriate model is identified, as shown at  202 , from among those which have been selected for the established multiple model estimation. Using this appropriate model, performance factors may be identified, as shown at  204 . The performance factors may be controllable variables that affect the performance outcome. Next, as shown at  206 , optimization is performed to improve performance. The optimization may include modifying a controllable variable (hence, a controllable aspect of the device or system) in a manner that, according to the model, is predicted to improve system performance.  
         [0059]     After optimization, the method may either continue to update the model as shown at  208 , either on an ongoing basis or as necessitated by incoming data that suggest modification is needed. Otherwise, if no updating is performed, or after updating, the method continues to iterate itself, as shown at  210 . The iteration may occur on an ongoing basis, for example, where iteration occurs as soon as computation is complete. In some embodiments, rather than the ongoing basis, iteration  210  may include setting a timer and waiting for a predetermined time period to perform the next operation. For example, in a given node, it may be desirable to avoid instability that the optimization only occurs periodically, for example, every 30 seconds. Alternatively, optimization may occur occasionally, as, for example, when a message is received that indicates optimization should occur, or when a timer or counter indicates optimization should occur. For example, if a counter indicating data transmission errors passes a threshold level within a certain period of time, optimization may be in order.  
         [0060]     As can be seen from the above, there are many different types and levels of analysis that may be performed. In some illustrative MANET embodiments, different nodes are differently equipped for analysis. In particular, some nodes may be equipped only to receive instructions regarding operation, while other nodes may be equipped to perform at least some levels of analysis, such as updating portions of a model and determining whether the multiple model solutions that are initially identified are functioning. Yet additional nodes may be equipped to perform analysis related to establishing a model. Such nodes may be differently equipped insofar as certain nodes may include additional or different programming and/or hardware relative to other nodes.  
         [0061]      FIG. 11  shows another illustrative embodiment in which a first device indicates an operating parameter to second device. In the illustrative embodiment, the first device D 1  analyzes its own operation and determines that, given its operating environment/conditions, a change in operation by a second device D 2  may provide for improvement. An example may be if device D 1  is experiencing received transmission errors on a consistent basis. One solution may be for device D 2  to reduce its data transmission length to accommodate the problems experienced by D 1 . While the data manipulations at D 1  that would correspond to this circumstance may not provide such a qualitative description, the result is the same. Specifically, D 1 , having identified a potential manner of improving system and device operation, communicates a suggested operating parameter to D 2 . If the suggested operating parameter can be efficiently incorporated by D 2 , D 2  will do so. For example, D 2  may incorporate the operating parameter into only the communications it addresses to D 1 , or into all communications. If desired, D 1  may further address the improvements to a particular node other than D 2 , and D 2  may in turn pass on the message.  
         [0062]     While the above discussion primarily focuses on the use of the present invention in MANET embodiments, the methods discussed herein may also be used in association with other wireless networks and other communication networks in general.  
         [0063]     Those skilled in the art will recognize that the present invention may be manifested in a variety of forms other than the specific embodiments described and contemplated herein. Accordingly, departures in form and detail may be made without departing from the scope and spirit of the present invention as described in the appended claims.