Palo Alto Research Center Inc.

Yi Shang

Markus P J Fromherz

Lara S Crawford

Ying Di Zhang

Sergei Vassilvitskii

Wheeler Ruml

A method is presented for a learning-based strategy utilized within message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, in which each node includes attributes. The method includes determining local attributes for each of the nodes and defining constraints on the attributes. Each node is provided access to the attributes of each neighboring node. Each message transmitted over the network has a message type, which includes a destination specification, route specification, and objective specification. Constraint checking and cost estimation checking are performed for each message type. Cost estimation is utilized to converge on an optimal message path. The message that is routed within the network includes the address of a sending node, the address of the source node, route constraints, destination constraints, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.

Learning-based strategies for message-initiated constraint-based routing

A method is presented for message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, in which each node includes attributes having attribute values. The method includes determining local attributes for each of the nodes in the ad-hoc network and defining constraints on the attributes. Each node is provided access to the attributes of each neighboring node, with a neighboring node being a node that is one hop away. Each message transmitted over the ad-hoc network has a message type, which includes a destination specification, route specification, and objective specification. Constraint checking and cost estimation checking are performed for each message type. The message that is routed within the network includes the address of a sending node, the address of the source node, route and destination constraints, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.

Protocol specification for message-initiated constraint-based routing

A method is presented for a time-aware strategy utilized within message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, in which each node includes attributes. The method includes determining local attributes for each of the nodes and defining constraints on the attributes. Each node is provided access to the attributes of each neighboring node, with a neighboring node being a node that is one hop away. Each message transmitted over the network has a message type, which includes a destination specification, route specification, and objective specification. Constraint checking and cost estimation checking are performed for each message type. The message that is routed within the network includes the address of a sending node, address of the source node, route constraints, destination constraints specified with a time bound, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.

Time-aware strategy for message-initiated constraint-based routing

Disclosed herein is a method for deriving node localization information within communication networks having a plurality of nodes, which are separated by node paths. The method includes estimating the shortest path between multiple pairs of nodes in the network and constructing a matrix encompassing the estimated shortest paths. Multidimensional scaling is then applied to the matrix and the largest eigenvectors of the transformed matrix are identified. From this is constructed a relative map of the location of the pairs of nodes within the network by utilization of the eigenvectors.

Node localization in communication networks

A cooperative solving method for controlling a plurality of constraint problem solvers identifies complexity criteria, which provide direction for selecting and for transitioning between constraint problem solvers. The method includes randomly selecting a test point and determining whether the test point satisfies a first complexity criterion. A first constraint problem solver is selected, and an alternate test point is identified by the first solver if the complexity criterion has not been satisfied. If the alternate test point is a problem solution, it is transmitted to the system. If the alternate test point is not a problem solution or if the original randomly-selected test point satisfies the complexity criterion, a second constraint solver selects a new test point. If the new test point is a problem solution, it is transmitted to the system; if the new test point is not a solution, the cooperative solver is restarted.

Complexity-directed cooperative problem solving

A method for feedback control of cooperative problem solving for real-time applications in complex systems utilizes solvers parameterized by control variables. The method includes initializing the time setting and selecting at least one solver parameter value. The solver is operated with the selected solver parameter value or values for a specified interim and the operational conditions are reviewed. A solution is transmitted to the system if a solution quality condition is satisfied. The solver continues to operate if the solution quality condition is not satisfied and the performance differential is not greater than a specified threshold. If the solution quality condition is unsatisfied, but the performance differential exceeds the threshold, at least one alternate solver parameter value is selected and the solver is operated with the new solver parameter value for a specified interim. The solver continues to operate until the solution quality condition is satisfied.

Growing community of inventors

Columbia, MO, United States of America

Yi Shang