Research Title: Distributed Service Discovery in Mobile IoT Environments Using Hierarchical Bloom Filters

Research Area: Mobile IoT, Service Discovery, Distributed Service Registry, Service Gateway

Led by: Hyeonjun Jo

 

Summary:

The Internet of Things (IoT) enables many devices, from small sensors to vehicles, to interact with each other in order to provide services to users. Especially, mobiles devices such as smart phones and wearable devices are becoming more powerful and common in everyday life, and it is essential to utilize their capabilities to provide services in IoT environments. In this research, we propose a fast and flexible approach to discovering IoT-based services in mobile IoT environments. We applied Bloom filters to the configuration and management of distributed service registries to reduce the configuration cost, and to reduce the number of message exchanges between registries in updating information about available services in dynamic mobile IoT environments. Especially, we extended the traditional Bloom filter to give it a hierarchical structure to more efficiently discover and manage information about the capabilities of IoT resources and the services that utilize them. We conducted a simulation of discovering services in a highly dynamic mobile IoT environment; our results proved that our approach is much more efficient than existing distributed service discovery approaches.

 

Core Approaches:

To run a service instance, that instance needs to be bound to necessary resource capabilities. In our registry system, the required resource capabilities can be specified at different abstraction levels. The IoT resources that provide capabilities at a certain abstraction level that a service specifies, or more specialized capabilities than those of the abstraction level, are all considered as candidate IoT resources for the service. To support this, the resource capabilities are defined hierarchically by representing the subsumption relations (by using the ‘subClassOf’ relation) between the capabilities. Services are also defined similarly by representing the subsumption relations between service capabilities. The abstract services of a user task define their necessary service capabilities, which can be represented at various abstraction levels, and a query to find service instances for an abstract service can be made according to the abstraction levels specified. Figure 1 shows a part of the service capability hierarchy. The ‘Lighting’ service can be specialized into the ‘Light On-Off’ service, and the ‘Color-changing’ lighting service, which has more specialized services for changing the light colors. If a timer is needed, the ‘Timer’ service can be chosen. For the ‘Security Alarm Service’, there are more specialized services including the ‘Flash Alarm’ and ‘Multimedia Alarm’ services. If the required resource capabilities are not present, a service cannot be instantiated. For instance, as shown in Figure 1, in order to instantiate any of the ‘Security Alarm Service’, both the ‘Security Sensing’ and ‘Multimedia’ or ‘Lighting’ resource capabilities are required. A user task can be performed if all the abstract services are instantiated by being bound to required IoT resources. For example, the ‘Secure a car’ task requires two services, the ‘Lighting’ and ‘Security Alarm’ services, which can be instantiated by using the ‘Lighting’, ‘Multimedia’, and ‘Security Sensing’ capabilities.

[Figure 1. Hierarchy of Resource Capability and Service and Binding Example]

A hierarchical Bloom filter is a set of Bloom filters, each of which corresponds to one level of the resource capability hierarchy. Figure 2 shows an example of the application of a hierarchical Bloom filter to the ‘Lighting’ capability hierarchy. In this example, since each Bloom filter has two hash functions, each capability is converted into two integers. In the figure, the ‘Lighting’ capability is represented by the integer numbers, 5 and 9, the ‘Colored’ lighting capability is converted to 5 and 7, and the 2 and 7 integer numbers are assigned to the ‘RGB Controllable’ lighting capability.

[Figure 2. Bloom Filters Applied to the Resource Capability Hierarchy]

We have developed a method to map all the Bloom filter output values of resource capabilities in a coordinate space. Then, each service registry shares the vector points of its own resource capabilities with other registries in a certain geographical region. The messages that are exchanged between registries are composed of the vector point information, and the location and name of the service registries. The vector points of the resource capabilities and services that are stored in a service registry can be projected to a coordinate system as Figure 3. Each point represents the location of a resource capability. Since a service may require multiple resource capabilities, we represent the location of a service as the median point of the required resource capabilities. By specifying a resource capability at a certain abstraction level, all the specialized resource capabilities can be included in the area in the coordinate system. Resource capabilities that are siblings belong to different areas in the coordinate system.

[Figure 3. Vector Conversion of Resource Capabilities]

 

Intermediate Results:

Figure 4 compares the computing time and message traffics between the non-hierarchical Bloom filter and the hierarchical Bloom filters with different depths (with 2 to 4 levels). As shown in (a) of Figure 4, all the cases of using the hierarchical Bloom filter take much less computing time than the case of using the non-hierarchical Bloom filter. In addition, the gap between the non-hierarchical and hierarchical Bloom filter approaches gets wider as the number of resource capabilities and services increases. The difference between the non-hierarchical Bloom filter approach and the hierarchical Bloom filter approach with four levels is about 490μs when there are 40 resource capabilities and services, and the difference reaches up to 1,020μs when there are 400 resource capabilities and services. We expect that there will be more performance improvement of discovering services when there are more number of resource capabilities and services that need to be managed in a local IoT environment by the distributed service registries.
The computing time of the hierarchical Bloom filter approaches increase slightly as the depth of the hierarchies increases. This time overhead is due to the increase of the time to access multiple integers that correspond to the levels in the hierarchies. The simulation is performed by using a high-performance desktop computer. In practical IoT environments, service gateways are usually located in mobile devices that have much less computing power than the desktop computer. Therefore, we expect that the performance gain that we obtained by using the hierarchical Bloom filters will be significant in real IoT-based service environments. In addition, the performance of individual service registries is critical to improve the overall performance of discovering services in a wide area where there are many resource capabilities and services to manage by a number of service registries.

[Figure 4. Comparisons between Non-Hierarchical and Hierarchical Bloom Filters with Three Hash Functions]

As shown in (b) of Figure 4, the non-hierarchical Bloom filter generates the least amount of message traffic. Regarding to the hierarchical Bloom filter approaches, the message traffic increases slightly as the depth of the resource capability and service hierarchies increases. This is due to the fact that the hierarchical Bloom filters generate longer bit arrays as the depth of the hierarchies increases. However, the differences between the non-hierarchical and hierarchical Bloom filter approaches are not significant (maximum 18Kbyte difference) in mobile IoT environments where the network bandwidth is usually greater than 10Mbps (with Wi-Fi connections).