Methods of networking interrogation devices for structural conditions

• US 20060287842A1
• Filed: 08/23/2006
• Published: 12/21/2006
• Est. Priority Date: 09/22/2003
• Status: Active Grant

• Current Assignee: Advanced Structure Monitoring, Inc.
• Original Assignee: Advanced Structure Monitoring, Inc.
• Inventors: Kim, Hyeung-Yun
• Granted Patent: US 7,668,665 B2
• Time in Patent Office: Days
• US Class Current: 702/183
• CPC Class Codes: G01H 11/00 Measuring mechanical vibrations or ultrasonic, sonic or infrasonic waves by detecting changes in electric or magnetic properties
• CPC Class Codes: G01H 11/08 using piezoelectric devices
• CPC Class Codes: G01H 9/004 using fibre optic sensors light guides per se G02B6/00, acousto-optical devices specially adapted for gating or modulating in optical wave guides G02F1/125
• CPC Class Codes: G01M 5/0033 by determining damage, crack or wear
• CPC Class Codes: G01M 5/0066 by exciting or detecting vibration or acceleration vibration testing of structures G01M7/00
• CPC Class Codes: G01M 5/0091 by using electromagnetic excitation or detection
• CPC Class Codes: G01N 2291/011 Velocity or travel time
• CPC Class Codes: G01N 2291/015 Attenuation, scattering
• CPC Class Codes: G01N 2291/02491 Materials with nonlinear acoustic properties
• CPC Class Codes: G01N 2291/0258 Structural degradation, e.g. fatigue of composites, ageing of oils
• CPC Class Codes: G01N 2291/0422 Shear waves, transverse waves, horizontally polarised waves
• CPC Class Codes: G01N 2291/0423 Surface waves, e.g. Rayleigh waves, Love waves
• CPC Class Codes: G01N 2291/0427 Flexural waves, plate waves, e.g. Lamb waves, tuning fork, cantilever
• CPC Class Codes: G01N 2291/106 one or more transducer arrays
• CPC Class Codes: G01N 29/043 in the interior, e.g. by shear waves
• CPC Class Codes: G01N 29/0609 Display arrangements, e.g. colour displays indicating or recording in connection with measuring in general G01D
• CPC Class Codes: G01N 29/0672 by acoustic tomography medical tomography A61B8/13
• CPC Class Codes: G01N 29/07 by measuring propagation velocity or propagation time of acoustic waves
• CPC Class Codes: G01N 29/223 Supports, positioning or alignment in fixed situation mounting transducers per se G10K11/004
• CPC Class Codes: G01N 29/245 Ceramic probes, e.g. lead zirconate titanate [PZT] probes
• CPC Class Codes: G01N 29/2475 : Embedded probes, i.e. probes incorporated in objects to be inspected
• CPC Class Codes: G01N 29/2493 : Wheel shaped probes
• CPC Class Codes: G01N 29/28 : providing acoustic coupling , e.g. water impedance matching G10K11/02
• CPC Class Codes: G01N 29/4418 : with a model, e.g. best-fit, regression analysis
• CPC Class Codes: G01N 29/4463 : Signal correction, e.g. distance amplitude correction [DAC], distance gain size [DGS], noise filtering

Abstract

Methods of operating an interrogation system that has a plurality of patches attached to a host structure. Each patch is capable of generating a diagnostic wave and/or developing a sensor signal in response to the diagnostic wave. In each method, a Euclidean undirected graph is generated by forming a plurality of paths, wherein each path connects two of the patches and the length of the path is shorter than a preset limit. Then, a directed graph is generated by assigning a propagation direction of the diagnostic wave to each path. Structural condition index (SCI) values are measured by use of the directed graph and, based on the SCI values, the host structure is scanned for anomalies. The directed graph is reconfigured to enhance accuracy in determining the shape and location of the anomalies.

Claims

1. A method of operating an interrogation system that includes a plurality of patches attached to an object, each said patch being capable of generating a diagnostic wave and/or developing a sensor signal in response to said diagnostic wave, said method comprising:

generating an undirected graph that includes a plurality of paths, each said path connecting two of said patches;

generating a directed graph based on the undirected graph;

reconfiguring the directed graph; and

scanning said object for an anomaly by use of the directed graph.

2. A method as recited in claim 1, wherein said anomaly is at least one of hole, crack, repair patch, local change in the temperature of said object, local change in the pressure applied to said object, and a body outside of said object.

3. A method as recited in claim 1, wherein said undirected graph is a Euclidean graph and the length of each said path being shorter than a preset value.

4. A method as recited in claim 3, wherein the step of generating an undirected graph includes:

generating a Voroni diagram for optimizing the distribution of said patches; and

generating a Delaunay diagram including Delaunay triangles.

5. A method as recited in claim 4, wherein at least one of a randomized incremental algorithm, a divide-and-conquer algorithm, a plane sweep algorithm, is used to generate said Voroni diagram.

6. A method as recited in claim 4, wherein at least one of a two-dimensional binary tree search algorithm, a near neighbor search algorithm, and a two-dimensional grid range search algorithm, is used to search, insert, or delete one or more of the diagnostic patches of said Voroni diagram.

7. A method as recited in claim 4, wherein a locally equiangular triangulation technique is used to generate said Delaunay diagram.

8. A method as recited in claim 4, wherein said Delaunay diagram includes a Euclidean minimum spanning tree (EMST) wherein one of Kruskal'"'"'s algorithm and priority-first-search of Prim'"'"'s algorithm is used to perform graph searching of said EMST

9. A method as recited in claim 4, wherein said object includes at least one obstacle that has obstacle vertices and said paths include line segments of said Delaunay triangles connecting said patches and obstacle vertices.

10. A method as recited in claim 4, wherein said object includes one or more obstacles, said paths include a visibility graph, and a Dijkstra algorithm is used to generate the visibility graph.

11. A method as recited in claim 4, wherein said object includes at least one obstacle that has obstacle vertices, said Delaunay diagram includes one or more passable channels formed between said obstacles, each said channel includes one or more of said patches, and only one of said patches is located within a circle that passes two of said obstacle vertices.

12. A method as recited in claim 4, wherein said object includes at least one obstacle and wherein at least one of said paths is generated by one of beam tracing and ray tracing techniques and represents a trajectory of a signal reflected on the boundary of said object.

13. A method as recited in claim 4, wherein said object includes at least one obstacle and wherein at least one of said paths is generated by the steps of:

dividing an area covered by said interrogation system into spatial subdivisions, each said spatial subdivision having a rectangular shape;

selecting a first one of said spatial subdivisions as an actuator subdivision and a second one of said spatial subdivisions as a sensor subdivision, said actuator subdivision including a patch capable of generating a diagnostic wave;

traversing said spatial subdivisions to determine a plurality of subdivision sequences, each said subdivision sequence including a set of contiguous spatial subdivisions and starting from said actuator subdivision to said sensor subdivision; and

selecting one of said subdivision sequences that has the maximum structural condition index value change due to said obstacle.

14. A method as recited in claim 4, wherein said object includes at least one obstacle and wherein at least one of said paths is generated by the steps of:

dividing a space covered by said interrogation system into spatial subdivisions, each said spatial subdivision having a cubical shape;

selecting a first one of said spatial subdivisions as an actuator subdivision and a second one of said spatial subdivisions as a sensor subdivision, said actuator subdivision including a patch capable of generating a diagnostic wave;

traversing said spatial subdivisions to determine a plurality of subdivision sequences, each said subdivision sequence including a set of contiguous spatial subdivisions and starting from said actuator subdivision to said sensor subdivision; and

selecting one of said subdivision sequences that has the maximum structural condition index value change due to said obstacle.

15. A method as recited in claim 4, wherein said object includes a plurality of obstacles and wherein at least one of said paths is generated by ray mirror method and represents a trajectory of a signal reflected on the boundaries of said obstacles.

16. A method as recited in claim 1, wherein said undirected graph is non-weighted, further comprising:

determining a shortest route for each pair of said patches in said undirected graph by use of a recursive depth-first-search (DFS) method.

17. A method as recited in claim 16, wherein said step of reconfiguring includes:

deleting said shortest route.

18. A method as recited in claim 1, wherein each of said paths is associated with a weight, said weight being one of the physical length of a path, a time-of-flight for a diagnostic wave to travel a path, and a change in a measured structural condition index (SCI) value of a path due to said anomaly.

19. A method as recited in claim 18, wherein said undirected graph is weighted, further comprising:

determining a shortest route for each pair of said patches in said undirected graph by use of a breadth-first-search (BFS) method.

20. A method as recited in claim 19, wherein said step of reconfiguring includes:

deleting said shortest route.

21. A method as recited in claim 18, wherein said undirected graph is weighted and said weight is the change in the measured SCI value, further comprising:

determining modified minimum spanning trees (MMSTs) for each said patch in said undirected graph, said MMSTs including a first tree that has a minimum total weight and a second tree that has a maximum total weight.

22. A method as recited in claim 21, wherein said MMSTs are generated by use of Boruvaka'"'"'s algorithm.

23. A method as recited in claim 21, wherein said undirected MMSTs are Euclidean MMSTs and the longest route in each MMST is an indicator of the area covered by said interrogation system and the sparsity of the said undirected graph.

24. A method as recited in claim 21, wherein said step of reconfiguring includes:

deleting a portion of said first MMST from said undirected graph; and

adding at least one path to said undirected graph.

25. A method as recited in claim 18, wherein said directed graph is weighted, further comprising:

determining modified shortest route trees (MSRTs) for each said patch in said directed graph, said MSRTs including a first tree that has a minimum total weight and a second tree that has a maximum total weight.

26. A method as recited in claim 25, wherein at least one of Dijkstra'"'"'s algorithm and Bellman-Ford'"'"'s algorithm is used to generate said MSRTs.

27. A method as recited in claim 25, wherein Floyd'"'"'s algorithm is used to search all maximum and minimum anomaly-detection routes in said directed graph and to generate all shortest interrogation routes.

28. A method as recited in claim 25, wherein said directed graph is weighted, further comprising:

for each pair of patches, determining a maximum anomaly-detection route and a minimum anomaly-detection route using one of a mincost-flow algorithm, an augmenting-route maxflow algorithm, and a network simplex algorithm.

29. A method as recited in claim 28, wherein said step of reconfiguring includes:

deleting a portion of said minimum anomaly-detection route; and

adding at least one path to said directed graph.

30. A method as recited in claim 18, wherein said step of reconfiguring includes:

adding one or more paths nearby selected ones of said paths, wherein the weights of said selected paths are larger than a preset value.

31. A method as recited in claim 1, further comprising:

generating a transitive closure of said undirected graph; and

checking reachability between said patches by use of said transitive closure.

32. A method as recited in claim 1, further comprising:

dividing said directed graph into strong components;

building a kernel of said directed graph based on said strong components;

computing a transitive closure of said kernel; and

checking whether or not the directed graph includes a cyclic route based on said transitive closure.

33. A method as recited in claim 1, further comprising:

scheduling a sequence of said paths by topologically sorting said directed graph.

34. A method as recited in claim 3, further comprising:

determining the diameter of said undirected graph.

35. A method as recited in claim 34, wherein said step of reconfiguring includes:

dividing said undirected graph if said diameter is larger than a preset limit.

36. A method as recited in claim 1, further comprising:

(a) discriminating said directed graph into several networks according to a set of weight levels;

(b) generating all-pairs shortest routes for each said network;

(c) repeating said steps (a) and (b) at a plurality of points in time; and

(d) detecting an evolution of said anomaly by comparing the all-pairs shortest routes of said discriminated networks with each other.

37. A method as recited in claim 36, wherein at least one of Bellman-Ford algorithm and Floyd'"'"'s algorithm is used to determine said all-pairs shortest routes.

38. A method as recited in claim 4, wherein said step of scanning said object for an anomaly by use of the directed graph includes:

generating influence circles or spheres associated with one of said Delaunay triangles; and

determining the location of said anomaly by use of said influence circles or spheres.

39. A method as recited in claim 38, wherein said step of determining the location is performed by an equation:

∥

x^damage−

x_j^sensor∥

=l_ij−

ct_ij^delay,

wherein l_ij is the distance between i^th and j^th patches, i^th patch is capable of generating said diagnostic wave, j^th patch is capable of developing said sensor signal, x_j^sensor is the coordinate of j^th patch, x^damage is the location of said anomaly, t_ij^delay is a delay in arrival time caused by said anomaly, and c is the propagation speed of said diagnostic wave.

40. A method as recited in claim 4, wherein said step of scanning said object for an anomaly by use of the directed graph includes:

generating influence circles or spheres associated with a plurality of said Delaunay triangles, said plurality of Delaunay triangles having a common patch for generating the diagnostic wave; and

determining the shape of said anomaly by use of said influence circles or spheres.

41. A method as recited in claim 18, wherein said weight is the change in the measured SCI value, further comprising:

compensating the SCI value associated with each said path.

42. A method as recited in claim 41, further comprising:

calculating a degree of said anomaly that is equal to a compensated SCI value change divided by a compensated SCI value.

43. A method as recited in claim 4, wherein said step of scanning said object for an anomaly by use of the directed graph includes:

generating a plurality of Euclidean shortest-route trees (ESRTs);

constructing and centralizing a tuple of echo-location triangles (ETs) of each said ESRT;

determining the shape and location of said anomaly by use of influence circles or spheres associated with said centralized tuple of ETs; and

combining information of said shape and location to construct a tomography image of said anomaly.

44. A method as recited in claim 43, wherein at least one of Dijkstra algorithm and first-priority-search (PFS) algorithm can be used to generate said ESRTs.

45. A method as recited in claim 43, wherein a parallel projection algorithm can be used to generate said tomography image.

46. A method as recited in claim 18, further including, prior to the step of scanning said object:

estimating statistical dependence between weights associated with said paths using one of a Bayesian network model and Markov random field model.

47. A method as recited in claim 46, wherein said Bayesian network model and Markov random model generate binary junction trees (BJTs), each said BJT including a plurality of nodes that are respectively associated with a plurality of wedges of said Delaunay triangles.

48. A method as recited in claim 18, further including, prior to the step of scanning said object:

estimating statistical dependence between weights associated with said paths by use of a binary junction tree (BJT), said BJT including a plurality of nodes that are respectively associated with a plurality of wedges of said Delaunay triangles,

wherein a local minimum-mean-square-error (MMSE) estimation algorithm is used to estimate said statistical dependence and a local message-passing algorithm is used for data association between said nodes of said BJT.

49. A method as recited in claim 18, wherein said interrogation system includes an interrogation management system and a plurality of diagnostic networks coupled to said interrogation management system and wherein each said network covers a portion of said object, is associated with a directed graph, and is operative to develop a structural condition rate (SCR) signal and to send said SCR signal to said interrogation management system at the end of every time slot for interrogating said network.

50. A method as recited in claim 49, wherein said SCR signal may include information that is the maximum deviation of SCI value associated with one specific path in one of said diagnostic networks or a change in the average of SCI values associated with all of paths in one of said diagnostic networks.

51. A method as recited in claim 50, wherein said time slot is determined by use of said SCR signal.

52. A method as recited in claim 50, wherein said specific path is coupled to a sentinel patch that wakes up other patches when said maximum deviation exceeds a preset threshold.

53. A method as recited in claim 1, further comprising:

selecting some of said patches as sentinel patches and causing the others to enter into a sleep mode;

causing said sentinel patches to periodically develop interrogation signals;

performing a statistical hypothesis test to determine a presence of said anomaly based on said interrogation signals; and

waking up a portion of said other patches located nearby said anomaly when the presence is confirmed.

54. A method as recited in claim 1, wherein said interrogation system is operative to communicate with a wireless communication system

55. A method as recited in claim 54, wherein said interrogation system communicates signals with the wireless communication system and wherein said signals are generated in one of wireless application protocol (WAP), simple object access protocol (SOAP), and XML-RPC and formatted by use of wireless markup language (WML) for Internet Web Services.

56. A method as recited in claim 54, wherein said interrogation system communicates signals with at least one of mobile and web-enabled devices for Internet Web Access.

57. A computer readable medium carrying one or more sequences of instructions for operating an interrogation system that includes a plurality of patches attached to an object, each said patch being capable of generating a diagnostic wave and/or developing a sensor signal in response to said diagnostic wave, wherein execution of one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

generating an undirected graph that includes a plurality of paths, each said path connecting two of said patches;

generating a directed graph based on the undirected graph;

reconfiguring the directed graph; and

scanning said object for an anomaly by use of the directed graph.