Network graph representation of physically connected network

• US 9,473,368 B1
• Filed: 01/28/2016
• Issued: 10/18/2016
• Est. Priority Date: 01/28/2016
• Status: Active Grant

• Current Assignee: Utopus Insights, Inc. (Vestas Wind Systems A/S)
• Original Assignee: International Business Machines Corporation
• Inventors: Chaudhary, Harsh, Raman, Abhishek, Kim, Younghun, Kumar, Tarun, Zhang, Rui
• Primary Examiner(s): Whipple, Brian P
• Application Number:
  US15/009,291
• Time in Patent Office: 264 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/12 Network monitoring probes

Abstract

A method and system to generate a network graph representation of a physically connected network include selecting a selected sensor among a plurality of sensors arranged along the physically connected network, searching a time-varying data signal from the selected sensor for measurement patterns; identifying candidate sensors among the plurality of sensors that are candidates for being directly connected with the selected sensor based on each of the candidate sensors outputting a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal, and constructing possible graph sub-structures including the selected sensor and the candidate sensors. Determining a feasible graph sub-structure is based on the possible graph sub-structure and spatial placement of each of the selected sensor and the candidate sensors, and generating the network graph representation is by iteratively determining the feasible graph sub-structure by selecting a different sensor as the selected sensor.

Claims

1. A computer-implemented method of generating a network graph representation of a physically connected network, the method comprising:

selecting a selected sensor among a plurality of sensors arranged along the physically connected network;

searching, using a processor, a time-varying data signal from the selected sensor for measurement patterns;

identifying, using the processor, candidate sensors among the plurality of sensors that are candidates for being directly connected with the selected sensor based on each of the candidate sensors outputting a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal of the selected sensor;

constructing possible graph sub-structures including the selected sensor and the candidate sensors;

determining a feasible graph sub-structure based on the possible graph sub-structure and spatial placement of each of the selected sensor and the candidate sensors; and

generating the network graph representation based on iteratively determining the feasible graph sub-structure based on selecting a different one of the plurality of sensors as the selected sensor.

2. The computer-implemented method according to claim 1, wherein the searching the time-varying data signal from the selected sensor for the measurement patterns includes using spectral analysis, histogram analysis, fast Fourier transform (FFT), or wavelet transformation on the time-varying data signal.

3. The computer-implemented method according to claim 1, wherein the identifying the candidate sensors includes identifying nearby sensors among the plurality of sensors to the selected sensor, the nearby sensors being identified based on a distance between each nearby sensor and the selected sensor according to geoposition information for the plurality of sensors.

4. The computer-implemented method according to claim 3, wherein the identifying the candidate sensors includes identifying which of the nearby sensors includes a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal of the selected sensor and a time lag between the candidate time-varying data signal and the time-varying data signal of the selected sensor below a threshold time lag.

5. The computer-implemented method according to claim 4, wherein the identifying the candidate sensors includes determining a correlation coefficient based on each candidate time-varying data signal and the time-varying data signal of the selected sensor.

6. The computer-implemented method according to claim 5, wherein the correlation coefficient is computed as:

7. The computer-implemented method according to claim 1, wherein the determining the feasible graph sub-structure includes determining interconnections between the selected sensor and each of the candidate sensors.

8. The computer-implemented method according to claim 1, wherein the generating the network graph representation includes generating a graphical representation of a natural gas pipeline in which the plurality of sensors measure pressure.

9. A system to generate a network graph representation of a physically connected network, the system comprising:

a memory device configured to store geopositions of a plurality of sensors arranged along the physically connected network; and

a processor configured to select a selected sensor among the plurality of sensors, search a time-varying data signal from the selected sensor for measurement patterns, identify candidate sensors among the plurality of sensors that are candidates for being directly connected with the selected sensor based on each of the candidate sensors outputting a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal of the selected sensor, construct possible graph sub-structures that include the selected sensor and the candidate sensors, determine a feasible graph sub-structure based on the possible graph sub-structure and spatial placement of each of the selected sensor and the candidate sensors, and generate the network graph representation based on iteratively determining the feasible graph sub-structure by selecting a different one of the plurality of sensors as the selected sensor.

10. The system according to claim 9, wherein the processor is configured to search the time-varying data signal from the selected sensor for measurement patterns by using spectral analysis, histogram analysis, fast Fourier transform (FFT), or wavelet transformation on the time-varying data signal.

11. The system according to claim 9, wherein the processor is configured to identify the candidate sensors based on identifying nearby sensors among the plurality of sensors to the selected sensor, the nearby sensors being identified based on a distance between each nearby sensor and the selected sensor according to geoposition information for the plurality of sensors, and identifying which of the nearby sensors includes a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal of the selected sensor and a time lag between the candidate time-varying data signal and the time-varying data signal of the selected sensor below a threshold time lag.

12. The system according to claim 11, wherein the processor is configured to identify the candidate sensors based additionally on determining a correlation coefficient based on each candidate time-varying data signal and the time-varying data signal of the selected sensor, the correlation coefficient being computed as:

13. The system according to claim 9, wherein the processor is configured to determine the feasible graph sub-structure based on determining interconnections between the selected sensor and each of the candidate sensors.

14. The system according to claim 9, wherein the network graph representation is of a natural gas pipeline, and the plurality of sensors are configured to measure pressure.

15. A computer program product for generating a network graph representation of a physically connected network, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to perform a method comprising:

selecting a selected sensor among a plurality of sensors arranged along the physically connected network;

searching a time-varying data signal from the selected sensor for measurement patterns;

identifying candidate sensors among the plurality of sensors that are candidates for being directly connected with the selected sensor based on each of the candidate sensors outputting a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal of the selected sensor;

constructing possible graph sub-structures including the selected sensor and the candidate sensors;

determining a feasible graph sub-structure based on the possible graph sub-structure and spatial placement of each of the selected sensor and the candidate sensors; and

generating the network graph representation based on iteratively determining the feasible graph sub-structure based on selecting a different one of the plurality of sensors as the selected sensor.

16. The computer program product according to claim 15, wherein the searching the time-varying data signal from the selected sensor for the measurement patterns includes using spectral analysis, histogram analysis, fast Fourier transform (FFT), or wavelet transformation on the time-varying data signal.

17. The computer program product according to claim 15, wherein the identifying the candidate sensors includes identifying nearby sensors among the plurality of sensors to the selected sensor, the nearby sensors being identified based on a distance between each nearby sensor and the selected sensor according to geoposition information for the plurality of sensors, and identifying which of the nearby sensors includes a respective candidate time-varying data signal with candidate patterns that match the measurement patterns of the time-varying data signal of the selected sensor and a time lag between the candidate time-varying data signal and the time-varying data signal of the selected sensor below a threshold time lag.

18. The computer program product according to claim 17, wherein the identifying the candidate sensors includes determining a correlation coefficient based on each candidate time-varying data signal and the time-varying data signal of the selected sensor, the correlation coefficient being computed as:

19. The computer program product according to claim 15, wherein the determining the feasible graph sub-structure includes determining interconnections between the selected sensor and each of the candidate sensors.

20. The computer program product according to claim 15, wherein the generating the network graph representation includes generating a graphical representation of a natural gas pipeline in which the plurality of sensors measure pressure.