Semantic and Logic Based Routing Algorithms for Service Discovery and Composition in Dynamic IoT-Edge Networks

Internet of Things (IoT) interconnects billions of smart sensors, devices, actuators, as well as people, over a distributed environment. Many existing IoT systems are built with predefined tasks and system architecture. To make better use of the large number of “things” available in the IoT infrastructure, we consider to dynamically discover and compose IoT services in the IoT network for new or dynamically arising tasks. To achieve this goal, we develop semantic-based routing protocols for IoT service discovery. We also introduce a distributed planning algorithm in order to efficiently compose distributed IoT services to address dynamically arising tasks. We first consider how to specify the capabilities of the IoT devices and the discovery queries so as to facilitate effective matchmaking. We need to address multi-keyword based queries in the IoT systems. We have studied IoT services and capabilities and noticed that their specification is very different from handling documents. Generally, an IoT device can be specified by a main functionality together with some additional attributes. Thus, we introduce a two-level specification model in which a single keyword is used to specify the main functionality and the Bloom filters are used for specifying the attribute keywords of an IoT service. Next, we consider the memory constraints on IoT and edge devices and focus on the design of routing tables to achieve space-efficiency. We design a capability summarization algorithm to retain the most routing information within the routing table size bound of each IoT node. Our routing table summarization is based on a predefined ontology of IoT capabilities, i.e., the child capabilities can be summarized to a parent capability following the ontology tree. However, this approach will require each node in the IoT network to store the whole ontology tree, which defeats the space reduction goal. Thus, we design an OnBF coding scheme for our two-level approach. For the main functionality specification, we introduce an ontology coding scheme to support ontology-based summarization without needing the ontology tree. The attributes for the IoT service specification are captured in a Bloom filter. Based on OnBF, we design the routing table, the summarization algorithm, etc., to achieve efficient, multi-keyword based service discovery in IoT networks. We also consider how to compose IoT services to achieve the goals of some dynamically arising tasks. When a dynamic task arises, distributed planning is performed over the IoT network to discover the available IoT services and determine how to select and compose them. To ensure planning efficiency, a Logic-based Overlay Network of Services (LONS) is maintained and updated periodically. We then develop a decentralized Graphplan algorithm to traverse through the LONS to derive the desired service composition. Our approach also considers the mutual exclusion relations in the planning graph. Unlike some existing service composition models, our algorithm is comprehensive, fully distributed and efficient in terms of network traffic and the depth of output plan workflow.