(en)Apparatuses, methods, and systems for automatically commissioning lighting controls using sensing parameters of the light controls are disclosed. One embodiment includes a building control system. The building control system includes a plurality of sensors, a plurality of lights associated with the plurality of sensors, and a controller. The controller is operative to receive sense signals from the plurality of sensors, and generate a graph based on the sensed signals, wherein the graph includes nodes that represent light locations, and edges that represent distances between the lights. For an embodiment, the controller further operative to performing inexact graph matching between a floor plan graph and the sensor graph, thereby automatically commissioning the plurality of lights based on the sensed signals of the plurality of sensors.

1.ApplicationNumber: US-201414194684-A
1.PublishNumber: US-9807849-B2
2.Date Publish: 20171031
3.Inventor: BHATKAR ANUP
MOHAN TANUJ
ASHAR PREMAL

4.Inventor Harmonized: BHATKAR ANUP(IN)
MOHAN TANUJ(US)
ASHAR PREMAL(US)

5.Country: US
6.Claims:
(en)Apparatuses, methods, and systems for automatically commissioning lighting controls using sensing parameters of the light controls are disclosed. One embodiment includes a building control system. The building control system includes a plurality of sensors, a plurality of lights associated with the plurality of sensors, and a controller. The controller is operative to receive sense signals from the plurality of sensors, and generate a graph based on the sensed signals, wherein the graph includes nodes that represent light locations, and edges that represent distances between the lights. For an embodiment, the controller further operative to performing inexact graph matching between a floor plan graph and the sensor graph, thereby automatically commissioning the plurality of lights based on the sensed signals of the plurality of sensors.

7.Description:
(en)RELATED APPLICATIONS
This patent application is a continuation-in-part (CIP) of U.S. patent application Ser. No. 14/040,640, filed Sep. 28, 2013, which is a CIP of U.S. patent application Ser. No. 12/874,331, filed Sep. 2, 2010, which is a CIP of Ser. No. 12/584,444 filed Sep. 5, 2009.


FIELD OF THE EMBODIMENTS
The described embodiments relate generally to control systems. More particularly, the described embodiments relate to methods, apparatuses and systems for automatically commissioning lighting controls using sensing parameters of the lighting controls.
BACKGROUND
Sensors within a structure can be utilized for automatically control lighting, and conserver use of energy to power with lighting. The sensors include, for example, motion sensors and light sensors. However, automated lighting control systems can be difficult to design, and can include high costs of installation. The installation process typically includes a commissioning process which can be time consuming and expensive.
It is desirable to have a method, system and apparatus for automatically, simply and inexpensively performing commissioning of automatic lighting control systems.
SUMMARY
One embodiment includes a method of locating lights of a structure. The method includes sensing signals, by a plurality of sensor units wherein the plurality of sensor units are associated with a plurality of lights, and generating a graph based on the sensed signals, wherein the graph includes nodes that represent light locations, and edges that represent distances between the lights.
Another embodiment includes a building control system. The building control system includes a plurality of sensors, a plurality of lights associated with the plurality of sensors, and a controller. The controller is operative to receive sense signals from the plurality of sensors, and generate a graph based on the sensed signals, wherein the graph includes nodes that represent light locations, and edges that represent distances between the lights.
Other aspects and advantages of the described embodiments will become apparent from the following detailed description, taken in conjunction with the accompanying drawings, illustrating by way of example the principles of the described embodiments.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 shows an area that includes multiple fixtures that include sensors and/or lights, according to an embodiment.
FIG. 2 shows a lighting fixture of a lighting system, according to an embodiment.
FIG. 3 shows a lighting fixture of a lighting system, according to another embodiment.
FIG. 4 shows variation of measured intensity of light with respect to distance from the source of the light, according to an embodiment.
FIG. 5 shows variation of measured link quality indicator (LQI) with respect to distance from the source of an electromagnetic signal source, according to an embodiment.
FIG. 6 is a flow chart that includes steps of operation of a motion sensor, according to an embodiment.
FIG. 7 show samples of data generated by a plurality of motion sensor units, according to an embodiment.
FIG. 8 shows steps of a method of constructing a graph G S1 from data generated by a motion sensor unit, according to an embodiment.
FIG. 9 shows an example of data generated by a light intensity sensor unit, according to an embodiment.
FIG. 10 shows steps of a method of constructing a graph G S2 from data generated by a light intensity sensor unit, according to an embodiment.
FIG. 11 shows an example of data generated by an LQI sensor unit, according to an embodiment.
FIG. 12 shows steps of a method of constructing a graph G S3 from data generated by an LQI sensor unit, according to an embodiment.
FIG. 13 is a flow chart that include steps of a method of constructing a compiled graph G S from the graphs G S1 , G S2 G S3 , according to an embodiment.
FIG. 14 is a flow chart that includes steps of a method of constructing the compiled graph G S using a synthesis function, according to an embodiment.
FIG. 15 is a flow chart that includes steps of a method of constructing a floor plan graph G f , according to an embodiment.
FIG. 16 shows a floor plan graph according to an embodiment.
FIG. 17 shows a sensor graph according to an embodiment.
FIGS. 18, 19, 20 show steps of methods for analyzing and matching two un-weighted graphs with a maximum run time, and outputting a best match found between the two graphs and a score of the best match, according to at least some embodiments.
FIGS. 21, 22, 23 show steps of methods for finding a match between two one-degree neighboring graphs with a maximum run time, and outputting a score of the best match, according to at least some embodiments.
FIGS. 24, 25 show steps of methods for finding best matched vertices between two graphs in which best matching is already known, according to at least some embodiments.



DETAILED DESCRIPTION
As shown in the drawings, the described embodiments provide methods, apparatuses, and systems for automatically, simply and inexpensively performing commissioning of automatic lighting control systems. An embodiment includes commissioning of lighting controls onto a floor plan using sensing parameters of the lighting controls. For at least some embodiments, the commissioning includes generating a sensor graph that include information of relationships (such as, which sensors are neighbors, estimated distances between the sensors, and confidences of the estimates of the distances) between sensors (and/or fixtures) of an area that is obtained through sensing and/or control of the sensors and/or lighting fixtures associated with the sensors. Further, the commissioning includes matching the sensor graph with a floor plan graph, wherein the floor plan graph is generated based on a known floor plan of the area. For an embodiment, the matching provides an identification of where each of the sensors of the area is located. Further, for an embodiment, the matching further provides a quality of the matching that reflects a confidence level of the matching.
FIG. 1 shows an area 100 that includes multiple fixtures 101 - 120 , according to an embodiment. For an embodiment, each fixture 101 - 120 includes one or more sensors, a lighting controller, and a light. For other embodiments, each of the fixtures 101 - 120 includes at least one sensor. For at least some embodiments, the fixtures 101 - 120 are dispersed within a structure that includes the area 100 . As shown, the fixtures 101 - 120 can be deployed within cubicles, hallways and open spaces within the area 100 . Once deployed, the locations of the fixtures 101 - 120 within the building are recorded for future reference, and for building control utilizing the fixtures 101 - 120 . After deployed, a commissioning process is completed to determine the location of each of the fixtures 101 - 120 .
For an embodiment, the fixtures 101 - 120 are interfaced with a controller 130 . For an embodiment, each fixture 101 - 120 is directly connected to the controller 130 . For another embodiment, links exist between the fixtures, allowing a fixture to be connected to the controller 120 through one or more other fixtures. For example, the fixtures 101 - 120 can form a wireless mesh network, and links between fixtures and other devices can include links through other fixtures. For an embodiment, the controller 130 receives information from the fixtures, and controls an environmental condition (such as, lighting or heating) within the area 100 . During commissioning, for an embodiment, the controller 130 receives information that includes at least sensed signals of sensors of the fixtures 101 - 120 within the area. Based on the sensed signals, the controller 130 automatically performs a commissioning process in which a location (both absolute locations and locations relative to other fixtures) of each fixture is determined. Once determined, the location of each of the sensors and/or fixtures is stored in memory 140 for future reference.
While shown as a separate controller 130 , for at least embodiments, the processing of the controller 130 is distributed amongst the controller of each of the fixtures. For other embodiments, the processing of the controller 130 is self-contained within a remote controller 130 .
FIG. 2 shows a lighting fixture 200 of a lighting system, according to an embodiment. As shown, for this embodiment the lighting fixture 200 includes a motion detecting unit (motion sensor unit) 210 , a light intensity detection unit (light intensity sensor unit) 220 , an LQI unit (electromagnetic signals transmitter and receiver) 230 , a controller/interface 240 , and a light controller unit 250 .
The motion detecting unit 210 sensed motion proximate to the fixture 200 . The light intensity detection unit 220 senses the intensity of light proximate to the fixture 200 . It should be noted, that for at least some embodiments, at least one light associated with the fixture 200 emits light. The LQI unit both senses (receives) electromagnetic signals proximate to the fixture 200 , and for at least some embodiments, also emits (transmits) and electromagnetic signal.
The controller/interface 240 receives the sensed signals of the motion detecting unit 210 , the light intensity detection unit 220 , and the LQI unit 230 and provides the sensed signals to the central controller 130 . At least one of the controller/interface 240 and the central controller 130 provides control information to the light controller unit 250 for controlling one or more light associated with the fixture 200 .
For an embodiment, based on the sensed signal of one or more of the motion detecting unit 210 , the light intensity detection unit 220 , and the LQI unit 230 the central controller 130 generates graphs that include estimated locations of each of multiple fixtures including the fixture 200 . For an embodiment, the central controller 130 further places the fixtures on an existing floor plan, thereby generating a floor plan graph of the area in which the fixtures are located that includes the locations of all of the fixtures. While describes as controlling light, it is to be understood that for at least some embodiments, the fixture additionally or alternatively control another environmental parameter, such as, heat or cooling (HVAC).
FIG. 3 shows sensor and associated lighting control (fixture), according to an embodiment. A sensor and associated lighting control fixture 300 includes a smart sensor system 302 that is interfaced with a high-voltage manager 304 , which is interfaced with a luminaire 340 . The sensor and associated lighting control of FIG. 3 is one exemplary embodiment of the sensors utilized for occupancy detection. Many different sensor embodiments are adapted to utilization of the described embodiments for occupant sensing and motion. For at least some embodiments, sensors that are not directly associated with light control are utilized.
The high-voltage manager 304 includes a controller (manager CPU) 320 that is coupled to the luminaire 340 , and to a smart sensor CPU 335 of the smart sensor system 302 . As shown, the smart sensor CPU 345 is coupled to a communication interface 350 , wherein the communication interface 350 couples the controller to an external device. The smart sensor system 302 additionally includes a sensor 340 . As indicated, the sensor 340 can include one or more of a light sensor 341 , a motion sensor 342 , and temperature sensor 343 , and camera 344 and/or an air quality sensor 345 . It is to be understood that this is not an exhaustive list of sensors. That is additional or alternate sensors can be utilized for occupancy and motion detection of a structure that utilizes the lighting control fixture 300 . The sensor 340 is coupled to the smart sensor CPU 345 , and the sensor 340 generates a sensed input. For at least one embodiment, at least one of the sensors is utilized for communication with the user device.
For an embodiment, the temperature sensor 343 is utilized for occupancy detection. For an embodiment, the temperature sensor 343 is utilized to determine how much and/or how quickly the temperature in the room has increased since the start of, for example, a meeting of occupants. How much the temperate has increased and how quickly the temperature has increased can be correlated with the number of the occupants. All of this is dependent on the dimensions of the room and related to previous occupied periods. For at least some embodiment, estimates and/or knowledge of the number of occupants within a room are used to adjust the HVAC (heating, ventilation and air conditioning) of the room. For an embodiment, the temperature of the room is adjusted based on the estimated number of occupants in the room.
According to at least some embodiments, the controllers (manager CPU 320 and the smart sensor CPU) are operative to control a light output of the luminaire 340 based at least in part on the sensed input, and communicate at least one of state or sensed information to the external device.
For at least some embodiments, the high-voltage manager 304 receives the high-power voltage and generates power control for the luminaire 340 , and generates a low-voltage supply for the smart sensor system 302 . As suggested, the high-voltage manager 304 and the smart sensor system 302 interact to control a light output of the luminaire 340 based at least in part on the sensed input, and communicate at least one of state or sensed information to the external device. The high-voltage manager 304 and the smart sensor system 302 can also receive state or control information from the external device, which can influence the control of the light output of the luminaire 340 . While the manager CPU 320 of the high-voltage manager 304 and the smart sensor CPU 345 of the smart sensor system 302 are shown as separate controllers, it is to be understood that for at least some embodiments the two separate controllers (CPUs) 320 , 345 can be implemented as single controller or CPU.
For at least some embodiments, the communication interface 350 provides a wireless link to external devices (for example, the central controller, the user device and/or other lighting sub-systems or devices).
An embodiment of the high-voltage manager 304 of the lighting control fixture 300 further includes an energy meter (also referred to as a power monitoring unit), which receives the electrical power of the lighting control fixture 300 . The energy meter measures and monitors the power being dissipated by the lighting control fixture 300 . For at least some embodiments, the monitoring of the dissipated power provides for precise monitoring of the dissipated power. Therefore, if the manager CPU 320 receives a demand response (typically, a request from a power company that is received during periods of high power demands) from, for example, a power company, the manager CPU 320 can determine how well the lighting control fixture 300 is responding to the received demand response. Additionally, or alternatively, the manager CPU 320 can provide indications of how much energy (power) is being used, or saved.
FIG. 4 shows variation of measured intensity of light with respect to distance from the source of the light, according to an embodiment. The light intensity detection unit 220 generates a sensed signal that represents an intensity of received light. This sensed signal can be used for estimating a location of the sensor (and therefore, a fixture that includes the sensor). As stated, the curve shown in FIG. 4 provides a representation of the variation in received light intensity as a function of the distance the sensor receiving the light is from the source of the light. Utilizing this relationship, estimates of the distance between a light source and a sensor sensing the light source can be determined. For example, a light associated with a first fixture can be controllably activated. By knowing the level of intensity of light being emitted from the activated light, and the level of the intensity of light at the sensor of a second fixture, the distance between the activated light of the first fixture and the light sensor of the second fixture can be estimated. As will be described, for an embodiment, a light of a single fixture of an area is activated making it the only source of light in the area and the distances between the activated light of the single fixture and the other fixtures of the area can be estimated.
As shown, the intensity of light generated by a fixture (light fixture) diminishes with distance traveled by the light way from the Fixture Light. The light intensity at exemplary distances of 0 feet, 2 feet, 4 feet and 6 feet are depicted in FIG. 4 . Based on knowledge of the relationship between received light intensity and distance as shown by the exemplary curve of FIG. 4 , the distances between the light intensity sensor and the originating light can be estimated based on the sensed light intensity.
FIG. 5 shows variation of measured link quality indicator (LQI) with respect to distance from the source of an electromagnetic signal source, according to an embodiment. As described, the LQI unit 230 of the fixtures includes an electromagnetic signal transmitter and an electromagnetic signal receiver. Utilizing a curve similar to the curve shown in FIG. 5 , the distance between a first LQI unit of a first fixture and a second LQI unit of the second fixture can be estimated. That is, by transmitting an electromagnetic signal from the first fixture at a known power level, the distance between the first LQI sensor and the second LQI sensor can be estimated based on the power level of the sensed electromagnetic signal received by the second LQI.
As shown in the FIG. 5 , LQI decreases with square of distance. Based on this observation of LQI between two LQI sensors (fixtures), the relative distance between fixtures in the network of fixtures can be determined.
FIG. 6 is a flow chart that includes steps of operation of a motion sensor, according to an embodiment. Rather than estimating signal levels as the light intensity detection unit 220 and the LQI unit 230 do, the motion detecting units 210 of multiple fixtures can associate commonly located fixtures by correlating motion sensed by the commonly located fixtures. That is, when the timing of sensed motion of multiple fixtures is the same, it is assumed that the multiple fixtures are proximately located. The more times the sensed motion of motion detecting units 210 of the multiple fixtures are correlated in time, the higher the level of confidence that the multiple fixtures are located near each other.
As shown, a first step 610 includes sensing motion by a motion detecting unit 210 over an interval of time. That is, sensed motion is monitored and observed over a fixed interval of time.
Further, a second step 620 includes recording the presence or absence of motion during the interval of time. The recorded presence of motion during the interval of time for multiple motion detecting units can be used to determine common locations of the fixtures of the motion detecting units.
Once the motion observation process is started, it observes (senses motion) of the area associated with the fixtures, for a fixed interval of time, for example, 5 seconds and then record the presence or absence of motion. This recorded information is sent to central controller at fixed interval of, for example, 5 minutes, for processing. The process continues until stopped.
FIG. 7 show samples of data generated by a plurality of motion sensor units, according to an embodiment. The data shown in FIG. 7 is raw data generated by multiple motion sensor units of multiple fixtures. The table of data of FIG. 7 includes the motion sensor unit number (1-5), a time stamp of the senses motion, and the raw sensed motion data. As previously stated, commonly located sensors and fixtures can be identified by correlating the sensed motion of the multiple fixtures.
For an embodiment, the data of the motion detecting unit is sent to the central controller once every time period (for example, every 5 minutes) and sampled at a sampling interval (such as, every 5 seconds). As shown, the LCS_ID represents identification identifier of sensor (fixtures), TIMESTAMP represents time at which 5 minute window ends and MOTION_DETECTED represents the 60 binary motion bits with 1 representing motion detected and 0 representing motion not detected.
FIG. 8 shows steps of a method of constructing a graph G S1 from data generated by a motion sensor unit, according to an embodiment. A first step 810 includes a controller retrieving the sensing motion data from memory.
A second step 820 includes identifying, for a particular motion sensor of a fixture, other motion sensors of other fixtures that repeatedly detect motion at the same time the particular sensor does. The other fixtures are identified as immediate neighboring fixtures. A confidence level is determined based how closely the motion of the other fixtures is correlated to motion sensed by the particular motion sensor, and the number of repeating times the motion is correlated.
A third step 830 includes constructing a graph G S1 , wherein the vertices of the graph include a motion sensor of a fixture. Further, an edge value between the vertices if the vertices are immediate neighbors, and the edge value is based upon the confidence level.
Once the graph G S1 has been constructed, the graph G S1 can be written to memory (step 830 ).
The process of FIG. 8 provides an exemplary method of algorithmically processing the motion data. The key observation in analysis of motion data is that if two sensors are detecting motion at same instant of time (for example, at the sampling interval of 5 seconds) or in a next interval then the sensors are spatially close with high probability. It could happen that two sensors are distant but detect motion in same interval because 2 different people are walking below that sensor in the same instant of time. But the probability of latter case happening is much smaller as compared to that of former one. So observing data over period of time and for a given sensor, finding all other sensors such that, they detect motions at the same time, repeatedly, then such sensors are immediate neighbored, with certain confidence measure, where the confidence measure is a value between 0 and 1, and is directly proportional to number of times the two sensors detect motion at the same time.
FIG. 9 shows an example of data generated by a light intensity sensor unit, according to an embodiment. More specifically, FIG. 9 includes a table that indicates the fixture of the activated light (light source), the fixture that senses the light, and the value of the sensed light. Based on this table, neighboring fixtures can be identified.
The light intensity detection unit can be used to construct G S2 , a graph similar to Graph G s1 . Consider a setup wherein first all light from sources, such as, Sunlight and so on, other than Fixture Light present on the floor plan is blocked. Second, only one light fixture (source) is switches on, and all other sensors (Destinations) present on the floor plan detect light intensity using the light intensity detection unit. This process is then repeated for all sensors (fixtures) of the floor plan. FIG. 8 is an exemplary embodiment of data generated by this setup. LCS_ID_SRC represent the sensor which is acting like a source and LCS_ID_DEST are the destination sensors. The column LIGHT_INTENSITY_DETECTED column represents the light detected by LCS_ID_DEST. Referring to FIG. 4 , it can be deduced that for a given LCS_ID_SRC, all the LCS_ID_DEST detecting max light of intensity are immediate neighbored, with a measure of confidence. This is true even if the light intensity detection unit is directional. That is, the light intensity detected depends on the orientation of sensor.
FIG. 10 shows steps of a method of constructing a graph G S2 from data generated by a light intensity sensor unit, according to an embodiment. A first step 1010 includes a controller retrieving the sensing light intensity data from memory. For this embodiment, the light data is generated while controllably activating a single light associated with a fixture within an area. Other fixtures within the area receive the light, and sense an intensity of the received light. The retrieved sensed light intensity is processed to identify the fixture that includes the highest level of sensed light intensity. A second step 1020 includes identifying the fixture that includes the highest level of sensed light intensity, and identifying this fixture as an immediate neighboring fixture of the fixture that generated the light that is being sensed.
A process can be initiated wherein a different one of the fixtures activates its light, and the sensed light intensity at all of the other of the fixtures is monitored. Through an iterative process, neighboring fixtures can be identified. A third step 1030 includes constructing a graph G S2 , wherein the vertices of the graph include a light sensor of a fixture. Between each vertex, an edge weight is assigned that reflects a confidence in the placement of adjacent (neighboring) fixtures. For an embodiment, the confidence level is dependent on the relative value of the sensed light intensity. The greater the sensed value, the greater the confidence level. Once the graph G S2 has been constructed, the graph G S2 can be written to memory (step 1030 ). The process of FIG. 10 provides an exemplary embodiment of algorithmically processing the light intensity data. The flow chart provides for construction of G S2 from the light intensity data.
LQI units can be used to construct G s3 graph similar to Graph G s2 . Referring to FIG. 5 , it can be concluded that a very high value of LQI between two fixtures implies that the fixtures are one degree close with high measure of confidence, irrespective of the noise factors involved in LQI readings. LQI unit can compute the LQI between two fixtures, compute LQI readings for all possible pairs of sensors (fixtures).
FIG. 11 shows an example of data generated by an LQI sensor unit, according to an embodiment. More specifically, the table includes a designation of the fixture that generates the electromagnetic signal, and then the fixtures that sense the electromagnetic signal, and a sensed LQI (Link Quality Indicator) of the received signal. The LQI of the fixture that receives electromagnetic signal having the greatest LQI is the fixture that has the best quality electromagnetic link. Typically, the fixture have the best electromagnetic link with the electromagnetic source, is the fixture that is closest to the fixture that generates the electromagnetic signal.
FIG. 12 shows steps of a method of constructing a graph G S3 from data generated by an LQI sensor unit, according to an embodiment. A first step 1210 includes retrieving the sensed LQI data from memory. A second step 1220 includes transmitting an electromagnetic signal by a one of a plurality of LQI units of the fixtures, and sensing LQI by the plurality of fixtures. The fixtures with the highest sensed LQI are determined to be the neighboring fixtures. A level of confidence is determined by the value of the sensed LQI. The neighboring fixture having the largest LQI is assumed to be the fixture that is closest to the fixture that transmits the electromagnetic signal.
A third step 1230 includes constructing a graph G S3 wherein fixtures of the LQI sensors are assigned to vertices of the graph G S3 , an edge exists between two vertices if they are immediate neighbored and the edge weight is equal to the confidence measure.
Once the graph G S3 has been constructed, the graph G S3 can be written to memory (step 1240 ).
For at least some embodiments, and Automated Commissioning System and/or method involves construction of a weighted graph (sensor graph) that includes nodes, wherein each node represent LCS (lighting control sensor, which can include a sensor and/or a lighting fixture) and weights on the edges between the nodes that represent a measure of distance between nodes (G s ). For at least some embodiments, the weighted graph is computed by algorithmically processing the sensing data sent by LCS's. Further, a Graph G s is computed by synthesizing the 3 Distance Graphs G s1 , G s2 , G s3 generated from the data sent by Motion Detecting Unit, Light Intensity Detecting Unit and LQI unit, respectively. The commission is completed through inexactly matching of the graph G s (sensor graph) with a floor plan graph (G f ).
FIG. 13 is a flow chart that include steps of a method of constructing a compiled graph G S from the graphs G S1 , G S2 G S3 , according to an embodiment. A first step 1310 includes retrieving the graphs G S1 , G S2 G S3 from memory. A second step 1320 includes for each pair of fixtures, synthesizing the edge weights. As previously stated, the edge weights reflect a level of confidence in the pair being neighboring fixtures.
A third step 1330 includes constructing a compiled graph G S in which a fixture is located at vertices, and edges between the vertices include synthesized weights from each of the graphs G S1 , G S2 G S3 .
Once the compiled graph G S has been constructed, the compiled graph G S can be written to memory (step 1340 ).
FIG. 14 is a flow chart that includes steps of a method of constructing the compiled graph G S using a synthesis function, according to an embodiment. As previously described, multiple sensor graphs G S1 , G S2 G S3 are generated based on the sensed signals. The generated graphs include nodes or vertices that represent the locations of the sensors, edges that include an estimated distance between the vertices, and a confidence value that represents a level of confidence in the accuracy of the estimated distance.
For an embodiment, the synthesized graph G S is generated by according to the steps of the flow chart of FIG. 14 . A first step 1410 includes reading the confidence levels of the plurality of sensor graphs at a particular vertex or node, such as, from sensor graphs G S1 , G S2 G S3 -A second step 1420 includes determining of any of the confidence levels are equal to 1. If yes, then the distance associated with the confidence level of 1 is used, and the confidence level of the synthesized distance estimate is set to 1 as well (step 1425 ). A third step 1430 includes determining if any of 2 confidence levels are greater than 0.75. If yes, then the synthesized confidence level is set to 1 (step 1435 ). A fourth step 1440 includes determining if any 2 confidence levels are greater than 0.50. If yes, then the synthesized confidence level is set to 0.75 (step 1445 ). A fifth step 1450 includes determining if any 2 confidence levels are greater than 0.25. If yes, then the synthesized confidence level is set to 0.50 (step 1455 ). A sixth step 1460 includes determining that all the confidence levels are 0. If yes, then the synthesized confidence level is set to 0 (step 1465 ). If all the confidence levels of step 1460 are not determined to be 0, then the synthesized confidence level is set to 0.25 (step 1470 ).
FIG. 15 is a flow chart that includes steps of a method of constructing a floor plan graph G f , according to an embodiment. A first step 1510 includes reading a floor plan of the area. For an embodiment, the floor plan is an existing plan that includes the exact location of all the sensor/fixtures within an area. However, the floor plan does not include information of which sensor/fixture is in each location, just that a fixture/sensor is in the precise location(s). A second step 1520 includes for each sensor/fixture, determining its immediate neighbor sensor/fixture using the (x,y) co-ordinates of the sensor/fixture. With this information, a third step 1530 includes constructing a floor plan graph G f where vertices of the graph represent sensor/fixtures and an edge exists between immediate neighboring sensor/fixtures having a weight 1. That is, the exact location of each sensor/fixture can be determined from the floor plan, and a weight (confidence level) of one can be assigned for the distance between because the exact distances between each vertex (sensor/fixture location) is know from the floor plan. A fourth step 1540 includes writing/storing the floor plan graph.
Matching of Sensor Graph with Floor Plan Graph
Once a representation of a sensor graph (synthesized or not, and including any number of sensor types) has been determined or obtained, and a floor plan graph that represents the actual locations of sensors (and/or light fixtures that include the sensors) has been obtained, the commissioning of the sensors/fixtures includes matching the sensor graphs with the floor plan graph for determining which sensors are at which sensor location of the floor plan graph. This process provides a method of identifying which sensor/fixture is located at which sensor location.
For at least some embodiments, the floor plan graph includes exact locations of the sensors within the structure, and matching includes placing each of the sensors based on the exact location of the sensors of the floor plan graph and information about the sensors of the sensor graph, wherein the information comprises the vertices and estimated distances between the vertices of the sensor graph. For at least some embodiments, the first-degree neighbors of the vertices of the floor plan graph are known, the first-degree neighbors of the vertices of the sensor graph is estimated based on sensed signals of the sensor, and both the floor plan graph and the sensor graph include a same number of vertices. For an embodiment, sensor graph and the floor plan graph are planar with bounded degree.
For at least some embodiment, the inexact graph matching is performed by using customized branch and bound method optimized with respect to time and accuracy. The branch and bound (BB or B&B) is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization. A branch-and-bound algorithm consists of a systematic enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded en masse, by using upper and lower estimated bounds of the quantity being optimized.
For at least some embodiments, vertices of the sensor graph are matched with vertices of the floor plan graph that include a similar edge structure. For at least some embodiments, an edge structure is determined based on a number of first degree neighboring vertices, and the similar edge structure is determined as vertices having a same number of first degree neighboring vertices.
At least some embodiments include identifying vertices of the floor plan graph that include unique characteristics, and matching vertices of the sensor graph that includes the unique characteristics. The unique characteristics include, for example, a unique number of first degree neighbor nodes, and/or unique number of edges.
At least some embodiments include first matching vertices of the sensor graph that include confidence levels above a threshold, and subsequently matching vertices of the sensor graph that include confidence levels below the threshold. For an embodiment, a measure of the confidence level of the vertex is a sum of the confidence levels of edges incident on that vertex.
At least some embodiments include identifying the vertices of the sensor graph that include the highest quality information about neighbors and confidence levels in the edge distances. Best matches identified and performed first, next lower quality matched performed next.
For at least some embodiments, the matching includes selecting a vertex of the floor plan graph to match a vertex of the sensor graph, wherein the degrees of the vertex of the floor plan graph and the degrees the vertex of the sensor graph are a maximum, and a difference between the degrees of the vertex of the floor plan graph and the vertex of the sensor graph are a minimum, and the vertex of the floor plan graph and the vertex of the sensor graph have not been previously matched, wherein the degrees reflects a number of neighboring vertices. That is, a vertex V f1 is selected from the floor plan graph and a vertex V s1 is selected from the sensor graph such that degrees of V f1 and V s1 are maximum, difference in degree of V f1 and V s1 is minimum and V f1 and V s1 have not been picked earlier. Next a determination is made regarding how good the match is between one degree neighbor of V f1 and V s1 and if it's good enough then continue with the best neighboring vertex else start afresh and go back to the previous step. If good match is found then output it or if too much time is consumed then output the best match found to date.
At least some embodiments include scoring a quality of the matching based on at least one of a difference in a cardinality of an edge set of the floor plan graph and the sensor graph, cardinality of a vertex set of the floor plan graph and the sensor graph, and/or a measure of a dis-similarity in an edge structure of the floor plan graph and the sensor graph after the match. For an embodiment, an error or quality estimate of the matching includes difference in the match score and ideal match score. The difference in number of edges between the floor plan graph and sensor graph gives a measure of the ideal match score.
FIG. 16 a floor plan graph according to an embodiment, and FIG. 17 shows a sensor graph according to an embodiment. As previously described, the vertices of the graphs represent sensor locations. The following are exemplary steps for matching Graphs G 1 (Floor Plan Graph) and G 2 (Sensor Graph). The graph matching process involves mapping all Vertices from one graph to another such that a maximum number of edges are matched and there is minimum number of mismatch between edges.
A first step (a) includes picking a Vertex from each graph such that they are similar and are have a maximum degree. A measure of similarity can be degree of Vertex. For example in Graph 1 and Graph 2 there are many pairs of vertices which satisfy above criteria of selection. Vertex pair (X 16 , Y 16 ) is one such pair, (X 10 , Y 16 ) is another, (X 10 , Y 10 ) is another but not (X 22 , Y 22 ).
A second step (b) includes assigning a cost to each Vertex match as sum of dissimilarity between Vertex. A measure of dissimilarity can be sum of difference in degree of matched Vertex and Match score of 1-degree neighboring graphs of matched Vertex. For example if Vertex Pair (X 16 and Y 16 ) are matched then the cost of Matching=(|degree of (X 16 )−degree (Y 16 )|+MatchScoreOf 1-degreeNeighbourerGraphs of (X 16 ,Y 16 )). The cost of Matching Vertex (X 16 ,Y 16 ) would be (0+(0+1+1+2))=4 and 1-degree neighboring vertices matched would be ((X 10 ,Y 10 ), (X 15 ,Y 15 ), (X 17 ,Y 17 ), (X 22 ,Y 22 )). Note: MatchScoreOf 1-degreeNeighbourerGraphs of (X 16 ,Y 16 )) is calculated by using step “c” defined below.
A third step (c) includes computing a MatchScoreOf 1-degreeNeighbourerGraphs by executing following steps:
1. To start the match, pick up Vertex from each graph such that they are similar and are have a maximum degree. For an embodiment, a measure of similarity is a degree of the Vertex. For example if (X 16 , Y 16 ) were matched then 1-degreeNeighbourerGraphs that are being matched are G 1 =(Vertices 1 =(X 10 , X 15 ,X 17 ,X 22 ), Edges 1 =((X 10 ,X 15 ), (X 10 , X 17 ), (X 15 , X 22 ), (X 17 , X 22 ))) and G 2 =(Vertices 2 =(Y 10 , Y 15 ,Y 17 ,Y 22 ), Edges 2 =((Y 10 ,Y 15 ), (Y 10 ,Y 17 ))) and as per the condition described above match vertices (X 10 , Y 10 ); 2. Assign cost to Vertex match as sum of dissimilarity between Vertex. A measure of dissimilarity can be difference in degree of matched vertices. For example if Vertex Pair (X 10 ,Y 10 ) are matched then the cost of Matching=(|degree of (X 10 )−degree (Y 10 )|)=(2−2)=0; 3. Next match the vertex pair which are similar and have maximum degree. A measure of similarity can be degree of Vertex. For example:—After (X 10 , Y 10 ) are matched one can match (X 15 , Y 15 ) and the cost of this match would be (1−0)=1; 4. MatchScore would be sum of cost of matches until now=(0+1)=1; 5. When there are no more vertices to be matched then the matching process stops and the MatchScoreOf 1-degreeNeighbourerGraphs is sum of cost of matched vertices; 6. If MatchScore is low enough value then it is acceptable Match. For example if |MatchScore−∥cardinality(Vertices 1 )−cardinality(Vertices 2 )|+|cardinality(Edges 1 )−cardinality(Edges 1 )|∥<=√min(cardinality(Vertices 1 ), cardinality(Vertices 2 )) then it can be considered as low matchscore and matching process stops. 7. If Match is not good then one goes back to step “a” and restart the match process, until a match with acceptable low score is found.

A fourth step (d) includes picking up that vertex matched pair whose degree is maximum and the difference in degree in minimum from 1-degree neighboring vertices matched set. For example while matching (X 16 ,Y 16 ) the 1-degree neighboring vertices matched set was ((X 10 ,Y 10 ), (X 15 ,Y 15 ), (X 17 ,Y 17 ), (X 22 ,Y 22 )) and vertex pair (X 10 ,Y 10 ) satisfy the condition of maximum degree and minimum degree difference, so the next vertex pair which is matched is (X 10 ,Y 10 ).
A fifth step (e) includes using step (b) to determine the cost of matching the new vertex pair found in step (d).
A sixth step (f) includes repeating step (d) in finding the next pair of vertex match.
A seventh step (g) includes repeating steps (b) to (d) until all vertices are matched.
An eighth step (h) includes determining a cost of the Graph match which is the sum of cost of matching vertices.
A ninth step (i) includes determining if |(cost of Graph match−Difference in the cardinality of edges of two Graphs)|<=√(cardinality(Vertices of Graph)) then it's an acceptable match else restart the matching process by going to step “a”.
FIGS. 18, 19, 20 show steps of methods for analyzing and matching two un-weighted graphs with a maximum run time, and outputting a best match found between the two graphs and a score of the best match, according to at least some embodiments.
FIGS. 21, 22, 23 show steps of methods for finding a match between two one-degree neighboring graphs with a maximum run time, and outputting a score of the best match, according to at least some embodiments.
FIGS. 24, 25 show steps of methods of providing a best match between a pair of vertexes of two graphs in which matching of the graphs is already known, according to an embodiment.
Although specific embodiments have been described and illustrated, the described embodiments are not to be limited to the specific forms or arrangements of parts so described and illustrated. The embodiments are limited only by the appended claims.