Service-to-device mapping for smart items using a genetic algorithm

• US 20070251998A1
• Filed: 04/28/2006
• Published: 11/01/2007
• Est. Priority Date: 04/28/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Belenki, Mikhail
• Granted Patent: US 7,890,568 B2
• Time in Patent Office: Days
• US Class Current: 235/380
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04L 41/16 using machine learning or artificial intelligence
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Systems and methods allow service-to-device mapping using genetic algorithm logic by which services are mapped onto best-suited smart items selected from a plurality of smart items of a sensor network. As part of the mapping, and/or subsequent thereto, a deployment of the service(s) onto the smart items is initiated. A sorted repair structure indicating an ordering of services in accordance with a hierarchy of atomic services and composite services based on a composition of services for one or more devices of a sensor network is determined. One or more derived generation structures are determined based on genetic algorithm logic that is operable on the sorted repair structure. A service is mapped onto at least one device of the sensor network, based on one of the derived generation structures. As a result, users may achieve a desired result in a fast, convenient, and reliable manner, even when executing the deployment remotely or automatically.

Claims

1. A method comprising:

determining a sorted repair structure indicating an ordering of services in accordance with a hierarchy of atomic services and composite services based on a composition of services for one or more devices of a sensor network;

determining one or more derived generation structures based on genetic algorithm logic that is operable on the sorted repair structure; and

mapping a service onto at least one device of the sensor network, based on one of the derived generation structures.

2. The method of claim 1 wherein determining the sorted repair structure comprises:

determining a request list indicating requested services for mapping onto the one or more devices of the sensor network; and

determining a sorted request list indicating the requested services based on the request list, sorted based on the ordering of services in accordance with the hierarchy of atomic services and composite services corresponding to the requested services.

3. The method of claim 1 wherein determining the sorted repair structure comprises:

determining a repair vector indicating requested services for mapping onto the one or more devices of the sensor network and deployment constraints indicating constraints associated with installing each of the requested services on one or more of the devices, the repair vector sorted based on the ordering of services in accordance with the hierarchy of atomic services and composite services corresponding to the requested services.

4. The method of claim 3 wherein each of the composite services comprises a composition of two or more of the requested services and wherein a first one of the requested services of the composition depends on an installation of a second one of the requested services of the composition installed on at least one device of the sensor network.

5. The method of claim 4 wherein the ordering of services in accordance with the hierarchy of atomic services and composite services corresponding to the requested services includes ordering each of the atomic services in an order preceding all composite services that depend on the each atomic service in a hierarchical ordering of the corresponding requested services.

6. The method of claim 1 wherein determining one or more derived generation structures based on genetic algorithm logic that is operable on the sorted repair structure comprises:

determining one or more base generation structures, based on the sorted repair structure;

modifying the base generation structures based on resource constraint logic operable on service metadata; and

determining one of the derived generation structures based on the modified base generation structures.

7. The method of claim 6 wherein modifying the base generation structures comprises:

determining whether the base generation structures include one or more installation indicators indicating installation of requested services onto the one or more devices of the sensor network, the installation indicators sorted based on the ordering of services in accordance with the hierarchy of atomic services and composite services corresponding to the requested services.

8. The method of claim 6 wherein modifying the base generation structure comprises:

determining whether a deployment constraint is violated based on a statistical analysis of system metadata.

9. The method of claim 6 wherein modifying the base generation structure comprises:

selecting two or more of the base generation structures as parent chromosomes based on a roulette operation; and

determining at least one child chromosome based on performing a crossover operation on the two or more parent chromosomes by the genetic algorithm logic.

10. The method of claim 6 wherein modifying the base generation structure comprises:

selecting one of the base generation structures as a selected chromosome; and

determining a mutated chromosome based on performing a mutation operation on the selected chromosome by the genetic algorithm logic.

11. A system comprising:

a network monitor configured to monitor a plurality of devices of a sensor network, and configured to determine device metadata associated with at least one of the plurality of devices; and

a service mapper configured to determine a base generation structure, based on one or more sorted repair structures indicating an ordering of services in accordance with a hierarchy of atomic services and composite services based on a composition of services associated with the devices, based on the device metadata, and based on service metadata associated with the service, and configured to map a service onto the at least one device based on a derived generation structure that is based on genetic algorithm logic operable on the base generation structure.

12. The system of claim 11 wherein the service mapper comprises:

a mapping system comprising;

the sorted repair structures;

the base generation structure; and

the derived generation structure; and

genetic algorithm logic configured to determine the sorted repair structure based on the composition of services.

13. The system of claim 11 wherein the sorted repair structure comprises a repair vector sorted based on the ordering of services in accordance with the hierarchy of atomic services and composite services.

14. The system of claim 13 wherein each of the composite services comprises a composition of two or more requested services that are requested for installation on at least one of the devices of the sensor network, and wherein a first one of the requested services of the composition depends on an installation of a second one of the requested services of the composition installed on at least one device of the sensor network.

15. The system of claim 13 wherein the ordering of services in accordance with the hierarchy of atomic services and composite services includes ordering each of the atomic services in an order preceding all composite services that depend on the each atomic service in a hierarchical ordering of the atomic services and composite services.

16. The system of claim 11 wherein the base generation structure comprises a chromosome indicating one or more installation states of one or more services on one or more of the devices.

17. The system of claim 16 wherein the chromosome includes a plurality of ordered indicators indicating the one or more installation states, sorted based on the ordering of services in accordance with the hierarchy of atomic services and composite services.

18. The system of claim 16 wherein the genetic algorithm logic is configured to provide a derived generation chromosome based on performing one or more of a selection operation, a crossover operation, a mutation operation, or a repair operation on the chromosome of the base generation structure, and based on the sorted repair structure.

19. A service mapper for a sensor network, the service mapper comprising:

genetic algorithm logic that is configured to provide one or more derived generation structures based on service composition logic that is operable on one or more sorted repair structures indicating an ordering of services in accordance with a hierarchy of atomic services and composite services; and

a mapping system that is configured to map a service onto at least one device of the sensor network, based on one of the derived generation structures.

20. The service mapper of claim 19 wherein the genetic algorithm logic is configured to provide a derived generation chromosome based on performing one or more of a selection operation, a crossover operation, a mutation operation, or a repair operation on a chromosome of the base generation structure, and based on one or more of the sorted repair structures.