Source: http://www.google.com/patents/US7890568?dq=7143430
Timestamp: 2017-05-23 20:11:37
Document Index: 206783724

Matched Legal Cases: ['art 200', 'art 600', 'art 700', 'art 800', 'art 900', 'Application No. 07010671', 'Application No. 07010652', 'Application No. 07010654', 'Application No. 08017795', 'Application No. 07008409', 'Application No. 07008409', 'Application No. 07008409', 'Application No. 07008409', 'Application No. 07008409']

Patent US7890568 - Service-to-device mapping for smart items using a genetic algorithm - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsSystems 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...http://www.google.com/patents/US7890568?utm_source=gb-gplus-sharePatent US7890568 - Service-to-device mapping for smart items using a genetic algorithmAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS7890568 B2Publication typeGrantApplication numberUS 11/413,230Publication dateFeb 15, 2011Filing dateApr 28, 2006Priority dateApr 28, 2006Fee statusPaidAlso published asCN101064652A, CN101064652B, EP1850277A1, EP1850277B1, US20070251998Publication number11413230, 413230, US 7890568 B2, US 7890568B2, US-B2-7890568, US7890568 B2, US7890568B2InventorsMikhail BelenkiOriginal AssigneeSap AgExport CitationBiBTeX, EndNote, RefManPatent Citations (83), Non-Patent Citations (207), Referenced by (36), Classifications (13), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetService-to-device mapping for smart items using a genetic algorithm
US 7890568 B2Abstract
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.
determining, using a processor, 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, using the processor, one or more derived generation structures based on genetic algorithm logic that is operable on the sorted repair structure, 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, and a repair operation on a chromosome of a base generation structure, and based on one or more of the sorted repair structures; and
mapping, using the processor, a service onto at least one device of the sensor network, based on one of the derived generation structures,
wherein determining the sorted repair structure comprises:
determining, using the processor, 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.
2. The method of claim 1 wherein determining the sorted repair structure comprises:
determining, using the processor, a request list indicating requested services for mapping onto the one or more devices of the sensor network; and
determining, using the processor, 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 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.
4. The method of claim 3 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.
5. 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, using the processor, one or more base generation structures, based on the sorted repair structure;
modifying, using the processor, the base generation structures based on resource constraint logic operable on service metadata; and
determining, using the processor, one of the derived generation structures based on the modified base generation structures.
6. The method of claim 5 wherein modifying the base generation structures comprises:
determining, using the processor, 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.
7. The method of claim 5 wherein modifying the base generation structure comprises:
determining, using the processor, whether a deployment constraint is violated based on a statistical analysis of system metadata.
8. The method of claim 5 wherein modifying the base generation structure comprises:
selecting, using the processor, two or more of the base generation structures as parent chromosomes based on a roulette operation; and
determining, using the processor, at least one child chromosome based on performing a crossover operation on the two or more parent chromosomes by the genetic algorithm logic.
9. The method of claim 5 wherein modifying the base generation structure comprises:
selecting, using the processor, one of the base generation structures as a selected chromosome; and
determining, using the processor, a mutated chromosome based on performing a mutation operation on the selected chromosome by the genetic algorithm logic.
10. A computer-implemented system comprising computer-executable code recorded on a non-transitory computer-readable medium comprising:
a network monitor configured via the computer-executable code 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 via the computer-executable code 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, wherein:
the sorted repair structure comprises 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, and
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, and a repair operation on a chromosome of the base generation structure, and based on the sorted repair structure.
11. The computer-implemented system of claim 10 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.
12. The computer-implemented system of claim 10 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.
13. The computer-implemented system of claim 10 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.
14. The computer-implemented system of claim 10 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.
15. The computer-implemented system of claim 14 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.
16. A non-transitory recordable storage medium having recorded and stored thereon instructions that, when executed by a processor, perform the action of using genetic algorithm logic 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 service in accordance with a hierarchy of atomic services and composite services; and mapping a service onto at least one device of the sensor network, based on one of the derived generation structures; wherein: the sorted repair structure comprises 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, and 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, and a repair operation on a chromosome of the base generation structure, and based on one or more of the sorted repair structures. Description
Software systems exist that provide various services for enterprises or other organizations. Such software systems may rely on decentralized, manual, and potentially error-prone data collection, while storing collected data in a centralized back-end system where business logic execution also occurs. These and other software systems may be extended through the use of smart item (also referred to as smart device) technologies, in which physical items (e.g., goods, tools, rooms, vehicles, persons, or shelves) are augmented or enhanced by the addition or inclusion of locally-provided or embedded technology.
Through automatic real-time object tracking and local, on-site execution of business logic, smart item technology may provide businesses with accurate and timely data about business operations, and also may help streamline and automate the business operations. Accordingly, cost reductions and additional business benefits (e.g., increased asset visibility, improved responsiveness, and extended business opportunities) may be obtained.
According to one general aspect, 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 based on genetic algorithm logic that is operable on the sorted repair structure is determined. A service is mapped onto at least one device of the sensor network, based on one of the derived generation structures.
According to another general aspect, a system includes 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. The system also includes 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.
According to another general aspect, a service mapper for a sensor network includes 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. The service mapper also includes 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.
FIG. 1 is a block diagram of an example system for service-to-device mapping for smart items using a genetic algorithm.
FIG. 2 is a flowchart illustrating example operations that may be performed by the system of FIG. 1.
FIG. 3 is a block diagram illustrating an example service composition hierarchy that may be utilized by the system of FIG. 1.
FIG. 4 is a block diagram illustrating an example sorted services list that may be utilized by the system of FIG. 1.
FIG. 5 is a block diagram illustrating an example sorted repair structure that may be utilized by the system of FIG. 1.
FIG. 6 is a flowchart illustrating additional example operations that may be performed by the system of FIG. 1.
FIG. 7 is a flowchart illustrating example operations to repair base generation structures having invalid combinations of services of the system of FIG. 1.
FIG. 8 is a flowchart illustrating example operations to repair base generation structures based on resources and composition of the system of FIG. 1.
FIG. 9 is a flowchart illustrating example operations to select base generation structures for inclusion in the derived generation structures of the system of FIG. 1.
FIG. 1 is a block diagram of a system 100 for a service-to-device mapping for smart items using a genetic algorithm. As described in more detail below, the system 100 may be configured to perform a mapping function, using a genetic algorithm, by which services may be mapped onto suitable smart items selected from a plurality of smart items of a sensor network 102. As part of the mapping, and/or subsequent thereto, a deployment of the service(s) onto the smart items may be initiated. Genetic algorithm techniques may be used as part of the mapping process to attempt to produce an optimal mapping. As a result, operators and users of the system 100 may achieve a desired result in a fast, convenient, and reliable manner, even when executing the deployment remotely or automatically, and may thus more conveniently use the system 100 in a desired fashion.
Service mapping may be used when a defined number of instances of a given service are requested to be installed on the network nodes; if a service is a composite service, for example, a service that needs other services installed to function properly, then services from its composition may also be mapped. The sensor network 102 may include nodes that are resource constrained. Thus, consequently, the mapping may be interpreted as a constrained optimization combinatorial problem. Therefore, genetic algorithms may be used in finding a solution, for example, an optimal mapping of the services to the devices of the network. The genetic algorithm techniques described herein for solving the mapping problem may include genetic algorithm concepts such as chromosomes, populations, selection, crossover or recombination, and mutation, and may accommodate consideration of constraints, for example, service constraints, network node constraints, and network constraints. Generally, genetic algorithms may include search techniques used to find approximate solutions to optimization and search problems. Genetic algorithms may be used as a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, natural selection and recombination, or crossover.
Genetic algorithms may be implemented as computer simulations in which a population of abstract representations of candidate solutions evolves toward better solutions. The abstract representations may be referred to as chromosomes which include genes, and the candidate solutions may be referred to as individuals. Solutions (e.g., chromosomes and individuals) may be represented using structures including binary digits as strings of 0's and 1's, but different encodings are also possible, e.g., floating point, character, table elements, linked list encodings, etc. The evolution may start from a base population of random individuals and iterate through evolving derived generations. In each generation, a fitness (or unfitness) of the whole population may be evaluated, multiple individuals may be stochastically selected from the current population (e.g., based on their fitness or unfitness), and modified (e.g., recombined or mutated) to form a new, or derived population, which replaces the base population in the next iteration of the algorithm.
The fitness/unfitness may be determined based on a fitness/unfitness function, which may quantify the optimality/grade of constraint satisfaction of a solution (e.g., a chromosome) in a genetic algorithm. Optimal chromosomes, or at least chromosomes which are more optimal, may then be allowed to breed and mix their datasets by any of several techniques, producing a new generation that may include even better chromosomes. As an example of a fitness/unfitness function, consider a health spa for adults that may specify a female's optimal weight to be 60 kilograms. An example unfitness function could then be defined for a female x as:
unfitness (x)=absolute value (actual weight (x)−60).
Using this example, if a female actually weighs 70 kilograms, then her unfitness may have a value of 10, while a female weighing 60 kilograms may have an unfitness value of 0 (e.g., indicating an optimal weight). Similarly, the female weighing 60 kilograms may be assigned a high value of fitness based on a suitable fitness function, for example:
fitness (x)=10−unfitness (x).
An example system and method described further with respect to FIGS. 1-9 is based on genetic algorithm concepts and uses concepts of evolutionary processes, but the example system and method based on genetic algorithms may encompass problem specific knowledge, which may be used to find feasible solutions of the service mapping problem, which may satisfy constraints such as resource constraints and service composition constraints associated with a network.
In the example of FIG. 1, the sensor network 102 may include various smart items or smart devices 104, 106, 108, and 110. That is, it should be understood that the terms “smart items,” “smart devices,” “smart item devices,” and similar terms, may be used similarly or interchangeably in various contexts. For example, the term “smart item” or “smart device” may refer to a device having local processing, storage, and communications capability, as referenced above, or may refer to a combination of such a device and an object to which the device is affixed (e.g., a pallet containing merchandise for sale). As part of the sensor network 102, such devices and/or device/object combinations also may be referred to as “nodes,” or “network nodes” in some contexts. In the present description, the term “device” is used for brevity and consistency to refer to the described devices having the described features within the sensor network 102.
Thus, the devices 104, 106, 108, 110, and potentially other devices within the sensor network 102 (and other sensor networks) may provide real-world data to one or more business data processing systems, applications, or processes, in a timely and accurate manner. Examples of such business processes may include, for example, inventory management systems, supply chain management systems, retail store management systems, warehouse management systems, product life cycle management systems, and any other system(s) that may be used to execute business processes with respect to real-world objects, where such real-world objects may include, for example, products for sale, pallets or other shipment elements, patients, or manufacturing materials/equipment. Thus, the business processes, including those portions of the business processes deployed and executed at the local level of the real-world objects, may be used, for example, to determine inventory levels, set pricing levels, evaluate marketing strategies, evaluate manufacturing or production technologies, reduce theft, or maintain safety.
In FIG. 1, the device 104 is illustrated as including a central processing unit (CPU) 112, as well as a memory 114. Thus, the device 104 should be understood to be capable of various levels of computing capabilities, including, for example, processing or transmitting sensed data (in the case where the device 104 includes, or is associated with, a sensor). Although not specifically illustrated in FIG. 1 for the sake of clarity and brevity, it should be understood that the devices 106, 108, and 110 also may include the same or different computing capabilities, including, for example, the capability to form and participate in the local network 102, such as a wireless network and/or a peer-to-peer network. That is, it should be understood that the devices 104, 106, 108, and 110 may include other standard elements and features, not specifically illustrated in FIG. 1 for the sake of brevity, such as, for example, a (e.g., radio) transceiver and a local power supply/battery.
Thus, the local network 102 may be used to collect, process, filter, aggregate, or transmit data that may be useful to related business processes, and, more specifically, may be used to execute portions of the business processes (e.g., business logic), that are best-suited for (or benefit most highly from) local execution. Specifically, in the example of FIG. 1, the portions of the business processes/business logic deployed on the sensor network include service B 116 that is deployed on the devices 104, 110, and service D 118 that is deployed on the devices 104, 106.
Various aspects and characteristics of services such as the service B 116 and service D 118 are described in more detail, below, e.g., with respect to FIG. 3. In general, though, it should be understood that the service B 116 and service D 118, and other services discussed herein, refer generally to software components that support a defined functionality, provide a defined interface through which the service may be invoked, and that may be combined with one another to obtain/provide additional or more complex functionalities. For example, the service B 116 and service D 118 may represent enabling services that, e.g., enable collaboration between two or more of the devices 104, 106, 108, 110; or may represent management services that, e.g., manage power consumption of the device 104; or may represent actual business services that, e.g., execute business-specific logic (such as determining a local temperature, and whether the local temperature exceeds a defined value, and whether any action should be taken in response to the local temperature exceeding the defined value).
More specifically, the service B 116 and service D 118 may represent instances of services (or service templates) stored in a service repository 120. The service repository 120 may thus provide a convenient location for registering, storing, and accessing services that may be deployed for use within the sensor network 102.
The service repository 120 may store service executables 122 and service metadata 124, where the service executables 122 may represent software code that may be instantiated onto the devices 104, 106, 108, 110 for actual execution of associated business logic, while the service metadata may represent or include, for example, various service descriptions and/or requirements that relate to whether and how the service(s) may be executed on one or more devices of the sensor network 102. For example, the service metadata 124 may include a service behavior description, or technical constraints of the service. For example, technical constraints may include a required CPU type or speed, an amount of (free) memory that is needed, a type or speed of connection that is required or preferred, an operating system version/name/description, or a type or status of a battery or other device power source(s). With respect to the service metadata 124, distinctions may be made between static and dynamic service requirements, such as hardware requirements. For example, a static value such as a total memory or maximum processing speed may be included, along with dynamic values such as available memory/processing/power, and/or a number or type of other services that may be allowed to concurrently run on a device together with the service(s) in question, at an execution time of the service(s).
In some examples, the same service may be implemented for a plurality of development platforms, e.g., may be implemented for known development platforms that are based on the C/C++ programming language or the Java programming language. By providing such a diversity of development platforms, a given service may be deployable to a wider range or type of devices that may be in use. Information about the development platform(s) of the service in question may be included as a type of the service metadata 124. Additionally, service interface information describing how the associated service may be called/invoked may be included in, or associated with, the service metadata 124.
The system 100 includes a service mapper 126 that may be configured to select at least the device 104 as a selected device from among the plurality of devices 104, 106, 108, 110 of the sensor network 102, for deploying the service B 116 and service D 118 thereon, as shown. For example, the service mapper 126 may operate in response to a request from an administrator, or may act automatically in response to a command from an associated business process. Thereafter, the service mapper 126 may access the service repository 120, and may determine appropriate information (i.e., information appropriate to the request or command) from the service metadata 124 and the service executable(s) 122.
In determining whether and how to map services from the service repository 120 onto one or more of the devices 104, 106, 108, 110 of the sensor network 102, the service mapper 126 may be in communication with a network monitor 128. The network monitor 128 may be operable to detect or otherwise determine information related to the devices 104, 106, 108, 110, related to the sensor network 102 as a whole (e.g., to interactions between the devices 104, 106, 108, 110), or related to an environment or use of the devices 104, 106, 108, 110. The network monitor 128 may thus provide, for example, hardware health diagnosis, or may provide statistical data for system software (e.g., names and runtime information regarding the service B 116 and service D 118). In some cases, application or service-specific monitoring may be implemented, based on the needs of the application/service. While the network monitor 128 is illustrated in FIG. 1 as a separate component from the sensor network 102, it should be understood that some or all of the network monitor 128 may be implemented at the service level on one or more of the devices 104, 106, 108, 110 of the sensor network 102. For example, the service D 118 may be a locally-deployed monitor service that is operable to collect and report information about a current status of the CPU 112, or the memory 114, or some other local characteristic of information.
Thus, in the example of FIG. 1, the network monitor 128 is operable to determine and provide device metadata 130. For example, the device metadata 130 may include a description of a corresponding device of the devices 104, 106, 108, 110, where the description may be constructed according to an ontology and/or schema that is known to the service mapper 126 and common to the various devices 104, 106, 108, 110. Additionally, or alternatively, the device metadata 130 may be collected in a device-specific format or structure for each of the devices 104, 106, 108, 110, and may thereafter be converted into such a common schema for use by the service mapper 126. For example, the device metadata 130 may include a description of various technical capabilities of the devices 104, 106, 108, 110, provided in an eXtensible Markup Language (XML)-based language, e.g., according to a defined XML schema. Of course, other formats, languages, and/or structures may be used, as well.
More generally, the device metadata 130 may include, for example, a device description, a software description, a hardware description, and a device status. For example, the device description may include a device name, identifier, or type, or may include vendor information including a vendor name or vendor website. The software description may include an operating system description, including version and/or vendor, or may include a description of services running or allowed to run on the device platform. The hardware description may include information about attributes of the CPU 112 (e.g., name or speed), memory 114 (e.g., total amount of memory), or connection capabilities (e.g., connection speed or connection type) of the device(s). The device status may include more volatile information, including a device location, current CPU usage, or remaining power or memory. Of course, other device aspects or information may be included in the device metadata 130, as described below and/or as would be apparent. For example, the device metadata 130 may include information about other devices, such as where the device 104 includes (or is associated with) an RFID reader, and the device metadata 130 may include a description of types of RFID tags that may be read and/or written to by the RFID reader.
Also, although the device metadata 130 is illustrated in FIG. 1 as being determined by the network monitor 128, it should be understood that at least the static device constraints (e.g., total memory or vendor information) may be stored separately, e.g., in a device (metadata) repository (not shown in FIG. 1), similar to the service repository 120. Such a device repository also may be used to store device metadata recently collected by the network monitor 128 (e.g., dynamic but slowly-changing, recently-collected device metadata).
Using at least the service metadata 124 and the device metadata 130, the service mapper 126 may map a given service onto one or more of the devices 104, 106, 108, 110 of the sensor network 102. Such a mapping is designed not only to value-match various aspects of the service metadata 124 and the device metadata 130, where necessary (e.g., matching a required memory specified in the service metadata 124 with a device memory specified in the device metadata 130), but also to enable and optimize a deployment and execution of the service in question. For example, it may be the case that both the device 104 and the device 110 are nominally or ostensibly capable of running the service B 116 (e.g., both devices 104 and 110 may posses some minimum required values of memory, processing capabilities, or power). However, it may be the case that the service B 116 is more power-hungry than memory-hungry (or vice-versa), so that the service mapper 126 may map the service B 116 to the device 104 if the device 104 is currently able to provide more power relative to the other candidate device 110, even if the device 110 currently provides more free memory than the device 104.
Thus, the service mapper 126 may be configured to determine (or attempt to determine) which of the matching or candidate devices is quantitatively and qualitatively best-suited to perform the function of the service in question. For example, a fulfillment priority may be applied that assigns a numeric weight or other priority information to one or more attributes of the service metadata 124 and/or the device metadata 130, so that the service mapper 126 may perform mapping of the associated service(s) accordingly. Of course, many different criteria may be associated with the fulfillment priority, such as, for example, information about a certain type or brand of device, or device platform, that is known to provide some advantage or benefit in executing a service to be deployed, e.g., in terms of reliability. Therefore, in such an example, all devices of this type, brand, or platform may be assigned corresponding priority information.
The network monitor 128 also may determine network metadata 132, such as, for example, various network parameters, particularly where such parameters are dynamic and not necessarily discernable from information about any single device. One such example of the network metadata 132 may include available bandwidth on the sensor network 102. Other examples include location information, mobility characteristics of the network as a whole, and reliability of network connections.
In performing the service mapping, the service mapper 126 also may access other information deemed to be useful or required for the mapping. For example, deployment constraints 134 may include various constraints applicable to one or more services, service deployments, and/or to the sensor network 102 itself. For example, and as discussed in more detail below, the deployment constraints 134 may include constraints requiring a maximization of battery life or battery usage in the sensor network 102, or may otherwise govern service deployment aspects that may be generic to a plurality of services and/or to a plurality of the devices 104, 106, 108, 110.
Once an appropriate service mapping has been performed by the service mapper 126, a service injector 136 may be used to install and start/activate the mapped service (e.g., the service B 116) on the device 104. The service injector 136, more generally, also may be used to manage a life cycle of the service(s), e.g., by performing service updates or stopping the service when necessary.
Thus, one task of the service injector 136 is transferring concrete service code (e.g., an appropriate one of the service executable(s) 122) to the selected/mapped device(s). Thus, the service injector 136 receives and installs the kind of code in question. Such an install component as the service injector 136 may be installed on the device-side, e.g., as a single standalone software component, or may cooperate with other installation components in order to distribute instances of the (mapped) service executables 122. After installing the instances of the service executable(s) 122, the service B 116 may be kept in an inactive state until the service injector 136 sends a start-up signal to change the service B 116 to a started, or active state. In a similar way, the service injector 136 may be used to organize the updating, stopping, or removal of services. Once mapping of the service B 116 has occurred, and the service B 116 has been installed and started on the device 104, then execution of the service B 116 may continue, as needed.
In the following examples, reference is made to a service C 138 that is to be deployed onto one or more devices of the sensor network 102. That is, it is assumed that a request for a mapping and deployment of the service C 138 has been received, so that subsequent mapping by the service mapper 126 may proceed accordingly. As such, and from the above explanation, it should be understood that the service C 138 may ultimately be deployed to whichever of the devices 104, 106, 108, 110 is determined to be best-suited for execution of the service C 138. In the examples below, the service C 138 is generally discussed as being mapped to, and deployed to, at least the device 104, as shown in FIG. 1.
In performing the mapping, the service mapper 126 may include a mapping system 140. As described, the mapping system 140 may be configured to receive a request for a service deployment (e.g., from a user entering a request to deploy a specified service, or in conjunction with the business process(es) that requires a service to be deployed). Based on the request, the mapping system 140 may determine that the service C 138 should be mapped and deployed onto at least one device of the sensor network 102, and, accordingly, may determine the service executable 122 of the service C 138, as well as associated service metadata 124, from the service repository 120. Current device metadata 130 may then be obtained for some or all of the plurality of devices 104, 106, 108 110, e.g., using the network monitor 128. Then, the mapping system 140 may determine a selected device (e.g., the device 104) from the plurality of devices 104, 106, 108, 110, based on the service metadata 126 and the device metadata 130 (and/or based on the network metadata 132).
In some cases, however, it may be the case that such a mapping and deployment initiated by the mapping system 140 may not succeed, or may only partially succeed. For example, as should be understood from the above description, an allowable deployment condition 142 may be required to exist at a time of the deployment, in order for successful deployment of the service C 138 to occur. The allowable deployment condition 142 may include, for example, that the deployment constraints 134 are met, or that service requirements (specified in the service metadata 124) associated with the service C 138 may adequately be met by device constraints (e.g., specified in the device metadata 130) associated with a device(s) of the sensor network 102. In the latter case, for example, the service C 138 may require a certain amount of free memory, or a certain processor speed, so that device constraints associated with a given device, such as the device 104 (e.g., with the memory 114 or the CPU 112) may not be sufficient to satisfy the service requirement(s), particularly given that the service B 116 and service D 118 are already being hosted and run by the device 104.
In the example of FIG. 1, then, it should be understood that the terms “deployment condition” and “allowable deployment condition,” or similar terms, may refer at least in part to condition(s) of physical conditions existing (or desired/required to be existing) with respect to the sensor network 102, such as a number or type of services deployed on the sensor network 102, an amount of the memory 114 existing or available for deployment of services, or a deployment constraint. In other words, such deployment conditions may overlap or encompass, in the context of a particular deployment at a particular time, some or all of the service metadata 124, the device metadata 130, the network metadata 132, or the deployment constraint(s) 134. Thus, such deployment conditions may represent a matching or fulfillment (or lack thereof) between the service metadata 124, the device metadata 130, the network metadata 132, or the deployment constraint(s) 134, for (in this case) deployment of the service C 138 onto the sensor network 102. As such, such deployment conditions may be represented, in whole or in part, as, for example, XML documents that describe the associated physical conditions for use by the mapping system 140 (as represented by the allowable deployment condition 142), where parameters of such XML documents at a given time may be determined from the service repository 120, the network monitor 128, and the deployment constraints 134.
For example, as referenced above, the service C 138 to be deployed in the example of FIG. 1 may be associated with the service metadata 124, which may include requirements of the service C 138 that are needed for the service C 138 to be successfully deployed and executed. Each such requirement may be provided within the service repository 120 as a range of acceptable values (e.g., from a minimum to a maximum acceptable value(s)), rather than as a single value. For example, the service C 138 may be associated with service requirements specifying that the service C 138 should be deployed only to a device having available memory, battery power, and/or transmission speed within certain specified ranges, e.g., min-max ranges.
In one example illustrated in FIG. 1, it may be the case that the service mapper 126 first attempts to map and deploy the service C 138 onto the sensor network 102, and, in so doing, may determine that the device 104 is the most likely candidate device for receiving the service 138 (due to, for example, local capabilities/functionalities of the device 104, or due to the device 104 (and associated device constraints) being closest of all available devices to matching the service requirements associated with the service C 138.
As described above, the deployment constraints 134 may generally refer to globally-applicable constraints, i.e., may refer to global constraints associated with the sensor network 102. Examples of the deployment constraints 134, as also referenced above, may include constraints requiring that all deployments (or a certain deployment): minimize battery usage, minimize memory usage, or minimize usage of processing power. Further, the deployment constraints 134 may designate that it is more important to minimize memory usage, or may designate that it is more important to minimize battery usage, even if sub-optimal memory usage or processing power occurs as a result. Thus, in the latter case, for example, the mapping system 140 may select the device 104 as being extremely power-efficient, and may thus determine that the device 104 is potentially well-suited for deployment of the service C 138.
Deployed services may include certain enabling services that may not be removed from an associated device without severely restricting an operation of the associated device and/or the sensor network 102 as a whole. For instance, it may be the case that the service D 118 is associated with a component or functionality of the service injector 136, so that removal of the service D 118 would thereafter render it impossible to inject new services onto the device 104. As a result, the mapping system 140 and associated algorithm(s) may include logic for ensuring that the service D 118 is not removed from the device 104.
The service mapper 126 includes logic that may be configured to determine one or more sorted repair structures 144 included in the mapping system 140 based on predetermined composition requirements of services to be mapped to the sensor network 102, for a request to map one or more services to the sensor network 102. The sorted repair structures 144 may include structures, for example, bit strings representing services to be installed on network nodes. The bit values included in the structures may be sorted to indicate 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, which may include, for example, ordering the bits corresponding to each of the atomic services in an order preceding the bits corresponding to all composite services that depend on the atomic service in a hierarchical ordering of the corresponding requested services. The ordering may further include, for example, ordering based on priorities among atomic services and composite services. Thus, in an example processing of services, by processing the services in the ordering indicated by the sorted repair structures, it may be unnecessary to backtrack when processing a composite service, as the services upon which the composite service depends may have been previously processed.
Therefore, services may either be implemented as single or atomic services that are substantially self-contained in their execution, or may be implemented as composite or combined services, so that services running on different devices of the sensor network 102 may collaborate to form composite services that a single service/device may not be capable of offering in a proper or efficient way. A composition requirement may include provisions for composite services, such that any particular composite service may need other services, for example, to be installed at specified locations and, for example, to be in a specified state in order for the particular composite service to run properly. For example, a composition requirement may specify that a service W needs a service X such that the service X is installed on the same device or node as service W (i.e., a local location) and service X is in a running state. As an example, locations may include local, neighbor and network locations, wherein a designation of local or neighbor refers to a node location of a service relative to the node location of the composite service. Example states may include a deployed state and a started, or running state.
A service composition may include complex compositions. For example, service W may need service X in a local location and a started state, service Y in a neighbor location and a deployed state, and service Z in a network location and a started state. The services X, Y, and Z may also need other services for their execution. Thus, the mapping of service W may also cause the mapping of all services from its composition, if they have not already been mapped. As one specific example, the service C 138 may collect and aggregate sensor data, e.g., room temperature, which may be measured and sent by each of service D 118 and service E 158.
The service mapper 126 may further include logic configured to determine one or more base generation structures 146 based on the sorted repair structures 144, as well as logic configured to determine one or more derived generation structures 148 based on the sorted repair structures 144 and the base generation structures 146. For example, the base generation structures 146 may include structures representing chromosomes including genes for use by a genetic algorithm. The derived generation structures 148 may include structures representing chromosomes including genes that are derived by a genetic algorithm based on the base generation structures 146 and the sorted repair structures 144. The base generation structures 146 and the derived generation structures 148 may represent binary chromosomes, each of which represents a potential solution of the mapping problem. The size of each chromosome may be determined, for example, based upon the size of the network and the number of services to be deployed.
For example, if a network includes 3 nodes and a service composition, for example, indicating service composition of 5 requested services, and the 5 services are requested to be installed onto the network, an example chromosome may include 15 binary values, determined as the number of network nodes multiplied by the number of requested services. Each example chromosome may include 5 parts, each part corresponding to one of the 5 services, and each part may include 3 genes, each gene corresponding to one of the 3 network nodes. For example, if a gene has a value of 1, the corresponding service may be deployed to its corresponding node. One possible chromosome may then have a value of “001 101 011 111 000”. For this example, parts of the chromosome may reference services in an order Y, Z, W, X, and V. Thus, according to the example chromosome, the service Y, represented by the first three bits, may be installed on the third node, the service Z, represented by the second three bits, may be installed on the first and third nodes, the service W may be installed on the second and third nodes; the service X may be installed on all nodes, and the service V may be not installed at all. The sorted repair structures 144 may include a structure similar to the base generation structures 146 and the derived generation structures 148.
Further, the service mapper 126 may include genetic algorithm logic 150 configured to determine at least the sorted repair structures 144, the base generation structures 146, and the derived generation structures 148 based on resource requirement logic 152, service composition logic 154, and deployment coverage logic 156.
The service composition logic 154 may include logic addressing the composition requirements of services to be mapped to the sensor network 102, as discussed above. As a further example, a composite service A 160 of FIG. 1 may utilize the service B 116, and service C 138, which further utilizes the service D 118 and service E 158. Thus, the service composition logic 154 may be configured to map composite services to ensure, e.g., that a request to map the service A 160 to a device on the sensor network 102 will result in an appropriate mapping of all of the service A 160, service B 116, service C 138, service D 118 and service E 158 to devices on the sensor network 102. Therefore, for this example, the whole composition hierarchy may be mapped.
The deployment coverage logic 156 may include logic addressing deployment coverage requirements associated with the services to be mapped onto the devices of the sensor network 102. A deployment coverage requirement may indicate a number of instances of a particular service that should be installed in the network to support a smooth functionality of the service. The deployment coverage may be represented as an absolute indicator, for example, the service must be mapped to 5 nodes, or as a relative indicator, for example, the service must be mapped to 25% of the relevant nodes. Thus, the deployment constraints 134 may provide a global or governing strategy for executing a given service mapping/deployment. Therefore, deployment coverage requirements may be met by mappings of services to the devices of the sensor network 102.
For example, a generation, e.g., the base generation structures 146 and the derived generation structures 148, may include a group of generation structures referred to as chromosomes, which represent a group of potential solutions of the service mapping problem. The first generation chromosomes, e.g., the base generation structures 146, may be generated randomly by the genetic algorithm logic 150. At least one of the sorted repair structures 144 may be used for checking of resource requirements on each randomly generated chromosome. After the base generation structures 146 are created, an evolutionary technique may be applied by the genetic algorithm logic 150 to generate second, or derived generation structures 148. A genetic algorithm technique of selection may be used to select the best structures (e.g., chromosomes) from the base generation structures 146 for generation of the derived generation structures 148. A genetic algorithm technique of recombination, or crossover, may be applied to a group of the best chromosomes from the base generation structures 146, but some of the chromosomes may be accepted for the derived generation without any changes, according to a predetermined probability.
In order to achieve better diversity, some of the chromosomes may be mutated according to a predetermined probability of mutation. After the creation of each new population or derived generation, each of the chromosomes may be repaired and its unfitness/fitness may be determined based on an unfitness/fitness function. As an example, an unfitness function may measure the difference between the number of instances of a particular service to be deployed as a result of the mapping indicated by the chromosome, and the number of instances of a particular service required to be deployed, for example, according to information that may be included in the service metadata 124, the network metadata 132, the deployment constraints 134, and/or the allowable deployment condition 142.
Since the mapping problem may be constrained, problem specific knowledge may be applied in the genetic algorithm techniques of the genetic algorithm logic 150 via a repair process and an unfitness function in order to solve a constraint satisfaction aspect of the mapping problem. Thus, after the generation of each population or generation, the chromosomes of the generated population may be modified; for example, the chromosomes may be modified in order to satisfy desired constraints. For example, the resource requirement logic 152 may determine whether all resource requirements are satisfied. For this purpose the genetic algorithm logic 150 may generate a list of services which will be installed on each node and determine whether all the services may be installed based on an analysis of the available resources of the node. If it is not possible to install all of the services on the node, some genes of the chromosome may be set to zero, indicating that some services may not be installed on the node, so that the resource requirements may be satisfied.
The service composition logic 154 may include repairing the chromosomes based on a determination of whether the composition requirements are satisfied. For example, the composition requirements may specify that a service X must be installed in a same node as service Y. If the composition requirement is not satisfied for some services, the corresponding genes of the corresponding chromosome may also be set to zero.
The deployment coverage logic 156 may further evaluate the deployment coverage requirement. Thus, for example if there are too many instances of a particular service which will be installed according to a particular chromosome, a corresponding number of genes of the chromosome may be set to zero in order to avoid violating the deployment coverage requirement (e.g., by exceeding the number of allowed instances of the service), which may be included with the deployment constraints 134. Therefore, the repair process may ensure that each chromosome represents at least a partially feasible solution, as it is possible, for example, that too few instances of a service may be mapped to the network. In order to avoid this problem, the unfitness of all chromosomes may be determined by an unfitness function such that, if the unfitness of a chromosome equals zero, then the chromosome represents a feasible solution. For example, the unfitness function may be defined as the difference between the number of allowed instances and the actual number of instances to be installed, such that an unfitness value of zero indicates an optimal solution with regard to the deployment coverage requirement regarding the number of instances allowed to be installed.
As shown in FIG. 1, the service mapper 126 may include software to be executed, in whole or in part, on a computer 162, such as a personal computer, workstation, or on any suitable computing device. For example, a user or administrator may install some or all of the service mapper 126 software onto the computer 162, and may interact with the service mapper 126 software using a graphical user interface (GUI) viewed on an associated display. In another example, some or all of the service mapper 126 may be installed on a remote computer, over a wide area network such as the Internet, and the user may access the service mapper 126 over the network, e.g., as a web-based graphical user interface.
For instance, such GUIs, whether local or web-based, may include fields or other input/output techniques that allow the user to set the deployment constraints 134, alter the service metadata 124, or develop/modify and/or register a service executable 122 with the service repository 120. The user also may use the GUI, or another suitable user interface(s) to, for example, initiate a service mapping (such as selecting a service and/or sensor network for a desired mapping), or to set parameters associated with the service mapper 126.
The service mapper 126 may be in communication with business processes executing in whole or in part on the computer 162, or executing on a remote computer and/or network. For example, the business processes may be located at a corporate headquarters, and the sensor network 102 may represent one of many (types of) networks that may be dispersed across a large geographical region connected by a wide area network.
Thus, any or all of the back-end business processes, the service repository 120, the network monitor 128, the service injector 136, or the sensor network 102, may be dispersed from one another across a relatively large geographical area that is connected by a wide area network, which may include, for example, the Internet or an enterprise-wide proprietary network. The service repository 120, the deployment constraints 134, the service injector 136, and the network monitor 128 may be installed in whole or in part on the computer 162, e.g., may be stored in a memory of the computer 162. For example, the network monitor 128 may include a server component, e.g., an application server, executing on the computer 162. At the same time, as referenced above, at least portions of, for example, the service mapper 126, the network monitor 128, and the service injector 136 may be stored/executed on a separate computing device, including, for example, a portable computing device (e.g., a laptop computer or personal digital assistant (PDA)), or may be stored/executed on one or more of the devices 104, 106, 108, 110 of the sensor network 102.
Techniques for communication between the computer 162 (or other just-described examples or variations of the computer 162) with devices of the sensor network 102 may vary, for example, on the types of devices. For example, the devices and/or embedded systems may represent anything from small-scale, one-chip microcomputers, all the way to full-blown PC hardware. Thus, for example, for devices that have the capabilities of a mobile phone or more (e.g., are able to run a Java Virtual Machine™ or other middleware platform(s)), implementation may be performed in Java™ and/or based on the Open Services Gateway initiative (OSGi), which represents a known framework for implementing a component model for remote installation and management of applications and/or application components.
FIG. 2 is a flowchart 200 illustrating example operations of the system of FIG. 1. In FIG. 2, as referenced above, the associated processes and operations may be initiated or requested by users or business applications that wish to use particular (e.g., currently not running) services of the sensor network 102 (e.g., services registered with the service repository 120).
Thus, in FIG. 2, service metadata (202) is determined that, as described above, may include or reflect service requirements (e.g., processor type, available memory, or requested bandwidth) that potential devices should fulfill in order to be able to host a specified, associated service (e.g., to host the corresponding executable code component from the service executables 122 of the service repository 120). As described, at least some of these requirements may define an acceptable/tolerable range of a measurable property, such as, for example, available memory.
Similarly, deployment constraints may be collected (204), such as the deployment constraints 134 that may include, for example, more global constraints, such as an expected number of devices that are preferred or required to host the service in question (in other words, a desired coverage of the sensor network 102). That is, for example, although the service C 138 is illustrated in FIG. 1 as being deployed to the single device 104, it should be understood from the nature and possible uses of the sensor network 102 that, in many cases, instances of the service C 138 may be deployed to a plurality of the devices 104, 106, 108, 110 of the sensor network 102. In this way, for example, a service for detecting temperature (or other physical or environmental parameter) may be deployed over a sufficiently-wide physical area. As another example, multiple instances of the service B 116 may be deployed to different devices such as devices 104, 110, in order to obtain a desired level of redundancy of the system 100.
Generally, then, the service metadata 124 (and associated service requirements) and the deployment constraints 134 represent information that may be stored and accessed from an appropriate memory or data store. For example, service requirements and any corresponding data may be specified by a developer of the service component(s), and stored in a properly-formatted file or database that is available to the service mapper 126. For example, although FIG. 1 illustrates the service metadata 124 stored in the service repository 120, with the deployment constraints 134 stored separately, it should be understood that any suitable storage scheme(s) may be used; for example, the service metadata 124 and the deployment constraints 134 may be stored together (or in association with one another) in a memory associated with a general requirements data storage.
However stored, the service requirements and the deployment constraints 134, or other requirements, may be associated with a fulfillment priority, which may be designed to indicate the importance of each associated type of requirement. For instance, such a fulfillment priority may indicate that the usage of a certain processor type (e.g., the CPU 112) may be more important than a remaining memory (e.g., memory remaining in the memory 114) after the installation of the service C 138. As also referenced, such fulfillment priority information, as applied generally to services (and deployments thereof) of the sensor network 102, may be used, for example, in reducing the service requirements (within a range(s)), reconfiguring the sensor network 102, or removing service components from the sensor network 102.
Further in FIG. 2, a second type of basic input data includes information about currently-available capabilities of devices in the sensor network 102, or of the sensor network 102 itself. Accordingly, the device metadata 130 may be collected (206), which may include, for example, various static parameters (e.g., vendor name, CPU type, or list of installed/running service components), as well as various dynamically-changing parameters (e.g., remaining battery or memory) of one or more of the devices 104, 106, 108, 110 of the sensor network 102. Still further, the network metadata 132 may be collected (208), which may include, for example, information about the topology of the sensor network 102 (e.g., neighborhood relationships, or available bandwidth between devices).
As understood from the description of FIG. 1, the device metadata 130 and the network metadata 132 may be collected by the network monitor 128. For example, in one implementation, a monitoring process of the network monitor 128 may assume that the target devices 104, 106, 108, 110 have information regarding their capabilities and current status. For instance, the devices 104, 106, 108, 110 may store, continuously update (if required), and retrieve data relevant to monitoring. The network monitor 128 may either actively request relevant data from the devices 104, 106, 108, 110, and/or the devices 104, 106, 108, 110 may autonomously indicate changes in current configuration(s). For instance, the device 104 may include the service D 118, which may be part of, or associated with, the network monitor 128, and which may indicate if a battery status (or virtually any other parameter) of the device 104 reaches a pre-defined level, e.g., a level determined to be critically low.
Further, the sorted repair structures 144 may be determined (210), for example, by the service mapper 126 of FIG. 1, based on composition of services information. As understood from the description of FIG. 1, the sorted repair structures 144 may be determined, for example, based on a hierarchical ordering of atomic services and composite services such that the ordering includes a particular service in the ordering before any services that depend on the particular service, and based on, at least, for example, information stored in the service metadata 124 and network metadata 132.
Based on the above-described input data (202-210), and as understood from the description of FIG. 1, the service mapper 126 may execute at least the genetic algorithm logic 150 to determine a base generation (212) and to determine a derived generation (214) based on a result of the determined base generation (212). The service mapper 126, based on the determination of the derived generation (214), may then perform a mapping (216) of requested services to devices of the sensor network 102. Then, an output of the service mapping may include a set of instructions for performing code injection (218). Specifically, after successful mapping of service(s), the service injector 136 may be used to transfer executable service components to the respective selected devices. Depending on an available network infrastructure associated with the service network 102, the code injection may be performed, for instance, in a device-by-device fashion, in which the service injector 136 may send a message to the target node(s) containing appropriate commands, e.g., “remove the service B 116 and install the service C 138.” In this case, the appropriate service executable may be transmitted to the device 104 from the service repository 120.
Once a device receives a certain set of commands and services from the service injector 136, the service may be activated (220). Such activation may depend in part on the specific associated hardware platform associated with the device(s).
FIG. 3 is a block diagram illustrating an example service composition hierarchy 300 that may be utilized by the system of FIG. 1. According to the service composition hierarchy 300, a composite service A 160 of FIG. 3 may utilize the service B 116, and service C 138, which further utilizes the service D 118 and service E 158. The service B 116 may need to run on the same node as the service A 160 (i.e., locally), and the service C 138 may need to run on a neighbor node to the node of the service A 160. Further, the service D 118 may need to run on the same node as the service C 138, and the service E 158 may only need to run on the same network as the service C 138. Thus, for example, the service composition logic 154 of FIG. 1 may be configured to map composite service A 160 and atomic service B 116 to the device 110 of FIG. 1, additionally mapping the composite service C 138 and atomic service D 118 to the device 104, further mapping the atomic service E 158 to the device 108 of the sensor network 102, thus satisfying the composition requirements of service A 160 based on the service composition hierarchy 300.
FIG. 4 is a block diagram illustrating an example sorted services list 400 that may be utilized by the system of FIG. 1. The example sorted services list 400 shown in FIG. 4 is based on the example service composition hierarchy 300 of FIG. 3. The sorted services list 400 may be a list of services to be mapped to the network, for example, as a result of a request for a mapping of services. For example, if service A 460 is requested to be installed on/mapped to the network, then all of the services B 416, C 438, D 418, and E 458 from its composition should be installed. In the example the sorted services list 400 includes the five services A 460, B 416, C 438, D 418, and E 458. The list may then be sorted according to a composition tree such as the example service composition hierarchy 300 of FIG. 3. Thus, for example, as a result of the sorting, indicators of atomic services may be positioned at the beginning of the list, and indicators of other services may be positioned in the list according to the hierarchy in the composition tree. The example sorting may thus provide an ordering of services such that the service located at position j in the list does not need the service located at position i in the list, where 1<=j< the size of the list and j<i<=the size of the list.
For example, the sorted services list 400 may indicate services ordered according to a sequencing: D 418, E 458, B 416, C 438, A 460. Thus, the ordering may indicate that service D 418 does not need services E 458, B 416, C 438, A 460, service E 458 does not need services B 416, C 438, A 460, service B 416 does not need services C 438 and A 460, and service C 438 does not need service A 460. The sequencing of services in the list may thus facilitate a more efficient repair process as part of the genetic algorithm logic 150 of FIG. 1, discussed further with regard to FIGS. 6-9. More particularly, for example, by starting repair of a chromosome by considering the services according to the ordering, and stepping through a repair process considering each service according to the ordering indicated by the sorted services list 400, a repair performed on service j may not need to further consider an effect by the repair on services upon which the service j may depend, as those services may have already been considered for repair, according to the ordering.
FIG. 5 is a block diagram illustrating an example sorted repair structure 500 that may be utilized by the system of FIG. 1. However, the sorted repair structure 500 indicates an example network that includes 3 nodes, while the example sensor network 102 of FIG. 1 includes at least 4 nodes, or devices 104, 106, 108, 110. The example sorted repair structure 500 may be used for a high level pre-analysis of resource requirement satisfaction, e.g., by the genetic algorithm logic 150 of FIG. 1 in determining the base generation structures 146, as well as the derived generation structures 148. The example sorted repair structure 500 may be represented analogously to a potential solution to the mapping problem represented as a chromosome, which may be implemented, for example, as a string of binary values. The size of the chromosome may be determined as the number of nodes (n) of the sensor network 102 multiplied by the number of services (s) to be mapped. As shown, the example sorted repair structure 500 indicates 3 nodes included in a network, with 5 services requested to be installed, for example, services A 560, B 516, C 538, D 518, and E 558. Thus, the chromosome represented by FIG. 5 includes 15 genes, with each gene indicating whether a particular service is to be mapped to a particular node in the network.
Thus, according to the representation of FIG. 5, the first 3 genes of the chromosome may represent a mapping of a first service, the next 3 genes may represent a mapping of a second service, etc. Each gene of the chromosome may thus have a binary value, for example, if the gene has a value of 1, the corresponding service may be mapped to the associated node, else the corresponding service may not be mapped to the associated node. The size of the example repair structure 500 may correspond to the size of each one of the base generation structures 146, which also may include binary values. It is of course possible that other types of values may be used, for example, floating point, character, strings, lists, etc. Each value of the sorted repair structure 500 may thus indicate the installation of a respective service to a corresponding node in the network. Thus, a sorted repair structure 500 value of 1 may indicate that the respective represented service can be installed on the respective represented node (i.e., resource constraints may not be violated if the service is installed), and a value of 0 may indicate that the service cannot be installed on the node, for example, because either the node can not provide enough resources to support the service, or the service is already installed on the node.
The example sorted repair structure 500 may be based on the service metadata 124, device metadata 130, network metadata 132, and deployment constraints 134 of FIG. 1, the example sorted services list 400 of FIG. 4, and the example service composition hierarchy 300 of FIG. 3, for a sensor network including three devices such as the devices 104, 108, and 110 of FIG. 1, in an ordering 104, 110, 108. Thus, a request to map service A 160 to the sensor network 102 may result in the service mapper 126 initializing the sorted repair structure 500 to have a value “111 101 110 111 010” which indicates that service D 518 may be installed on all nodes (e.g., devices 104, 108, and 110), service E 558 may be installed on the first and third nodes (e.g., devices 104 and 108), service B 516 may be installed on the first and second node (e.g., devices 104 and 108), service C 538 may be installed on all nodes (e.g., devices 104, 108, and 110), and service A 560 may be installed on the second node (e.g., device 110).
The example sorted repair structure 500 as shown may not account for situations wherein several services may be installed on the same node. In the example, any one of services D 518, E 558, B 516, and C 538 may be installed separately on the first node according to the sorted repair structure 500, but the example sorted repair structure 500 may not indicate whether all of services D 518, E 558, B 516, and C 538 may be installed on the first node simultaneously.
FIG. 6 is a flowchart 600 illustrating additional example operations of the system 100 of FIG. 1. A list of services, e.g., the sorted services list 400 as discussed with regard to FIG. 4, to be mapped to the sensor network 102, may be determined (602), for example, as a result of a request for a mapping of services. For example, if service A 160 is to be installed/mapped to the network, then all of the services B 116, C 138, D 118, and E 158 from its composition may be installed. In this example, the sorted services list 400 may include indicators of the 5 services A 460, B 416, C 438, D 418, and E 458. The list may then be sorted, for example, according to a composition tree, e.g., the example service composition hierarchy 300. Thus, for example, as a result of the sorting, atomic services may be located at the beginning of the list, and other services may be located in the list in an ordering corresponding to the hierarchy in the composition tree. As understood from the description of FIG. 4, the sequencing of services in the list may thus facilitate more efficient repair of base generation structures 146 and derived generation structures 148 by the genetic algorithm logic 150 of FIG. 1.
A repair vector, e.g. the sorted repair structure 500 as discussed with regard to FIG. 5 may be determined (604) based on the service metadata 124, device metadata 130, network metadata 132, and deployment constraints 134 of FIG. 1, the example sorted services list 400 of FIG. 4 and the example service composition hierarchy 300 of FIG. 3.
Data structures (not shown) may be initialized for storing at least chromosomes and populations for determinations of the base generation structures 146 and derived generation structures 148.
The first population, e.g., the base generation structures 146, may be determined (606), e.g., by a random process according to genetic algorithm techniques, combined with a pre-analysis, high level, application of resource constraints, additionally determining whether a requested service may already be installed on the nodes of the sensor network 102, which may be accomplished based on the sorted repair structure 500, which may be applied to all chromosomes, e.g., the base generation structures 146, e.g., using a logical AND operation. The random generation of the population may further generate invalid and incomplete solutions of the mapping problem represented, e.g., as invalid chromosomes. As understood from the description of FIG. 1, after a population is generated, the invalid chromosomes may be repaired. Further, the incompleteness of solutions represented by the chromosomes, e.g., the base generation structures 146, may be determined based on an unfitness function.
The base generation structures 146, e.g., represented as base chromosomes, with invalid combinations may be repaired (608), as understood from the description of FIG. 1. After all base generation structures 146, e.g., base chromosomes, have been repaired, they may represent valid solutions, which may satisfy resource and composition constraints. Further, as understood from the description of FIG. 1, the repair process may provide that the deployment coverage of each service to be mapped is not violated by solutions represented by the repaired base generation structures 146. However, the base generation structures 146 or chromosomes may represent incomplete solutions, for example, as deployment coverage conditions may not be satisfied.
Therefore, the unfitness of each base generation structure 146 or chromosome may be determined (610), for example, by determining the difference between a desired deployment coverage (e.g., having a value of 10) and an actual chromosome based deployment coverage (e.g., having a value of 8), thus yielding an unfitness value (e.g., a value of 2) for the respective one of the base generation structures 146 or chromosomes. As understood from the description of FIG. 1, the desired deployment coverage may be determined, e.g., by the deployment coverage logic 156 of FIG. 1.
The derived generation structures 148 may be determined (612) based on a genetic algorithm selection technique which may be used to select the base generation structures 146 or chromosomes from which the next generation may be created, as discussed further with regard to FIG. 9. Chromosomes that may be determined to be “good” chromosomes, for example, chromosomes having a lower unfitness value according to an unfitness function, may be given a higher weight, and thus may be assigned a larger section of a roulette wheel selection scheme, thus leading to a higher probability that “good” chromosomes may be selected for the next generation, e.g., the derived generation structures 148. The roulette wheel analogy may correspond, for example, to a roulette wheel in which each candidate solution, or chromosome, represents a pocket on the wheel. The size of a pocket is proportionate to the probability of selection of the solution. Thus, selecting N chromosomes from a population, or generation, may be considered as equivalent to playing N games on the roulette wheel, as each candidate is drawn independently. For the example genetic algorithm that may be utilized by the genetic algorithm logic 150, the number of chromosomes in each of the base generation structures 146 and the derived generation structures 148 may be constant, although it is generally possible to vary the size of populations. Chromosomes or structures whose unfitness is smaller than an average unfitness of the population, or generation, may be ignored.
Modified derived generation structures 148 may be determined (614) based on applying genetic algorithm techniques, for example, including recombination, or crossover, techniques to the selected chromosomes. For example, two chromosomes may be selected from the population as parent chromosomes, as discussed further with regard to FIG. 9. As an example, a one point crossover technique may be used wherein a crossover point on the parent chromosome strings is selected. All data beyond that point in the chromosome string is swapped between the two parent chromosomes, and the resulting chromosomes may become the children of the parent chromosomes. As another example, a two point crossover technique may be used wherein two points are selected on the parent chromosome strings. All values between the two points are swapped between the parent chromosomes, rendering two child chromosomes.
As a further example, in accordance with a uniform crossover scheme, individual bits in chromosome strings may be compared between two parents. The bits may be swapped with a fixed probability (e.g., 0.5). As yet another example, in accordance with a half uniform crossover scheme, exactly half of the nonmatching bits may be swapped. Thus, first a Hamming distance (i.e., the number of differing bits) may be determined, for example, by applying an exclusive-OR operation on two chromosomes represented as bit strings, and adding the bits in the resulting bit string. The Hamming distance may be divided by two. The result may then indicate the number of the bits that do not match between the two parents that may be swapped.
Genetic algorithm mutation techniques may also be applied to the selected chromosomes by the genetic algorithm logic 150. For example, a mutation probability may be used to determine whether each bit in a chromosome is to be modified (e.g., set to a different value).
Each chromosome of the new population, e.g., each derived generation structure 148, may be repaired (616) based on a sorted repair structure 144, for example, by applying a logical AND function on the derived generation structure 148 and the sorted repair structure 144, and an unfitness value of each chromosome may be determined (618). For example, the unfitness value may be determined based on a fitness function, for example, based on resource requirements or on composition requirement unfitness.
The old base generation structures 146 may be replaced by the new derived generation structures 148, and steps 614-618 may be repeated until a predetermined maximum number of populations is generated. As each new generation is generated, a “best” structure or chromosome (e.g., having a smallest unfitness value) of that particular population may be stored so that when the predetermined maximum number of populations has been generated, the best chromosome, e.g., the chromosome having the smallest unfitness value may be determined resulting from all of the derived generation structures. If there are no chromosomes with an unfitness value of 0, which may represent a valid and complete solution of the mapping problem, the genetic algorithm logic 150 may be configured to attempt to complete the “best” chromosomes. Thus, an attempt may be made to install missing services on the network nodes via operations on the chromosomes, so that the deployment coverage constraints, for example, as included in the deployment constraints 134, may be satisfied. As a result, the “best” chromosome may be returned as a solution to the service mapping request.
FIG. 7 is a flowchart 700 illustrating example operations to repair base generation structures 146 having invalid combinations of services, for example, of the system 100 of FIG. 1. The chromosomes may be repaired successively for each service. As understood from the description of FIG. 1, because the services may be sorted, a repair of a service x may not influence the mapping of a service y for 1<=x<y, since service x may be repaired before service y.
After determining a chromosome, e.g., one of the base generation structures 146, for repair, and after initializing index values i and j to have values of 1, a service i of the chromosome may be determined (702) for repair analysis, and node j and a corresponding gene, or bit may be determined (704) from a node list, e.g., a node list of nodes in the network. If the gene has a value of 1, a determination may be made (706) of which services need to be installed on device, or node j, according to the chromosome values. A gene having a value of 1 may indicate that the service corresponding to the gene's position in the chromosome may need to be installed on the node corresponding to the gene's position on the chromosome. For example, a gene having a value of 1 that is located on the chromosome in a position corresponding to service D 518 and node, or device 104 may indicate that the service D 118 is to be installed on the device 104 of FIG. 1.
It may then be determined (708) whether the device, or node j satisfies resource and composition requirements for the installation of the service i on node j. For each device, or node in the network, the chromosome may be analyzed regarding the resource constraints, including determining which services are currently to be installed on which device or node, determining all resource constraints for all services which are to be installed on each device or node. If the resource constraints are not met, then services may be removed from the chromosome by setting corresponding genes to a value of zero. For each service, the chromosome may be analyzed regarding the service composition for the service, for example, by the service composition logic 154 based at least on the sorted services list 400 of FIG. 4.
For each service, sub-services may be determined, a determination may be made whether the sub-services are already installed on the device or node, and if so, the service may be installed on the device or node; if not, it may be determined whether the current chromosome indicates installation of all required sub-services on the respective device or node (where required). Since services may be sorted according their hierarchy in composition, e.g., according to the sorted services list 400 of FIG. 4, the determination may be straightforward. If it is not possible to install the sub-services, the service may be removed from the chromosome, e.g., by setting the gene corresponding to the service for the respective device or node to a value of zero. Further explanation is provided with regard to FIG. 8.
The number of service instances indicated to be installed may be determined (710), the number of service instances required to be installed may be determined (712), and the two results may be compared. If the number of service instances to be installed and the number of service instances already installed exceeds the required number, the excessive service mappings may be removed (714) from the chromosome, e.g., by setting genes corresponding to the excess service mappings to a value of zero. The index j may be incremented (716) by 1 for consideration of services for the next node or device according to the node list, until all network nodes have been considered for service i, for example, by repeating steps 704-716 until all nodes have been considered. Thus, it may then be determined whether j is equal to the number of nodes in the network (718), and if not, control returns to 704. If all services to be mapped have been considered, e.g., by determining whether the index i meets the number of services (720), then the repair may end; else the index i may be incremented by 1 (722) and steps 702-722 may be repeated until the index i indicates that all services have been analyzed for repair.
FIG. 8 is a flowchart 800 illustrating example operations, for example, to repair base generation structures 146 and derived generation structures 148 based on resources and composition, for example, of the example system 100 of FIG. 1, and as further explanation of steps 708-712 of FIG. 7. It is noted that the example steps discussed herein regarding the repair of the structures involve an ordering of the services as established based, for example, on the sorted services list 400 discussed previously with regard to FIG. 4. Thus, as each service i is considered in turn for repair, it may be assumed that all services on which service i may depend, have been previously considered for repair, and thus there may be no need to reconsider all services included in a composition.
As explanation of an example repair process, a part of a chromosome that installs service i may be determined (802). Index j may be set to a value of 1. Thus, a gene j of the chromosome part that indicates whether service i is to be installed on device or node j may be determined (804). The service i may be added to a list of services to be installed on node j based on the current chromosome (806). It may then be determined (808) whether node j provides sufficient resources to host all resources on the list of services to be installed on node j. This determination may be performed, for example, by the resource requirement logic 152 based at least on the service metadata 124 and the network metadata 132. Additionally, the determination may be based on the deployment constraints 134 or the allowable deployment condition 142.
If it is determined (808) that node j does not provide sufficient resources to host all resources on the list of services to be installed on node j, the corresponding gene may be set to a value of zero (814), the index j may be incremented by a value of 1 (816), and control may pass to step 804 if j does not exceed the size of the network (818); else the repaired part of the chromosome may be returned (820). If node j provides sufficient resources (808), then it may be determined (810) whether the composition requirements of service i are satisfied by node j based on a current network status. This determination may be performed, for example, by the service composition logic 154 based at least on the sorted services list 400, the sorted repair structure 500, the service metadata 124 and the network metadata 132. Additionally, the determination may be based on the deployment constraints 134 or the allowable deployment condition 142.
If it is determined (810) that the composition requirements of service i are satisfied by node j based on a current network status, the index j may be incremented by 1 (816), and control may pass to step 804 if j does not exceed the size of the network (818); else the repaired part of the chromosome may be returned (820). If it is determined (810) that the composition requirements of service i are not satisfied by node j based on a current network status, it may be determined (812) whether the composition requirements of service i are satisfied by node j based on a current chromosome status. If it is determined (812) that the composition requirements of service i are not satisfied by node j based on the current chromosome status, the corresponding gene may be set to a value of zero (814), the index j may be incremented by a value of 1 (816), and control may pass to step 804 if j does not exceed the size of the network (818); else the repaired part of the chromosome may be returned (820).
If it is determined (812) that the composition requirements of service i are satisfied by node j based on the current chromosome status, the index j may be incremented by 1 (816), and control may pass to step 804 if j does not exceed the size of the network (818); else the repaired part of the chromosome may be returned (820). The repair technique may ensure that the deployment coverage is not exceeded (for each service), for example, via the deployment coverage logic 156. For example, if there are too many instances of a particular service for a chromosome, the service instances may be removed from the chromosome, for example, by setting the corresponding genes of the chromosome to a value of 0. These genes may be selected randomly, or they may, for example, be selected in accordance with a priority of services for removal.
FIG. 9 is a flowchart 900 illustrating example operations to select base generation structures 146 for inclusion in the derived generation structures 148 of the system 100 of FIG. 1, as discussed with regard to step 614 of FIG. 6. An average unfitness value may be determined (902) based on unfitness values determined for all chromosomes in the base population, e.g., the base generation structures 146. For example, the unfitness values of each chromosome, or structure in the base generation structures 146 may be added together, and the resulting sum may be divided by the total number of chromosomes or structures in the population, to determine the average unfitness value. As noted previously, chromosomes having smaller unfitness values may indicate better solutions to the mapping problem, e.g., better mappings for the requested services.
A roulette wheel may be determined (904) such that services associated with smaller unfitness values may be associated with more sections of the roulette wheel than other services. Thus, the better chromosomes may have a higher probability of being selected for participation in the next generation, for example, the next derived generation structures 148. Index i may be set to a value of 1 (906). A chromosome i may be determined based on roulette (908). If i is equal to a predetermined size of the derived population (910), e.g., the number of structures in the derived generation structures 148, then the derived population is returned (914) as the new derived generation, e.g., the derived generation structures 148; if not, the index i is incremented (912) by a value of 1 and control returns to step 908. As discussed previously, the genetic algorithm techniques of crossover or recombination and mutation may be applied to resulting chromosomes.
It is also possible to generate an optimal or sub-optimal solution of the mapping problem. In order to generate such a solution, the fitness of each chromosome with regard to predefined goals may be determined. When processing is complete, a most feasible solution, which may have a smallest unfitness value and a largest fitness value, is returned.
As described herein, service-to-device mapping algorithms based on genetic algorithm techniques enable the automatic intelligent mapping of services to appropriate devices, e.g., smart item devices, so that the services may thereafter be deployed thereto. The genetic algorithm techniques use constraint information in determining initial populations and derived populations and consider composite services information in determining the populations based on a sorted repair structure. Accordingly, a desired service deployment may be obtained in an easy, reliable manner, and a functionality of the sensor network may be made more flexible and more predictable. Techniques described herein are not limited to service-to-device mapping, and may be used for other applications, e.g., in grid computing.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6016499Jul 21, 1997Jan 18, 2000Novell, Inc.System and method for accessing a directory services respositoryUS6138162Feb 11, 1997Oct 24, 2000Pointcast, Inc.Method and apparatus for configuring a client to redirect requests to a caching proxy server based on a category ID with the requestUS6189038Nov 18, 1999Feb 13, 2001Hewlett-Packard CompanyGeneric notifications framework system and method for enhancing operation of a management station on a networkUS6226788Jul 22, 1998May 1, 2001Cisco Technology, Inc.Extensible network management systemUS6292856Jan 29, 1999Sep 18, 2001International Business Machines CorporationSystem and method for application influence of I/O service order post I/O requestUS6363411Oct 19, 1999Mar 26, 2002Mci Worldcom, Inc.Intelligent networkUS6378128 *Oct 8, 1998Apr 23, 2002Microsoft CorporationSystem and method for dynamically modifying an install-setUS6460082 *Jun 17, 1999Oct 1, 2002International Business Machines CorporationManagement of service-oriented resources across heterogeneous media servers using homogenous service units and service signatures to configure the media serversUS6480977Oct 29, 1999Nov 12, 2002Worldcom, Inc.Multi-protocol monitorUS6785707Jun 21, 2001Aug 31, 2004Bitfone Corp.Enhanced multimedia mobile content delivery and message system using cache managementUS6816862Jan 17, 2002Nov 9, 2004Tiax LlcSystem for and method of relational database modeling of ad hoc distributed sensor networksUS6832373Apr 1, 2003Dec 14, 2004Bitfone CorporationSystem and method for updating and distributing informationUS6847974Jul 25, 2001Jan 25, 2005Us Search.Com IncMethod and apparatus for intelligent data assimilationUS6859831Oct 4, 2000Feb 22, 2005Sensoria CorporationMethod and apparatus for internetworked wireless integrated network sensor (WINS) nodesUS6891823Jun 15, 1999May 10, 2005Pluris, Inc.Apparatus and method for scaling a switching fabric in a network switching nodeUS6980993Mar 14, 2002Dec 27, 2005Microsoft CorporationSchemas for a notification platform and related information servicesUS6990660Sep 20, 2001Jan 24, 2006Patchlink CorporationNon-invasive automatic offsite patch fingerprinting and updating system and methodUS7072960Jun 10, 2002Jul 4, 2006Hewlett-Packard Development Company, L.P.Generating automated mappings of service demands to server capacities in a distributed computer systemUS7075960Jan 9, 2004Jul 11, 2006Matsushita Electric Industrial Co., Ltd.Semiconductor laser apparatus and production method thereofUS7099582May 31, 2002Aug 29, 2006Lucent Technologies Inc.Method and apparatus for multi-protocol and multi-rate optical channel performance monitoringUS7099946Nov 13, 2001Aug 29, 2006Canon Kabushiki KaishsaTransferring a media browsing session from one device to a second device by transferring a session identifier and a session key to the second deviceUS7114146May 2, 2003Sep 26, 2006International Business Machines CorporationSystem and method of dynamic service composition for business process outsourcingUS7130773Nov 30, 2004Oct 31, 2006Sun Microsystems, Inc.Method and apparatus for processing data using objectsUS7152019Apr 4, 2005Dec 19, 2006Oracle International CorporationSystems and methods for sensor-based computingUS7171471Aug 15, 2002Jan 30, 2007Cisco Technology, Inc.Methods and apparatus for directing a resource requestUS7206289Jan 31, 2002Apr 17, 2007Oki Electric Industry Co., Ltd.Method of and apparatus for calculating traffic from data on packet transmission collected from routersUS7237243Feb 14, 2002Jun 26, 2007Microsoft CorporationMultiple device management method and systemUS7286158Dec 22, 1999Oct 23, 2007Axcess International Inc.Method and system for providing integrated remote monitoring servicesUS7304976Jan 31, 2005Dec 4, 2007Virginia Tech Intellectual Properties, Inc.Method and apparatus for control and routing of wireless sensor networksUS7313467Mar 31, 2006Dec 25, 2007Automotive Technologies International Inc.System and method for in-vehicle communicationsUS7557707May 31, 2005Jul 7, 2009Microsoft CorporationRFID enabled information systems utilizing a business applicationUS20020007422Jun 28, 2001Jan 17, 2002Bennett Keith E.Providing equipment access to supply chain membersUS20020100036Sep 20, 2001Jul 25, 2002Patchlink.Com CorporationNon-invasive automatic offsite patch fingerprinting and updating system and methodUS20020161751Jan 17, 2002Oct 31, 2002Mulgund Sandeep S.System for and method of relational database modeling of ad hoc distributed sensor networksUS20020184103 *May 31, 2001Dec 5, 2002Safwan ShahActive transaction generation, processing, and routing systemUS20030078946Jun 5, 2002Apr 24, 2003Laurie CostelloClustered filesystemUS20030097443Nov 21, 2001May 22, 2003Richard GillettSystems and methods for delivering content over a networkUS20030217186May 16, 2002Nov 20, 2003Bushey Robert D.Apparatus for and method of seamless wireless multimedia download path to peer networked appliancesUS20040121792Dec 18, 2002Jun 24, 2004Allen Vernon A.Multi-protocol network and method of switching protocolsUS20040166807Feb 20, 2003Aug 26, 2004Petri VesikiviApparatus, system, method and computer program product for implementing an automatic identification system with a personal communication device to improve functionalityUS20040181541Feb 24, 2004Sep 16, 2004Computer Associates Think, Inc.Relational model for management information in network devicesUS20040220910 *May 2, 2003Nov 4, 2004Liang-Jie ZangSystem and method of dynamic service composition for business process outsourcingUS20040250113Apr 16, 2003Dec 9, 2004Silicon Graphics, Inc.Clustered filesystem for mix of trusted and untrusted nodesUS20050047545May 20, 2002Mar 3, 2005Paolo BenedettiNon-destructive process for continuously measuring the density profile of panelsUS20050060365Jan 24, 2002Mar 17, 2005Robinson Scott L.Context-based information processingUS20050198228Feb 10, 2005Sep 8, 2005Bajwa Raminder S.Radio frequency identification (RFID) network system and methodUS20050228763Apr 2, 2005Oct 13, 2005Altusys CorpMethod and Apparatus for Situation-Based ManagementUS20050235058Oct 8, 2004Oct 20, 2005Phil RackusMulti-network monitoring architectureUS20060022801Jul 29, 2005Feb 2, 2006Reva Systems CorporationRFID tag data acquisition systemUS20060029054Apr 14, 2005Feb 9, 2006International Business Machines CorporationSystem and method for modeling and dynamically deploying services into a distributed networking architectureUS20060052882Dec 23, 2004Mar 9, 2006Uwe KubachReal-time monitoring using sensor networksUS20060074912Sep 28, 2004Apr 6, 2006Veritas Operating CorporationSystem and method for determining file system content relevanceUS20060085798Oct 4, 2005Apr 20, 2006Bristol Technology Inc.Method and apparatus for correlation of events in a distributed multi-system computing environmentUS20060161909 *Jan 19, 2006Jul 20, 2006Raju PandeySynthesizing a scalable and incrementally updatable system software infrastructure for sensor networksUS20060206582May 3, 2006Sep 14, 2006David FinnPortable music device with song tag captureUS20060212453Mar 18, 2005Sep 21, 2006International Business Machines CorporationSystem and method for preserving state for a cluster of data servers in the presence of load-balancing, failover, and fail-back eventsUS20060235976Apr 14, 2005Oct 19, 2006Ying ChenMethod and apparatus for metadata driven web service mediationUS20060265661 *May 20, 2005Nov 23, 2006Microsoft CorporationDevice metadataUS20060277079Apr 20, 2006Dec 7, 2006Gilligan Geffrey DGroupware travel itinerary creationUS20070032244Aug 8, 2005Feb 8, 2007Microsoft CorporationGroup-centric location tagging for mobile devicesUS20070112574Aug 5, 2004May 17, 2007Greene William SSystem and method for use of mobile policy agents and local services, within a geographically distributed service grid, to provide greater security via local intelligence and life-cycle management for RFlD tagged itemsUS20070118496Nov 21, 2005May 24, 2007Christof BornhoevdService-to-device mapping for smart itemsUS20070118549Jun 30, 2006May 24, 2007Christof BornhoevdHierarchical, multi-tiered mapping and monitoring architecture for smart itemsUS20070118560 *Nov 21, 2005May 24, 2007Christof BornhoevdService-to-device re-mapping for smart itemsUS20070130208Oct 18, 2006Jun 7, 2007Christof BornhoevdHierarchical, multi-tiered mapping and monitoring architecture for service-to-device re-mapping for smart itemsUS20070168925Dec 1, 2005Jul 19, 2007Christof BornhoevdComposition model and composition validation algorithm for ubiquitous computing applicationsUS20070233881Mar 31, 2006Oct 4, 2007Zoltan NochtaActive intervention in service-to-device mapping for smart itemsUS20070276619Dec 28, 2004Nov 29, 2007Great American Lines, Inc.Container inspection systemUS20070282746May 12, 2006Dec 6, 2007Juergen AnkeDistributing relocatable services in middleware for smart itemsUS20070282988May 31, 2006Dec 6, 2007Christof BornhoevdDevice registration in a hierarchical monitor serviceUS20070283001May 31, 2006Dec 6, 2007Patrik SpiessSystem monitor for networks of nodesUS20070283002May 31, 2006Dec 6, 2007Christof BornhoevdModular monitor service for smart item monitoringUS20080010284Apr 16, 2007Jan 10, 2008Silicon Graphics, Inc.Snapshot copy of data volume during data accessUS20080033785Jul 31, 2006Feb 7, 2008Juergen AnkeCost-based deployment of components in smart item environmentsUS20080306798Jun 5, 2007Dec 11, 2008Juergen AnkeDeployment planning of components in heterogeneous environmentsUS20090097397Oct 12, 2007Apr 16, 2009Sap AgFault tolerance framework for networks of nodesEP0697654A1Jul 17, 1995Feb 21, 1996Canon Kabushiki KaishaLoad distribution method and systemEP0810755A2Jan 16, 1997Dec 3, 1997Hewlett-Packard CompanyMethod for enhancing operation of a network management systemEP1372073A2May 21, 2003Dec 17, 2003Hewlett-Packard CompanyMapping service demands in a distributed computer systemEP1788480A2Nov 8, 2006May 23, 2007Sap AgHierarchical, multi-tiered mapping and monitoring architecture for smart itemsEP1863223A1May 30, 2007Dec 5, 2007Sap AgSystem monitor for networks of nodesEP1892656A1Jul 26, 2007Feb 27, 2008Sap AgCost-based deployment of components in smart item environmentsWO2005106666A1Feb 17, 2005Nov 10, 2005International Business Machines CorporationA system and method for modeling and dynamically deploying services into a distributed networking architecture* Cited by examinerNon-Patent CitationsReference1"Java Native Interface (JNI)", Wikepedia, the free encyclopedia, Retrieved on Dec. 20, 2005, from http://en.wikipedia.org/wiki/Jini, 6 pages.2"OSGI Service Platform", Release 3, IOS Press, Mar. 2003, 602 pages.3"Service Location Protocol (SLP)", Wikepedia, the free encyclopedia, Retrieved on Dec. 20, 2005, from http://en.wikipedia.org/wiki/Service-Location-Protocol, 1 page.4"Universal Plug and Play (UPnP)", Wikepedia, the free encyclopedia, Retrieved on Dec. 20, 2005, from http://en.wikipedia.org/wiki/Universal-Plug-and-Play, 6 pages.5"UPnP Device Architecture 1.0", UPnP Forum, 1999, 80 pages.6"Composite Capability/Preference Profiles (CC/PP): Structure and Vocabularies 1.0", W3C Recommendation (Jan. 15, 2004), pp. 1-78.7"FAQ: Fault management—How does Fault Management Work?" GoAhead Software (2000), 9 pgs.8"FIPA Device Ontology Specification", Foundation for Intelligent Physical Agents (Apr. 9, 2001), pp. 1-15.9"MVP Brochure", Biffone Corporation (2005), www.biffone.com/usa/uploads/mvp.brochure (Retrieved Sep. 20, 2005), pp. 1-3.10"Service Location Protocol (SLP)", Wikepedia, the free encyclopedia, Retrieved on Dec. 20, 2005, from http://en.wikipedia.org/wiki/Service—Location—Protocol, 1 page.11"The OSGi Service Platform- Dynamic services for networked devices", Retrieved Nov. 16, 2005 from http://www.osgi.org/osgi—technology/index.asp?section=2, 5 pgs.12"TINYOS: Mission Statement", Retrieved Nov. 16, 2005 from http://www.tinyos.net/special/mission, 2 pgs.13"Universal Plug and Play (UPnP)", Wikepedia, the free encyclopedia, Retrieved on Dec. 20, 2005, from http://en.wikipedia.org/wiki/Universal—Plug—and—Play, 6 pages.14Advisory Action for U.S. Appl. No. 11/284,195, mailed Oct. 9, 2008, 4 pages.15Advisory Action mailed Oct. 9, 2008 for U.S. Appl. No. 11/284,195, 4 pgs.16Akehurst, D H., et al., "Design Support for Distributed Systems: DSE4DS", Procedings of the 7th Cabernet Radicals Workshop (Oct. 2002), pp. 1-6.17Anke, J. et al., "A Planning Method for Component Placement in Smart Item Environments Using Heuristic Search", Proceedings of the 7th IFIP WG 6.1 International Conference, Distributed Applications and Interoperable Systems, Jun. 2007, pp. 309-322.18Anke, J. et al., "A Service-Oriented Middleware for Integration and Management of Heterogeneous Smart Items Environments", Proceedings of the 4th MiNEMA Workshop, July 2006, pp. 7-11.19Anke, J. et al., "Cost-based Deployment Planning for Components in Smart Item Environments", IEEE Conference on Emerging Technologies and Factory Automation, Sep. 2006, pp. 1238-1245.20Anke, J. et al., "Early Data Processing in Smart Item Environments Using Mobile Services", Proceedings of the 12th IFAC Symposium on Information Control Problems in Manufacturing—INCOM, (May 19, 2006), pp. 823-828.21Ardaiz, et al, "On Service Deployment in Ubiquitous Computing", Proceedings of the 2nd International Workshop on Ubiquitous Computing and Communications, Sep. 2001, 7 pages.22Arkin, et al, "Web Service Choreography Interface (WSCI) Version 1.0", W3C Note, Aug. 2002, 84 pages.23Arkin, et al, "Web Services Business Process Execution Language Version 2.0", Committee Draft, Sep. 2005, 81 pages.24Baker, M. et al., "Grids and Grid Technologies for wide-area Distributed Computing", Software-Practice & Experience (Sep. 27, 2002), pp. 1437-1466.25Baker, M. et al., "Grids and Grid Technologies for wide-area Distributed Computing", Software—Practice & Experience (Sep. 27, 2002), pp. 1437-1466.26Bandara, Ayomi et al., "An Ontological Framework for Semantic Description of Devices", Nov. 11, 2004, 2 pgs.27Basile, Claudio et al., "A Survey of Dependability Issues in Mobile Wireless Networks", Technical Report, LAAS CNRS Toulouse (Feb. 21, 2003), pp. 1-45.28Bellavista, Paolo et al., "The Ubiquitous Provisioning of Internet Services to Portable Devices", Pervasive Computing, Jul. 2002, pp. 81-87.29Benatallah, B., "Facilitating the Rapid Development and Scalable Orchestration of Composite Web Services", 2005 Springer Science + Business Media, Inc., pp. 1-33.30Bitkom, "RFID White Paper Technology, Systems and Applications", An Overview for companies seeking to use RFID technology to connect their IT systems directly to the "real" world, Dec. 2005, 50 pgs.31Bohn, et al, "SIRENA-Service Infrastructure for Real-time Embedded Networked Devices: A service oriented framework for different domains", International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies, 2006, 6 pages.32Bohn, et al, "SIRENA—Service Infrastructure for Real-time Embedded Networked Devices: A service oriented framework for different domains", International Conference on Networking, International Conference on Systems and International Conference on Mobile Communications and Learning Technologies, 2006, 6 pages.33Bornhoevd, C. et al., "Integrating Smart Items with Business Processes an Experience Report", IEEE Proceedings of the 38th Hawaii International Conference on System Sciences (Jan. 3, 2005), pp. 1-8.34Bornhoevd, Christof et al., "Integrating Automatic Data Acquisition with Business Processes Experiences with SAPs Auto-ID Infrastructure", Very Large Data Conference (Sep. 3, 2004), pp. 1-8.35Boudec, Jean-Yves L., et al., "A Theory of Deterministic Queuing Systems for the Internet", Network Calculus, Online Version of the Book Springer Verlag—LNCS 2050, (May 10, 2004), pp. 1-269.36Box, et al, "Web Services Eventing (WS-Eventing)", Aug. 2004, 16 pages.37Buchholz, S. et al., "Adaptation-Aware Web Caching: Caching in the Future Pervasive Web", In: KiVS, (2003), pp. 55-66.38Buschmann, C et al., "Towards Information Centric Application Development for Wireless Sensor Networks", In Proceedings of the System Support for Ubiquitous Computing Workshop (UbiSys) at the Sixth Annual Conference on Ubiquitous Computing (UbiComp 2004), pp. 1-12.39California Software Laboratories, "White Paper: The JetSend Appliance Architecture", retrieved from http://www.calsoftlabs.com/whitepapers/jetsend-architecture.html, 2002, 28 pages.40Carvalho, H et al., "A General Data Fusion Architecture", Proceedings of the 6th International Conference on Information Fusion (Jul. 2003), pp. 1-8.41Carzaniga, Antonio et al., "Designing distributed applications with mobile code paradigms", In: Proceedings of the 19th International Conference on Software Engineering, Boston, Massachusetts, (1997), pp. 22-32.42Casati, F., et al "Specification and Implementation of Exceptions in Workflow Management Systems", ACM Transactions on Database Systems, vol. 24, No. 3, Sep. 1993, pp. 405-451.43Chackrabarti, et al, "Securing the Pharmaceutical Supply Chain", Technical Report, Auto-ID Centre Institute for Manufacturing, University of Cambridge, Jun. 1, 2003, 19 pages.44Chandra, Bharat et al., "Resource management for scalable disconnected access to web services", WWW '01: Proceedings of the 10th International Conference on World Wide Web (May 5, 2001), pp. 245-256.45Chatterjee, Mainak et al., "WCA: A Weighted Clustering Alogrithm for Mobile Ad Hoc Networks", Cluster Computing 5, Klluwer Academic Publishers, 2002, pp. 193-204.46Christensen, et al, "Web Services Description Language (WSDL) 1.1", W3C Note, Mar. 2001, 27 pages.47Clement, et al, "UDDI version 3.2, UDDI Spec Technical Committee Draft, OASIS, UDDI Spec TC", Oct. 2004, 420 pages.48Colt, Charles et al., "Oracle Â® Collaboration Suite, Deployment Guide10g Release 1 (10.1.1) B14479-02", (Oct. 2005), pp. 1-230.49Crossbow, "Stargate: X-Scale Processor Platform SPB 400", retrieved on Dec. 20, 2005 from http://www.xbow.com/Products/productsdetails.aspx?sid=63, 2 pages.50Crossbow, "Wireless Sensor Networks: Sensor and Data-Acquisition Boards", retrieved on Apr. 24, 2005 from http://www.xbow.com/Products/productsdetails.aspx?sid=63, 1 page.51Davenport, "Process Innovation: Reengineering work through information technology", Harvard Business School Press, 1993, 6 pages.52de Sales, et al, "Towards the UPnP-UP: Enabling User Profile to Support Customized Services in UPnP Networks", Proceedings of the 2008 The Second International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, 2008, pp. 206-211.53Decasper, D. et al., "Router Plugins: A Software Architecture for Next Generation Routers", Computer Communication Review (Oct. 1998), pp. 229-240.54Decker, et al, "CoBls Platform Survey and State-of-the-Art Sensor Platforms", CoBls Deliverable Report, Aug. 2005, 51 pages.55Deering, "Hinden. Internet Protocol, Version 6 (Ipv6) Specification. Request for Comments RFC 2460", Internet Engineering Task Force, 1998, 39 pages.56Deering, S. et al., "ICMP Router Discovery Messages", IETF Standard, Internet Engineering Task Force (Sep. 1991), pp. 1-19.57Domagalski, Ronald et al., "Moglichkeiten der Anfragebearbeitung in mobilen Ad-hoc-Netzwerken", English Title: Possibilties of Query Processing in Mobile Ad Hoc Networks, Contribution to the Workshop "Applications of Mobile Information Technology", Heidelburg German, Full length English translation included, Mar. 23-24, 2004, 12 pages.58ETSI, "Selection procedures for the choice of radio transmission technologies of the UMTS", Universal Mobile Telecommunications System 30.03 version 3.2.0 (Apr. 1998), pp. 1-84.59European Search Report for Application No. 07010671.1 mailed on Nov. 16, 2007, 4 pgs.60European Search Report for Application No. EP06023720.3, mailed Apr. 10, 2007, pp. 1-4.61European Search Report for Application No. EP07005127.1, mailed Jul. 20, 2007, pp. 1-3.62European Search Report for Application No. EP07008409.0, mailed Aug. 24, 2007, pp. 1-4.63European Search Report for Application No. EP07009428.9, mailed Oct. 4, 2007, pp. 1-4.64European Search Report for Application No. EP07014724.4, mailed Nov. 27, 2007, pp. 1-4.65European Search Report for EP Application No. 07010652.1 mailed on Oct. 26, 2007, 3 pgs.66European Search Report for EP Application No. 07010654.7 mailed on Oct. 5, 2007, 4 pgs.67European Search Report for U.S. Appl. No. EP06023256.8, mailed May 9, 2007, pp. 1-5.68Extended European Search Report for Application No. 08017795.9, mailed Feb. 10, 2009, 11 pgs.69Ferreira, L. et al., "Introduction to Grid Computing with globus", IBM International Technical Support Organization, 2nd edition (Sep. 2003), pp. 1-58.70Final Office Action for U.S. Appl. No. 11/284,195, mailed Jun. 25, 2008, 31 pages.71Final Office Action for U.S. Appl. No. 11/396,299, mailed Jan. 28, 2010, 54 pages.72Final Office Action for U.S. Appl. No. 11/444,119, mailed Aug. 24, 2010, 28 pages.73Final Office Action for U.S. Appl. No. 11/479,284, mailed Jun. 11, 2009, 4 pages.74Final Office Action mailed Feb. 23, 2009 for U.S. Appl. No. 11/479,284, 29 pgs.75Final Office Action mailed Jun. 25, 2008 for U.S. Appl. No. 11/284,195, 31 pgs.76Final Office Action mailed May 13, 2009 for U.S. Appl. No. 11/283,618, 32 pgs.77Foster, I. et al., "The Open Grid Services Architecture, Version 1.0", Informational Document, Global Frid Forum (Jan. 29, 2005), pp. 1-62.78Foster, I. et al., "Globus: A Metacomputing Infrastructure Toolkit", The International Journal of Supercomputer Application and High performance Computing, MIT Press, US, 11 (2), (Jun. 21, 1997), pp. 115-128.79Fredriksson, Johan et al., "Calculating Resource Trade-offs when Mapping Component Services to Real-Time Tasks", Fourth Conference on Software Engineering Research and Practice (Oct. 2004), pp. 1-8.80Gao, T., et al "Toward QoS Analysis of Adaptive Service-Oriented Architecture", Service-Oriented System Engineering, IEEE International Workshop (Oct. 20, 2005), pp. 1-8.81Geller, et al, "Web Services Eventing (WS-Eventing)", Aug. 2004, 38 pages.82Golatowski, F et al., "Service-Oriented Software Architecture for Sensor Networks", International Workshop on Mobile Computing (Jun. 17-18, 2003), pp. 1-8.83Gounaris, Anastasios et al., "Adaptive Query Processing: A Survey", Lecture Notes in Computer Science, vol. 2405, Archive of Proceedings of the 19th British National Conference on Databases: Advances in Databases, 2002, pp. 11-25.84Graupner, S. et al., "A framework for analyzing and organizing complex systems", Proceedings of Seventh IEEE International Conference on Engineering of Complex Computer Systems, Jun. 11-13, 2001, Piscataway, NJ, USA, (Jun. 11, 2001), pp. 155-165.85Greenstein, Ben et al., "A Sensor Network Application Construction Kit (SNACK)", SenSys '04, Nov. 3-5, 2004, 12 pages.86Gudgin, et al, "SOAP Message Transmission Optimization Mechanism", Jan. 25, 2005, 15 pages.87Guttman, "Service Location Protocol", Version 2, Jun. 1999, 55 pages.88Haas, "Service Deployment in Programmable Networks", PhD Thesis, ETH Zurich, Switzerland, 2003, 253 pages.89Hammer, et al, "Reengineering the Corporation-A Manifesto for Business Revolution", Nicholas Brealey Publishing, May 1994, 14 pages.90Hammer, et al, "Reengineering the Corporation—A Manifesto for Business Revolution", Nicholas Brealey Publishing, May 1994, 14 pages.91Han, et al, "Sensor Network Software Update Management: A Survey", Journal of Network Management, 2005, 26 pages.92Hasiotis, T., et al., "Sensation: A Middleware Integration Platform for Pervasive Applications in Wireless Sensor Networks", Proceedings of the 2nd European Workshop on Wireless Sensor Networks (Jan. 31, 2005), pp. 1-13.93Hawick, K A., et al., "Middleware for Wireless Sensors and Robots", DHPC Technical Report DHPC-112 (Aug. 18, 2002), pp. 1-6.94Hill, Jason Lester, "System Architecture for Wireless Sensor Networks", Dissertation of Jason L. Hill, University of California, Berkeley (2003), 196 pages.95Hoareau, D et al., "Constraint-Based Deployment of Distributed Components in a Dynamic Network", LNCS, vol. 3894 (Mar. 16, 2006), pp. 450-464.96Hwang, S-Y, et al, "Personal Workflows: Modeling and Management", MDM 2003, LNCS 2574, pp. 141-152.97Information Society Technologies, "State of the Art in Resource Management on Wired and Wireless Access Networks with Resilience", Jul. 23, 2004, pp. 1-198.98Intel Research, "An Introduction to Wireless Sensor Networks", Technical Report, 2004, 6 pages.99Karuppiah, et al, "Design and Implementation of Multihomed IPv6 Testbed Network for Research Community: The Malaysian IPv6 Network Operation Centre Experience", IWS2000, APAN Conference, Tsukuba, 2000, 6 pages.100Kichkaylo, T et al., "Constrained Component Deployment in Wide-Area Networks Using AI Planning Techniques", Proceedings of the 17th International Symposium on Parallel and Distributed Processing 2003), pp. 1-10.101Kichkaylo, T et al., "Optimal Resource-Aware Deployment Planning for Component-Based Distributed Applications", HPDC '04: Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing (HPDC '04), IEEE Computer Society (2004), pp. 150-159.102Kim, et al, "A leader election algorithm in a distributed computing system", 5th IEEE Workshop on Future Trends of Distributed Computing Systems, 1995, 5 pages.103Kiselyov, "Functional XML parsing framework: SAX/DOM and SXML parsers with support for XML Namespaces and validation", 2001, 42 pages.104Kotov, V. et al., "Optimization of E-Service Solutions with the Systems of Servers Library", Hewlett Packard, Modeling, Analysis and Simulation of Computer and Telecommunication Systems (Aug. 29, 2000), pp. 575-582.105Krause, et al.,"Near optimal Sensor Placements: Maximizing Information while Minimizing Communication Cost", IPSN'06, Apr. 19-21, 2006, 9 pages.106Lacour, S et al., "A Software Architecture for Automatic Deployment of CORBA Components Using Grid Technologies", Networking and Internet Architecture, DECOR04 (Nov. 24, 2004), pp. 187-192.107Lampe, et al, "A ubiquitous computing environment for aircraft maintenance", SAC '04: Proceedings of the 2004 ACM Symposium on Applied Computing, 2004, pp. 1586-1592.108Law, et al, "Assessing Security-Critical Energy-Efficient Sensor Networks", 2002, 10 pages.109Levis, Philip et al., "TinyOS: An Operating System for Sensor Networks", Feb. 17, 2004, pp. 1-32.110Liu, Jinshan et al., "Group Management for Mobile Ad Hoc Networks: Design, Implementation and Experiment", Proceedings of the 6th International Conference on Mobile Data Management, Ayia Napa Cyprus, May 13, 2005, 8 pages.111Liu, Jinshan et al., "QoS-aware Service Location in Mobile Ad-Hoc Networks", Proceedings of the 5th International Conference on Mobile Data Management, Berkeley, CA USA, Jan. 2004, 12 pages.112Malek, S et al., "A decentralized redeployment algorithm for improving the availability of distributed systems", LNCS, vol. 3798 (Nov. 3, 2005), 13 pgs.113Malek, S et al., "A style-aware architectural middleware for resource-constrained,distributed systems", IEEE Transactions on Software Engineering, vol. 31, Issue 3 (Mar. 2005), pp. 256-272.114Malpani, et al, "Leader election algorithms for mobile ad hoc networks", Proceedings of the 4th international Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Aug. 11, 2000, pp. 96-103.115Mikic-Rakic, M et al., "A tailorable environment for assessing the quality of deployment architectures in highly distributed settings", Second International Working Conference on Component Deployment (2004), pp. 1-15.116Mikic-Rakic, M et al., "Improving availability in large, distributed component-based systems via redeployment", LNCS, vol. 3798 (Nov. 3, 2005), 15 pgs.117Nochta, et al, "Relocatable services and service classification scheme", Authorization Level: Public (PU) Version 1.0, Feb. 2005, 59 pages.118Nokia, "Nokia Intellisync Device Management", Overview for IT Managers, May 2007, 19 pages.119Non Final Office Action received for U.S. Appl. No. 11/444,119, mailed on Aug. 28, 2009, 19 pages.120Non-Final Office Action for U.S. Appl. No. 11/283,618, mailed on May 24, 2010, 42 pages.121Non-Final Office Action for U.S. Appl. No. 11/284,195, mailed Nov. 1, 2007, 17 pages.122Non-Final Office Action for U.S. Appl. No. 11/433,621, mailed Aug. 17, 2010, 43 pages.123Non-Final Office Action for U.S. Appl. No. 11/444,119, mailed Mar. 30, 2010, 45 pages.124Non-Final Office Action for U.S. Appl. No. 11/479,284, mailed Aug. 11, 2010, 19 pages.125Non-Final Office Action for U.S. Appl. No. 11/479,284, mailed Oct. 30, 2009, 19 pages.126Non-Final Office Action for U.S. Appl. No. 11/496,641, mailed Jul. 29, 2010, 55 pages.127Non-Final Office Action for U.S. Appl. No. 11/583,274, mailed Aug. 5, 2010, 21 pages.128Non-Final Office Action for U.S. Appl. No. 11/583,274, mailed Oct. 7, 2009, 22 pages.129Non-Final Office Action for U.S. Appl. No. 11/810,357, mailed on Apr. 26, 2010, 61 pages.130Non-Final Office Action for U.S. Appl. No. 11/871,616, mailed Mar. 9, 2010, 46 pages.131Non-Final Office Action mailed May 14, 2008 for U.S. Appl. No. 11/479,284, 16 pgs.132Non-Final Office Action mailed Nov. 1, 2007 for U.S. Appl. No. 11/284,195, 14 pgs.133Non-Final Office Action mailed Oct. 28, 2008 for U.S. Appl. No. 11/283,618, 35 pgs.134Non-Final Office Action received for U.S. Appl. No. 11/396,299, mailed on Jul. 9, 2009, 15 pages.135Non-Final Office Action received for U.S. Appl. No. 11/444,119, mailed on Feb. 27, 2009, 23 pages.136Notice of Allowance for U.S. Appl. No. 11/479,284, mailed on May 13, 2010, 30 pages.137Overeinder, B. et al., "A Dynamic load balancing system for parallel cluster computing", Future Generations computer Systems, Elsevier Science Publishers, Amsterdam, 12, (1), (May 1996), pp. 101-115.138Paradis, L. et al., "A survey of Fault Management in Wireless Sensor Networks", Journal of Network and systems management, Kluwer Academic Publishers, NE, vol. 15 No. 2, Mar. 13, 2007, pp. 171-190.139Parikh, et al, "Security in Sensor Networks", CS 588: Cryptography, 2001, 28 pages.140Park, "Specification of the Bluetooth System: Wireless connections made easy", Covered Core Package version: 1.2, Nov. 2003, 1200 pages.141Passing, "Profiling, Monitoring and Tracing in SAP WebAS", SAP Library, Jun. 22, 2005, 9 pages.142Perkins, C. et al., "IP Mobility Support for IPv4", IETF Standard, Internet Engineering Task Force (Aug. 2002), pp. 1-100.143Phillips, "Aqueduct: Robust and Efficient Code Propagation in Heterogeneous Wireless Sensor Networks", Master's Thesis submitted to the Graduate School of the University of Colorado, 2005, 61 pages.144Ploennigs, J et al., "A traffic model for networked devices in the building automation", In: Proceedings of the 5th IEEE International Workshop on Factory Communication Systems (WFCS 2004), Vienna, Austria, (2004), pp. 137-145.145Postel, "Internet Control Message Protocol", Protocol Specification. Request for Comments RFC 792, 1981, 21 pages.146Postel, "Internet Protocol", Protocol Specification, Request for Comments RFC 791, 1983, 51 pages.147Postel, "Transmission Control Protocol", Protocol Specification, Request for Comments RFC 793, 1981, 91 pages.148Postel, "User Datagram Protocol", Protocol Specification, Request for Comment, RFC 768, Information Sciences Institute, 1981, 3 pages.149Prabhu, B S., et al., "WinRFID—A Middleware for the Enablement of Radio Frequency Identification (RFID) Based Applications", Mobile, Wireless and Sensor Networks (Mar. 28, 2006), pp. 1-23.150Rebahi, et al, "Service Management Module (SMM)", 2004, 61 pages.151Response to Examination Report for European Application No. 07008409.0, filed May 25, 2010, 17 pages.152Response to Examination Report for European Application No. 07008409.0, filed Nov. 27, 2007, 13 pages.153Response to Examination Report for European Application No. 07008409.0, filed Sep. 8, 2008, 17 pages.154Rostad, et al, "Closing the Product Lifecycle Information Loops", 18th International Conference on Production Research, 2005, 5 pages.155SAP, "SAP NetWeaver: Providing the foundation to enable and manage change", retrieved on Nov. 10, 2005 from http://www.sap.com/solutions/netweaver/index.epx, 1 page.156SAP, "Security Guide for Mobile Engine 2.1 SP02", SAP Library-SAP Mobile Engine, Dec. 1, 2004, 13 pages.157SAP, "Security Guide for Mobile Engine 2.1 SP02", SAP Library—SAP Mobile Engine, Dec. 1, 2004, 13 pages.158SAX, "About SAX", retrieved on Jan. 6, 2006 from http://www.saxproject.org/, 1 page.159Scheer, "Aris-Business Process Modeling", Springer 3rd edition, 2000, 10 pages.160Schlimmer, et al, "Devices Profile for Web Services", May 2005, 39 pages.161Schlimmer, et al, "Web Services Dynamic Discovery (WS-Discovery)", Apr. 2005, 42 pages.162Schneider, et al, "Application and Scenarios of RFID technology", Seminar Datenschutzaspekte im Umfeld des Pervasive Computing, 2004, 29 pages.163Schneier, "Applied Cryptography", 2nd edition, John Wiley & Sons, Inc., 1996, 18 pages.164Sgroi, Marco et al., "A Service-Based Universal Application Interface for Ad-hoc Wireless Sensor Networks", Preliminary Draft (Nov. 26, 2003), pp. 1-39.165Sheng, Q. Z., et al "Enabling Personalized Composition and Adaptive Provisioning of Web Services", CAiSE 2004, LNCS 2084, pp. 322-337.166Skouteli, Chara et al., "Concept-Based Discovery of Mobile Services", Proceedings of the 6th International Conference on Mobile Data Management, Ayia Napa Cyprus. May 13, 2005, 5 pages.167Speiss, "Collaborative Business Items: Decomposing Business Process Services for Execution of Business Logic on the Item", European Workshop on Wireless Sensor Networks, Istanbul, 2005, 3 pages.168Speiss, et al, "Collaborative Business Items", Sixth Framework Programme, Information Society Technology Technical Report, CoBlsDeliverable D101, 2005, 59 pages.169Speiss, et al, "going beyond auto-id-a service-oriented smart items infrastructure", JEIM, Mar. 2007, 9 pages.170Speiss, et al, "going beyond auto-id—a service-oriented smart items infrastructure", JEIM, Mar. 2007, 9 pages.171Spiess, P., et al, "Collaborative Business Items", Deliverable 401: Final Project Report, CoBls Project No. IST-004270, Version 2.0 (Mar. 2007), pp. 1-42.172Spiess, P., et al, "Collaborative Business Items", Deliverable 401: Management & Maintenance Requirements, CoBls Project No. IST-004270, Version 1.0 (Jan. 2005), 21 pgs.173Spiess, Patrik et al., "Going Beyond Auto-ID: A Service-oriented Smart Items Infrastructure", Journal of Enterprise Information Management, vol. 20, Issue 3 (2007), pp. 1-9.174Srivastava, Utkarsh et al., "Operator Placement for In-Network Stream Query Processing", Proceedings of the 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (Dec. 2004), pp. 1-10.175Stewart, C et al., "Profile driven Component Placement for Cluster-based Online Services", IEEE Distributed Systems Online, vol. 5, No. 10, (Oct. 2004), p. 1-6.176Strohbach, et al, "Cooperative Artefacts:Assessing Real World Situations with Embedded Technology", In Proceedings of the 6th International Conference on Ubiquitous Computing, Nottingham, UK, 2004, pp. 250-267.177Sun Microsystems, "Connected Limited Device Configuration", Java(TM) 2 Platform, Micro Edition (J2ME(TM)) Specification Version 1.1, Mar. 2003, 60 pages.178Sun Microsystems, "Jini Architecture Specification", Version 1.2, Dec. 2001, 26 pages.179Sun Microsystems, "Sun SPOT System: Turning Vision into Reality", Sun SPOT System Project description, 2005, 4 pages.180Sun Microsystems, "Connected Limited Device Configuration", Java™ 2 Platform, Micro Edition (J2ME™) Specification Version 1.1, Mar. 2003, 60 pages.181Supplemental Examination Report for European Application No. 07008409.0, mailed Jun. 30, 2008, 3 pages.182Supplemental Examination Report for European Application No. 07008409.0, mailed Mar. 5, 2010, 4 pages.183Talwar, et al, "Approaches for Service Deployment", IEEE Internet Computing, vol. 9(2), Mar.-Apr. 2005, pp. 70-80.184Tolksdorf, R., "Coordination Technology for Workflows on the Web: Workspace", COORDINATION 2000, LNCS 1906, Springer-Verlag Berlin Heidelberg 2000, pp. 36-50.185US 7,752,304, 07/2010, Bornhoevd et al. (withdrawn)186US 7,801,983, 09/2010, Bornhoevd et al. (withdrawn)187van de Loo, et al, "Enterprise Services Design Guide", Version 1.0, SAP, 2005, pp. 1-40.188van der Aalst, "Modelling and analysing workflow using a Petri-net based approach", Proceedings of the 2nd Workshop on Computer-Supported Cooperative Work, Petri nets and related formalisms, 1994, pp. 31-50.189Vasudevan, Sudarshan et al., "Design and Analysis of a Leader Election Algorithm for Mobile Ad Hoc Networks", Proceedings of 12th IEEE ICNP, Oct. 8, 2004, 11 pages.190Veizades, et al, "Service Location Protocol. Request for Comments RFC 2165", Network Working Group, Jun. 1997, 72 pages.191VeriSign, "The EPCglobal Network: Enhancing the Supply Chain", VeriSign Technical Report, 2004, 8 pages.192Vigna, Giovanni "Mobile Code Technologies, Paradigms, and Applications", PhD Thesis, Politecnico di Milano, Milano, Italy, (1998), pp. 1-89.193Villanueva, et al, "Context-Aware QoS Provision for Mobile Ad-hoc Network-based Ambient Intelligent Environments", Header Background Image, 12(3), 2006, 13 pages.194Villanueva, et al, "Context-Aware QoS Provision for Mobile Ad-hoc Network—based Ambient Intelligent Environments", Header Background Image, 12(3), 2006, 13 pages.195Waldo, "The Jini architecture for network-centric computing", Communications of the ACM archive, vol. 42, Issue 7, Jul. 1999, pp. 76-82.196Wameke, et al, "Smart dust: Communicating with a cubic-millimeter computer", Computer, 34(1), 2001, pp. 44-51.197Wander, et al, "Energy Analysis of Public-Key Cryptography for Wireless Sensor Networks", UC Santa Cruz, Sun Microsystems Laboratories, 2005, 5 pages.198Wang, et al, "Timing Analysis of Real-Time Networked RFID Systems", Cambridge Auto-ID Lab, Cambridge UK, 2004, 4 pages.199Wegdam, M et al., "Dynamic reconfiguration and load distribution in component middleware", PhD thesis, University of Twente, Enschede, (2003), pp. 1-257.200Weiser, "The computer for the 21st century", ACM Sigmobile Mobile Computing and Communications Review archive, vol. 3 , Issue 3, Jul. 1999, 6 pages.201Wiemann, M. et al., "A Service and Device Monitoring Service for Smart Items Infrastructures", Third International Conference on Wireless and Mobile Communications 2007, ICWMC, 6 pages.202Wonohoesodo, R et al., "A Role Based Access Control for Web Services", Proceedings of the 2004 IEEE International Conference on Services Computing (2004), pp. 49-56.203Woods, "Enterprise Services Architecture", Galileo Press, 2003, 10 pages.204Wu, Q et al., "Adaptive component allocation in scudware middleware for ubiquitous computing", LNCS, vol. 3824 (Dec. 6, 2005), pp. 1155-1164.205Wu, X et al., "Performance modeling from software components", ACM SIGSOFT Software Engineering Notes, vol. 29, Issue 1 (Jan. 2004), pp. 290-301.206Yao, Yong et al., "Query Processing for Sensor Networks", Proceedings of the 2003 CIDR Conference, Jan. 2003, 12 pages.207Yoonhee, K. et al., "Wapee: A Fault-Tolerant Semantic Middleware in Ubiquitous Computing Environments", Proceedings of EUC Workshops, 2006, pp. 173-182.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8005879Nov 21, 2005Aug 23, 2011Sap AgService-to-device re-mapping for smart itemsUS8065411May 31, 2006Nov 22, 2011Sap AgSystem monitor for networks of nodesUS8131838 *May 31, 2006Mar 6, 2012Sap AgModular monitor service for smart item monitoringUS8156208Oct 18, 2006Apr 10, 2012Sap AgHierarchical, multi-tiered mapping and monitoring architecture for service-to-device re-mapping for smart itemsUS8239419 *Aug 4, 2009Aug 7, 2012Oracle International CorporationGenerating service component definition language from metadataUS8296408May 12, 2006Oct 23, 2012Sap AgDistributing relocatable services in middleware for smart itemsUS8296413May 31, 2006Oct 23, 2012Sap AgDevice registration in a hierarchical monitor serviceUS8396788 *Jul 31, 2006Mar 12, 2013Sap AgCost-based deployment of components in smart item environmentsUS8522341Mar 31, 2006Aug 27, 2013Sap AgActive intervention in service-to-device mapping for smart itemsUS8751644Mar 5, 2012Jun 10, 2014Sap AgModular monitor service for smart item monitoringUS8868725 *Jun 10, 2010Oct 21, 2014Kent State UniversityApparatus and methods for real-time multimedia network traffic management and control in wireless networksUS9094304 *May 10, 2012Jul 28, 2015Cognex CorporationSystems and methods for dynamically configuring communication data itemsUS9098312Nov 16, 2012Aug 4, 2015Ptc Inc.Methods for dynamically generating an application interface for a modeled entity and devices thereofUS9158532Mar 14, 2014Oct 13, 2015Ptc Inc.Methods for managing applications using semantic modeling and tagging and devices thereofUS9183742Oct 26, 2012Nov 10, 2015Xerox CorporationMethods, systems and processor-readable media for optimizing intelligent transportation system strategies utilizing systematic genetic algorithmsUS9225606 *Apr 3, 2013Dec 29, 2015Mitsubishi Electric Research Laboratories, Inc.Method for clustering devices in machine-to-machine networks to minimize collisionsUS9348943Dec 8, 2014May 24, 2016Ptc Inc.Method for analyzing time series activity streams and devices thereofUS9350791Mar 21, 2014May 24, 2016Ptc Inc.System and method of injecting states into message routing in a distributed computing environmentUS9350812Mar 21, 2014May 24, 2016Ptc Inc.System and method of message routing using name-based identifier in a distributed computing environmentUS9420541 *Aug 28, 2013Aug 16, 2016Zte CorporationUplink power control method and device based on genetic algorithm in communication networkUS9462085Mar 21, 2014Oct 4, 2016Ptc Inc.Chunk-based communication of binary dynamic rest messagesUS9467533Mar 21, 2014Oct 11, 2016Ptc Inc.System and method for developing real-time web-service objectsUS9560170Mar 21, 2014Jan 31, 2017Ptc Inc.System and method of abstracting communication protocol using self-describing messagesUS9576046Nov 16, 2012Feb 21, 2017Ptc Inc.Methods for integrating semantic search, query, and analysis across heterogeneous data types and devices thereofUS9578082Jun 26, 2015Feb 21, 2017Ptc Inc.Methods for dynamically generating an application interface for a modeled entity and devices thereofUS20070233881 *Mar 31, 2006Oct 4, 2007Zoltan NochtaActive intervention in service-to-device mapping for smart itemsUS20070283002 *May 31, 2006Dec 6, 2007Christof BornhoevdModular monitor service for smart item monitoringUS20080033785 *Jul 31, 2006Feb 7, 2008Juergen AnkeCost-based deployment of components in smart item environmentsUS20090276525 *Sep 7, 2007Nov 5, 2009Jung Hee JoMethod and apparatus for integrating heterogeneous sensor data in ubiquitous sensor networkUS20100077429 *Sep 19, 2008Mar 25, 2010Electronics And Telecommunications Research InstituteSystem and method for providing multimedia serviceUS20100318652 *Jun 10, 2010Dec 16, 2010Kent State UniversityApparatus and methods for real-time multimedia network traffic management & control in wireless networksUS20110035389 *Aug 4, 2009Feb 10, 2011Oracle International CorporationGenerating service component definition language from metadataUS20110153788 *Dec 23, 2009Jun 23, 2011Jacobus Van Der MerweMethod and System for Automated Network OperationsUS20130304882 *May 10, 2012Nov 14, 2013Cognex CorporationSystems and Methods for Dynamically Configuring Communication Data ItemsUS20140304383 *Apr 3, 2013Oct 9, 2014Mitsubishi Electric Research Laboratories, Inc.Method for Clustering Devices in Machine-to-Machine Networks to Minimize CollisionsUS20150289210 *Aug 28, 2013Oct 8, 2015Zte CorporationUplink Power Control Method and Device Based on Genetic Algorithm in Communication Network* Cited by examinerClassifications U.S. Classification709/200, 709/225, 709/226, 709/224, 709/223International ClassificationG06F15/16Cooperative ClassificationH04L69/40, H04L67/12, H04L41/16, G06N3/126European ClassificationH04L29/08N11, G06N3/12G, H04L41/16Legal EventsDateCodeEventDescriptionAug 7, 2006ASAssignmentOwner name: SAP AG, GERMANYFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:BELENKI, MIKHAIL;REEL/FRAME:018074/0639Effective date: 20060428Jul 28, 2014FPAYFee paymentYear of fee payment: 4Aug 26, 2014ASAssignmentFree format text: CHANGE OF NAME;ASSIGNOR:SAP AG;REEL/FRAME:033625/0334Effective date: 20140707Owner name: SAP SE, GERMANYRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services