HOÀNG QUỐC HỒNG NHẬT

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
---------------------------------------

HỒNG QUỐC HỒNG NHẬT

HỆ THỐNG THƠNG TIN

NGHIÊN CỨU XÂY DỰNG MƠ HÌNH NGỮ NGHĨA
CHO PHÉP QUẢN LÝ VÀ TRUY VẤN CÁC THIẾT BỊ
TRONG INTERNET VẠN VẬT

LUẬN VĂN THẠC SĨ KHOA HỌC
Hệ thống thông tin

2017A
Hà Nội – Năm 2018


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------HỒNG QUỐC HỒNG NHẬT

NGHIÊN CỨU XÂY DỰNG MƠ HÌNH NGỮ NGHĨA
CHO PHÉP QUẢN LÝ VÀ TRUY VẤN CÁC THIẾT BỊ
TRONG INTERNET VẠN VẬT

Chuyên ngành : Hệ thống thông tin

LUẬN VĂN THẠC SĨ KHOA HỌC
Hệ thống thông tin

NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. Nguyễn Bình Minh

Hà Nội – Năm 2018


Acknowledgments
First of all, I would like to send my sincere thanks to the lecturers in Hanoi University of Science and Technology, as well as, the lecturers in the School of Information and Communication Technology. Particularly,
I would like to send my special thanks to Dr. Nguyen Binh Minh, Dr. Vu Tuyet Trinh who have given me
precious instructions and experience to complete this thesis.
I also would like to thank my family. The support and encouragement from my family is always the
motivation for me to move forward.

2


Commitment
I, Hoang Quoc Hong Nhat, commit that this thesis is my own research under the guidance of Dr. Nguyen Binh
Minh.
The results shown in this thesis are honest, not copied or reproduced from any published work. All citations
are clearly referenced.
Hanoi, 15th of October, 2018
Author

Hoang Quoc Hong Nhat
Confirmation of the supervisor


3


Co-author declaration and confirmation
I, co-author with Hoang Quoc Hong Nhat in the article Multiple Peer Chord Rings Approach for Device Discovery in IoT Environment, confirm the contribution of the author including:
• Contribute to the design and develop Multiple Peer Chord Rings architecture
• Implement simulation environment and perform experiments
• Write the draft of the article
I completely agree to the author Hoang Quoc Hong Nhat use this article for the purpose of research, writing
and report Master Thesis at Hanoi University of Science and Technology.
Hanoi, 15th of October, 2018
Responsible author

Nguyen Binh Minh

4


Abstract
Over the last years, in line with the development of information and electrical technologies, Internet of Thing
(IoT) has moved from being a far vision to an increasing market reality. However, how to manage things in
the manner of allowing the dynamic combination among different devices in diverse contexts is one of IoT
challenges today. To address the problem, digital twin concept was put forward with a world that have the
convergence of the physical and the virtual. Creating the virtual representation for physical assets or devices
is first and foremost step to furtherly realize a series of smart operations. In addition, another IoT challenge
is that there are a lot of IoT solutions deployed everywhere. However, towards a large scale smart area (e.g.
building, city, or country), the key requirement is to integrate the solutions with many smart contexts (e.g.
health care, disaster alert, or resource monitor) together. In this study, we propose an overlay management
architecture based on Chord algorithm to manage physical things on a dynamic digital representation layer.
The architecture thus is a combination of multiple Chord rings, and each of them is an overlay network among

devices in a smart context. We also bring forward a multi-attributes management mechanism on the architecture
to effectively support semantic discovery with device attributes.

5


Contents
Acknowledgments

2

Commitment

3

Co-author declaration and confirmation

4

Abstract

5

List of acronyms and symbols

8

List of Figures

9


1

2

3

Problem Statement

10

1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

1.2

Scenario and Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

1.3

Goal and Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1.3.1


Goal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

1.3.2

Assumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

Background

16

2.1

Chord . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2

Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.2.1

Things Management and Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . .


17

2.2.2

Semantic in IoT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.2.3

Attribute indexing scheme on Chord-based DHT . . . . . . . . . . . . . . . . . . . .

19

2.2.4

Our contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

Designing Model

21

3.1

Overall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

21


3.2

Multi-Chord-Ring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.1

Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3.2.2

Operational Mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

6


3.3

4

33

3.3.1


Attribute Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

3.3.2

Applying semantic discovery to ring management . . . . . . . . . . . . . . . . . . . .

38

Experiment and Evaluation

39

4.1

Key Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.1.1

Key Lookup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

4.1.2

Semantic Query . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


41

4.1.3

Querying an attribute on a single ring . . . . . . . . . . . . . . . . . . . . . . . . . .

41

Node Mobility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.2.1

Single Node Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.2.2

Shared Nodes Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

Ring Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

4.2


4.3
5

Semantic Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Conclusion

48

References

49

Author’s Publications

51

Appendix

52

7


List of acronyms and symbols
IoT

Internet of Things

DHT


Distributed Hash Table

P2P

Peer-to-Peer

SHA1

Secure Hash Algorithm 1

SHA256

Secure Hash Algorithm 256

MD5

Message-Digest algorithm 5

URI

Uniform Resource Identifier

RFID

Radio Frequency Identification

EPC

Electronic Product Code


N

Number of nodes in a ring

2m

Key space size of a ring

2p

Key space size of attribute segment

log

Logarithm base 2

hardwareID

Physical identifier of a thing

keyID

Logical identifier of a thing in a ring

ringID

Logical identifier of a ring

globalID


Logical identifier of a thing over entire system

attributeID

Logical identifier of a attribute

attributeA ID

Logical identifier of attribute A

attributeA Key

Logical identifier of a thing having attribute A

8


List of Figures
2.1

Example of context intersections on a hierarchical model in a smart residence area . . . . . . .

18

3.1

Convergence between Physical Layer and Virtual Layer . . . . . . . . . . . . . . . . . . . . .

21


3.2

Multi-Chord-Ring Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

3.3

Example of shared-node-table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.4

Example of neighbor-ring-table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

29

3.5

Example about a query propagation on multi-chord-ring architecture . . . . . . . . . . . . . .

32

3.6

An example about broadcasting on Chord ring . . . . . . . . . . . . . . . . . . . . . . . . . .

35


3.7

An example about attribute distribution tree and thing attribute-based query . . . . . . . . . .

36

4.1

Mean key lookup costs on a single ring in three cases of key space sizes using MD5, SHA1,
and SHA256 hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.2

Mean key lookup cost on 1024-node rings with increasing faulty node number . . . . . . . . .

40

4.3

Success rate of key lookup on 1024-node rings with increasing faulty node number . . . . . .

40

4.4

Path length cost for a single attribute query on a single ring . . . . . . . . . . . . . . . . . . .


41

4.5

Network load cost for a single attribute query on a single ring . . . . . . . . . . . . . . . . . .

41

4.6

Single node join cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

4.7

Shared-Node Lookup Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4.8

Cost of shared-node lookup in two cases 4 shared-nodes and 8 shared-nodes with different strides 44

4.9

Shared node join enhancement by indexing attribute ”ring” instead of using neighbor-ring-table

45


4.10 Experimental topology of a multi-chord-ring architecture . . . . . . . . . . . . . . . . . . . .

46

4.11 Network load cost of the testing ring-propagation operation in two cases of using ring-propagation
and attribute-query mechanisms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

47


Chapter 1

Problem Statement
1.1

Introduction

Internet of Things (IoT) has emerged as a core factor of forth industrial evolution, where all things connect each
other to share data and perform automatically tasks in specific contexts. Nowadays, advances in IoT create a
huge potential for programmers to build novel value-added services by exploiting multiple capabilities (e.g.
sensing, communication, computing, storage, and analytic) [6]. Thus, a lot of existing IoT solutions have been
developed such as smart building management, traffic control, and health monitoring and so on. However, it
is also well-known that the IoT solutions require the ability of very high scale and dynamic adaptation to be
able to expand on large space such as towards the development of smart cities or even smart country in the near
future.
In order to build up a large scale IoT environment like that, ”how to manage things efficiently” is a fundamental issue that needs to be addressed. Things management is required not only to identify things and monitor
the join/leave of them, but also to provide the ability to query them. Doing this is not easy because there are a
diversity types of things as well as ways to communicate among them, creating a heterogeneous environment.

There are also dozens of different contextual IoT solutions deployed on the same hardware infrastructure. For
example, fire alarm system, HVAC-type system and health monitoring system would work together in a smart
building and they frequently require the involvement of the same devices such as temperature sensor, cell
phone or intermediate gateway to perform their own operations or data forwarding. This can be seen as the
intersection among smart contexts, that makes building a general management systems become more complex.
In addition, ”semantic interoperability” is a matter of concern [18]. This means that different IoT services
(in other word smart contexts) can access and interpret unambiguously desired data among a vast amount of
data collected from a huge number of things. It is also useful for discovering exactly a thing by providing a
semantic description which expresses the purpose of data it provides, where it is located, or the technical and
non-technical attributes it has. Dealing with those challenges, digital twin is a state-of-art concept that helps
things management become easier and enables semantic interoperability.
Digital Twin concept [12] by John Vickers and Dr. Michael Grieves was put forward with a world that
10


has the convergence of the physical and the virtual. Since that time, many authors have tried to define the
term digital twin by introducing models that digitize physical entities, manufacture processes and interactions
among real-world objects in a variety of fields. In the aerospace industry [15], digital twin provides virtual representations of structural mechanics along with their lifecycle, that enables optimizations and decisions making
relying on the real-time data collected from sensors. [20] proposed a paradigm towards smart manufacturing by
controlling and monitoring the real production process through logic interaction with their digital twin, and [4]
approached digital twin in simulation aspect. In summary, a digital twin can be considered as a digital copy of a
physical object to display the state of the object through the data associated with it. In addition, it also provides
a simple digital representation of the object so that many individuals, including from a variety of locations, can
collaborate to monitor and control. In this direction, we take advantages of digital twin concept to represent
IoT environment on an overlay network to mask the heterogeneousness and complexity at physical lever.
In this thesis, we propose a novel approach to manage things and thus provide discovery mechanisms for
them in a semantic way based on Chord algorithm [19]. In our proposal, we build a virtual representation
layer based on multiple Chord rings architecture [3] which represents a large IoT environment as an integration of multiple intersected Chord rings. Each Chord ring is seen as a digital twin of a smart context where
interconnections among things involved in are represented by overlay links. Physical things are categorized
in to gateways and sensors, and they are also converted to their own digital twins in form of virtual objects

represented by keys on the rings. In this proposed virtual representation layer, we identify each ring, gateway,
and sensor by assigning them a hashed ID under several features to distinguish each other. We also propose
operation mechanisms to manage join/leave processes of things and query them based on their keys. Dealing
with semantic interoperability, we design an attribute management to query things based on their semantic
attributes. With the approach, we can solve the diverse and complicated links problem among things in real
smart environments and hence enables IoT systems to manage and control things efficiently. The approach also
meets scalability, flexibility, robustness and maintainability requirements for large and mash-up smart contexts.
Our work distinguishes with existing studies in four main aspects: adopting Chord to build a multiple rings
in a single unified architecture to identify things, store and query their digital twin locally on gateway devices
themselves, managing intersections among rings through their shared nodes, controlling joining and leave of
things in the architecture, and enabling semantic discovery for things based on their attributes.
The rest of the thesis is organized as follows. In the remaining parts of this first chapter, section 1.2 presents
a typical IoT scenario, which puts motivations for our study in section 1.3. We present the used theoretical basis
and discuss some related work in the next chapter 2. In chapter 3.1, we describe our general approach of the
virtual representation layer to address the motivation challenges. The model designing is detailed in chapter 3.
In this chapter, our proposed Multi-Chord-Rings architecture along with the main operational mechanisms to
manage things including naming, things join/leave, things lookup and semantic discovery mechanism. Chapter 4 provides our experiments, gained results and observations with our proposals through simulation in order
to demonstrate the efficiency and feasibility of the proposal. Finally, chapter 5 concludes and figures out some
future directions.

11


1.2

Scenario and Challenges

First of all, in order to have a simple and intuitive view of things management and semantic discovery in the
IoT environment, a specific scenario is given.
BKTown is designed for entire BK University community. The town is located on a large campus with more

than 50 hectares area and is divided into two main zones including study plaza and resident village. The study
plaza completes with teaching facilities, study clusters, research centers and several cafeterias, including 33
buildings in this zone. The resident village has 11 buildings, a large gardens and a supermarket. BK Town also
has two stadiums (indoor and outdoor) and an indoor swimming pool. People can go inside BK Town through
5 gateways. There is a bus system provided for residents to move within the campus and also to link to outside
public transportation stations (e.g. city buses and trains). Towards environmental sustainability, BK Town is
built around a lot of trees. By applying high technologies, clean energy is taken full advantage and reused. Key
points for green environment of BKTown includes: CO2 reduction, resource recycling, minimizing the amount
of net water consumption and environmental impact caused by chemical substances, using clean energies (e.g.
solar, wind). BKTown has created an intelligent, social, cultural, and green environment for BK University
staffs and students.
In BKTown, by setting up many industry indoor and outdoor access points, high quality wifi is available
in all spaces (e.g. amphitheatres, studios, buses, rooms) that enables to withstand large connection amount.
Besides wireless, wired links (e.g. power line communication - PLC, twisted pair, optical fiber) are provided for
non-mobility (e.g. street lights, barriers, ventilators) and plug-in-able devices (e.g. desktop computers, printers,
scanners, servers, cameras). Also in BKTown, hundreds of thousands of smart devices, actuators and sensors
(such as televisions, micros, projectors, interactive whiteboards, polycom systems, presence sensors, motion
sensors, temperature sensor, humidity sensor, electronic lock, lighting control, water sensors, door/window
opener/closer, air-conditioners, heaters, robots, sirens, smart meters, smoke detectors, and so on) are deployed
at suitable places of rooms, corridors, floors, lobbies, halls, parkings, roads, path, stadium, and so forth. Due to
the low-energy features, many small devices cannot connect persistently and transmit continuously their data to
the Internet as well as cloud data services for analyses. Instead of, the devices send their data and receive control
orders from other more powerful things via short-range communication mediums (e.g. bluetooth, infrared).
These powerful devices thus pre-process or transmit sensing data to global. Those intermediate things could
be computers, smart TVs, smart phones, network routers, etc. that have capabilities of computing, storing
and transmitting data. In other word, things in BKTown are connected together via ad-hoc and heterogeneous
networks with different protocols. In addition, mobility devices (e.g. smartphone and wearable things) can join
in and leave dynamically BKTown intelligent environment as a part of entire system.
Based on the full spread of network connections, it is possible to gather real-time data around and to make
automatically smart behaviors in different contexts or even linking multiple contexts at the same time. A

number of applications have built for BKTown that are divided into groups: population (live and study), data,
transportation, and environment. The first group focus on improving all life aspects of those who work, study,
live and visit BKTown. The next service group uses information to gain a deeper understanding of BKTown

12


and residents. The third group makes transport systems safer, faster and fairer. Finally the last group create
sustainable, greener environment.
In order to consider the smart operations of BKTown IoT environment, some examples are given as follows:
Example 1: For concrete example, a lecture will be happened after next 30 minutes. All lecture students
and professor are notified via mobile application based on schedule (the application is assigned privilege).
Tracking and directing functions thus show the shortest path go to the lecture hall for whom are inside BKTown.
Users also can set the notification time before lecture (e.g. 30, 60 minutes or more). In this context, if users
drive electric car/bike to the town, the application will suggest free parking slots, where are the nearest lecture
hall. Car license plate identification, GPS location detector, street cameras and parking space sensors thus are
combined to help make the suggestion above. Electrical system and other lecture hall equipments like light,
projectors, micro, interactive whiteboards and so forth are turned on before lecturers. The system is optimized
in the manner of saving power according to collected sensor data (temperature, humidity, light, presence and
so on).
Example 2: Another example about smart management system of BK Towns study plaza: whenever a
researcher and his/her colleagues need to arrange online meetings in a room, they use the resource management
system to register in advance. The assigned meeting rooms are equipped with sensors to control lights, air
conditioning, heating and status (on/off) of all the available devices, making it much easier for these researchers
to personalize the climate. Meeting rooms are monitored by an automated temperature control system, which
automatically turns on/off the heating/air conditioning before the meeting and similarly after the meeting. The
sensors adapt the changes to match the time of the year, the outside temperature, outside light and to the need
of the presenter in automatic set-up of the appropriate parameters for all resources before the meeting. This
ensures his/her personal preferences are met while the building automatically adjusts these preferences in an
environmental friendly way.

Example 3: Emergency disaster management also is one of typical examples for smart environment of
BKTown. In the case of a fire appears in a resident village tower. Many emergency services are composed
and operate together including: activate automatic fire systems, fire alarms, alerting watchmen, polices, doctors, alerting hospitals, identifying optimal roads/routes to be assigned for emergency for each person, who are
staying inside the tower and so on. All scripts for emergencies are built in advance with cooperation of many
different services. To do that data collected from environment (e.g. inside the tower) like temperature, smoke,
video and so on are used to determine emergency locations and situations. Besides,through wearable or mobility devices, residents are identified, and their health statuses are monitored in order to help optimize rescue
processes. Smartphones are brought inside the towers (i.e. there is a high probability that the smartphone owner
is in the tower) are detected through they join in a network and smart contexts of the tower (e.g. identification,
room finding). In the case of emergency, notifications will be sent to the smartphone to assist the owner all
needed information. In another aspect, traffic network for all the emergency services and sensors is tuned in
the manner of ensuring and prioritizing connectivity (e.g. optimal the best routes), bandwidth (e.g. extension).
From the above scenario, there are several research challenges in building BKTown towards to smart and

13


green space. Within our research theme scope, three challenges could be figured out as follows:
Challenge 1: Scalable architecture. Although all IoT services as well as smart contexts presented in the
examples above provide diverse functionalities for a specific scope, they operate based on a common infrastructure of BKTown, including sensors, actuators, electrical equipments, network, clouds and other analytic
applications. There are also devices capability diversities in communication, computation, storage, energy
consumption, produced data types and formats, etc. Moreover, under device viewpoint, in BKTown space, a
thing usually joins in diverse smart contexts (e.g. temperature sensors in a room provide degree data for both
fire emergency and air conditioning services or even more at the same time). As a consequence, scalability is
required to accept the complex and heterogeneous architecture of the device physical lever. Thus, this leads to
the first motivation question: ”How to manage effectively things in the heterogeneous environment with the
context intersection?”
Challenge 2: Elasticity. Elasticity in BKTown IoT environment is manifested by increase or decrease
of resources, services, things, and users amounts depending on the circumstances. In the examples described
above, according to device traits (e.g. mobility, power), the thing number in smart contexts is changeable
by time. Thus, mobile and wearable equipments can become gateways/terminal devices and play the role of

transmitting/receiving data from several other things/services to/from the Internet while they are connecting
in a local network. The mobility devices also can leave from these contexts when their owners move out to
other spaces. There are several questions rising here: ”How to identify things in the large IoT environment
of BKTown? Which mechanisms enable to manage the join and leave processes in/from smart contexts for
things? How to find as well as locate things in the complicated architecture of contexts?”
Challenge 3: Semantic interoperability. Another problem of BKTown environment is to integrate seamlessly between things together at anytime, anywhere in any context. From this viewpoint, semantics interoperability means that different IoT services (in other word smart contexts) can access and interpret unambiguously
data collected from things at the same time. Semantics of the data (for example, with domain knowledge) can
provide machine-interpretable way on what the data represents, where it originates from, how it can be related
to its surroundings, who is providing it, and what are the quality, technical, or even non-technical attributes.
However, related to features such as distributed, shared infrastructures of IoT, semantic interoperability in BKTown also requires comprehensive solutions for organization, discovery, and management of data. In this way,
the semantics model must provide the capability of sharing, processing by various services across different
domains simultaneously. The following questions could be highlighted in order to clear the semantic interoperability problem in BKTown space: ”Which structure is suitable to the semantic interoperability model?
How to map the semantics interoperability model to physical things effectively? What are mechanisms for
organization, discover, management things based on semantics of data collected from BKTowns common
infrastructures?”

14


1.3
1.3.1

Goal and Assumption
Goal

Dealing with the above challenges, our goal in this thesis is to design a virtual representation layer to represent
and manage the device physical layer, that provides:
• Scalable architecture that accepts heterogeneous devices and hides complex interconnections of the device physical lever to organize devices in multiple contexts.
• Appropriate management mechanisms to identify, manage join/leave processes, and query devices.
• Multi-attributes mechanism to represent devices and query based on their semantic attributes, that supports semantic discovery.


1.3.2

Assumption

We also offer some assumption for our work as follows:
• In IoT environment, there are various type of devices, including sensing devices, actuating devices, data
collecting, processing or transferring devices, low-end electronic devices, and so on. To simplify, we
assume that all devices belonging into two types, including sensor and gateway. Sensors are low-resource
devices with the main role is to sense surroundings (e.g. thermometers, smoke detectors, cameras, etc.)
or electronic devices (e.g. light bulbs, fans, doors, etc.), meanwhile gateways are high-resource devices
which can collect data from sensors, process data or transfer data to each other (e.g. smart phones, smart
TVs, Raspberry Pi, etc.). Sensors cannot directly interact to each others, they need connect to gateway
to forward their sensed data.
• The term ”smart context” used in this thesis is defined flexibly in many cases. It may represent a service
domain or a geographic area, depending on services deployed at application level. We assume that
gateways in a context can connect together via some kinds of machine-to-machine protocols such as
CoAP [17], LWM2M [21]. So that, our proposal management layer can leverage those protocols for
communication among devices.
• Semantic discovery is normally known to resolve a semantic query (e.g. ”reducing the room temperature
to 25 degrees”) then query related devices to execute smart actions. The first phase can be done with
an processing engine and a library of rules (e.g. ontology, SPARQL), that returns a set of semantickeywords which describe devices. Then, at the second phase, desired devices are queried based on those
semantic-keywords. So that, we assume that semantic queries are processed beforehand at the former
phase, and our work aim to provide mechanism to manage and query devices at the latter phase based on
resolved semantic-keywords. In this thesis, we call those semantic-keywords as term ”attributes”.

15


Chapter 2


Background
2.1

Chord

Chord [19] is widely known as one of the most popular distributed hash table (DHT) protocols (or algorithm)
using consistent hashing in peer-to-peer (P2P) overlay network, along with CAN, Tapestry, and Pastry. Chord
was introduced in 2001 by Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan of
MIT. Chord is a ring-shaped peer-to-peer overlay network whose nodes (i.e. peers) and data items are matched
into a circle key space including 2m identifiers through a hash function (e.g. SHA-1, SHA-256, etc.). Each
data item is assigned an identifier, denoted as key k, then it is stored on the node whose identifier is equal to or
smallest greater than k. That node is called successor of key k, denoted as successor(k). A node, namely n, is
responsible for an interval of keys (k pred(n) , kn ], in which kn is the node’s key and k pred(n) is its predecessor’s
key. To ensure the durability for Chord ring, each node has overlay links pointing to its immediate next node and
previous node, namely successor and predecessor perspectively. Beside, it maintains a finger table containing
up to m entries pointing to its neighbor nodes, namely finger nodes, for efficient routing. In this way, Chord
provides a lookup service. Whenever a node wants to search a data item with key k, it calls f ind successor(k)
function to route the request to successor(k). In this process, closest preceding node(k) function is performed
to hop to the closest preceding node to k in the finger table. For a Chord ring sized N, a lookup request costs
O(logN) hops.
In addition, Chord is also robust in fault tolerance. By letting each node keep a list of some its successors,
namely successor-list, and backup its keys on those nodes, Chord ensures high success rate for queries when
some nodes are faulty. In our recent research [9], we verified that the success rate is still close to 100% with
the failure rate in the ring up to 50%.
According to [19], Chord has some features as follows:
• Load balance: Chord acts as a distributed hash function, spreading keys evenly over the
nodes; this provides a degree of natural load balance.
• Decentralization: Chord is fully distributed; no node is more important than any other. This


16


improves robustness and makes Chord appropriate for loosely organized peer-to-peer applications.
• Scalability: The cost of a Chord lookup grows as the log of the number of nodes, so even very
large systems are feasible. No parameter tuning is required to achieve this scaling.
• Availability: Chord automatically adjusts its internal tables to reflect newly joined nodes
as well as node failures, ensuring that, barring major failures in the underlying network,
the node responsible for a key can always be found. This is true even if the system is in a
continuous state of change.
• Flexible naming: Chord places no constraints on the structure of the keys it looks up; the
Chord keyspace is flat. This gives applications a large amount of flexibility in how they map
their own names to Chord keys.
Due to these features, we make use of Chord as back-end to build up an overlay architecture and mechanisms
to manage and discover things in a large IoT environment.

2.2

Related Work

There are a lot of existing works related to this study. In this section, we classify roughly these works into
several groups according to their approaches as follows.

2.2.1

Things Management and Discovery

Management architecture. There are three strategies of things management in the IoT environment, including:
centralized, hierarchical and decentralized. Firstly, the centralized management means that all information
about things will be stored in a data center or a cloud storage, seen as a central node, and all discovery activities

will be handled there. This strategy allows for simplicity in design and management and low cost of discovery
because the only matter to do is to ask the central for any things’ information. However, this strategy has
great difficulty in scaling as the number of things and the number of queries increases, besides, the risk of
failures due to network errors or server overload is considerably potential. Secondly, the hierarchical strategy
is a widely used solution in many IoT platforms today. The duty of IoT platforms is to provide a common and
unified architecture to coordinate entire system operations. In the small space, at logical management layer of
IoT platform, things often are modeled in a hierarchical form consisting of several levels of root, parent and
child nodes. Then, they are queried by resolving their URI consisting of routing path to them. Likewise but
in a contextual way, in [11] and [13], a hierarchical tree of smart spaces (e.g., country, region, city, streets,
buildings, rooms), whose each node is a gateway, was introduced to model an IoT environment. Nonetheless,
in larger environments, due to the heterogeneous of network, maybe each device or object has more than one
link to connect to others and some of them can participant in many contexts at the same time. Figure 2.1
illustrates an example of context intersections in a smart residence area, where black lines display hierarchical

17


links between things, meanwhile red and green zones group things into contexts of fire emergency and climate
adjustment respectively. In this way, the hierarchical architecture at logical management layer may not be
sufficient, especially in mash-up scenarios that contain millions of devices belonging to different IoT solutions
integrated together. The reason is that we cannot determine what and where are root, parent, and child nodes
to control and manage efficiently. While some devices can be looked up quickly, other thing control data
flows will get stuck. Finally, the decentralized architecture represents the natural connection of things in IoT
environment. There is no central node and each node is connected to some neighbors. In unstructured overlay
network model, management would be very complex and discovery is performed by flooding a request message
until the target node is found or the Time To Live (TTL) is reached, expending a high cost without ensuring
efficiency. In contrast, structured overlay network model helps to reduce the complexity of management and
discovery costs.

L0


L1

L2

L2

L2

L3

L3

L3

L3

L2
L3
L4

L4
L4

L4

Figure 2.1: Example of context intersections on a hierarchical model in a smart residence area
DHT Chord-based overlay networks in IoT. Using DHT overlay networks seems to be an useful solution for
things discovery in IoT. [8] introduced and compared two architectures for distributed and scalable discovery
services in EPCglobal network to share Electronic Product Code between trading partners, including a flat and

a hierarchical architecture. While the former organizes all EPCglobal subscribing companies over the world
as nodes in a same Chord overlay network, the latter partition those companies into different rings depending
on their geographical locations. Likewise, in [7], the authors also exploited two-level architecture with a DGT
(Discovery Geographic Table) and a DLS (Discovery Location Service) to connect IoT networks that can be
deployed to very large scale. P. Liu in [14] proposed another architecture with Chord rings, which correspond
with two levels to identify objects using many different RFID standards. Each node in the high level Chord ring
is a specific standard and it is linked to the low level ring, where nodes with the same standard are connected
together. Effort presented in [22] brought forward a model, in which many unstructured peer-to-peer networks
are linked together through super nodes. These nodes thus are located in a Chord ring. In other words, the super
nodes are elements of Chord’s ring and the unstructured peer-to-peer networks will be linked and their peers
could be discovered based on the DHT identifications. Those above studies, however, are primarily focused on
building high-level discovery services which serve IoT smart services through intermediaries, and no one aim

18


to enable things discovery right on gateways’ network itself. Moreover, some of those studies manage things
into discrete groups or regions, which are linked by an intermediate DHT network. This limits interoperability
among things in different groups.
Unlike the above approaches, our previous work in [3] proposed a multi peer Chord ring architecture,
where things are grouped and managed by multiple Chord rings deployed on gateway themselves. These rings
can intersect together by sharing one or many common nodes, and there is no central or high-level ring like the
existing studies and therefore our system achieves scalability without depending on any main ring. However,
in this work, routing request among rings takes a long path length and discovering things based on semantic is
still not mentioned. In addition, only one key space are used for the entire architecture, leading to limitations
in the integration and elasticity capabilities.

2.2.2

Semantic in IoT


There are some levels of approaches to semantic interoperability in IoT, including data level, service level
and device level. At data level, information collected from the IoT network is often modeled using ontology
semantic-web for data analysis problems. Service level focuses on categorizing and discovering services based
on semantic descriptions to increase the effectiveness of the coordination and interoperability between services
to operate smart operations. And at device level, semantic interoperability aims to provide data access and direct
control of devices for coordination within a service through semantic attributes of devices. In [11], the authors
introduced a semantic-based IoT service discovery mechanism by grouping things as a hierarchical tree of
smart spaces, each smart space is embodied by a semantic gateway. Each semantic gateway gathers information
from sensors, clusters and aggregates its content, then sends to its parent gateway. Requests are processed by
matching with a routing table in each gateway which representing clusters. In the same direction of partitioning
IoT environment into smart spaces, the study proposed in [13] enables semantic interoperability at device
level where devices’ information and capabilities are represented with virtual representations of semantic-web.
Within a smart space, each device is implemented an agent to transform data and interoperate others by query
the virtual representations maintained by a semantic information brokers (SIB). For discovering devices outside
a smart space, a device’s agent has to query SIB Resolution Service and ucode Resolution Server to reach the
appreciate SIB. However, as mentioned in the previous part, tree-like structures of smart spaces in those studies
have some characteristics that are not well suited to express intersecting contexts environment, moreover, query
handling is may be overburdened by only one gateway for each smart space.
Our solution in this problem is to represent attributes of things as keys on Chord rings, so that semantic
discovery simply becomes key lookup on Chord rings, which can be carried out by any gateway, instead of a
central semantic gateway or an outside semantic server/service.

2.2.3

Attribute indexing scheme on Chord-based DHT

In order to enable semantic discovery on multiple Chord rings architecture like in [3], we review some existing
studies aiming to distribute and query data based on attribute on Chord-based DHT overlay network. The
19



study named Mercury proposed in [2] distributes each attribute on a separate DHT ring-shape overlay network
where Chord is used to partition the value ranges of attributes into intervals. However, the value ranges on
each ring depend on the distribution of nodes, so they also provide light-weight sampling mechanisms for
uniformly sampling random nodes to balance the nodes in the ring. In contrast, Multi-Attribute Addressable
Network (MAAN) in [5] only use a single Chord ring to support multi-attribute and range queries. The authors
partition Chord ring into segments corresponding to different attributes and attribute values are mapped to
correct segment via uniform locality preserving hashing. The study also showed that the number of routing
hops to resolve a multi-attribute range query is O(logN + N × si ), where N is the number of nodes in ring and
si is the ratio of query range width in identifier space to the size of the whole identifier space. In a hybrid
perspective, effort in [1] proposed an approach that uses multiple Chord rings in looking up multi-dimensional
data. In this way, data is distributed and labeled on many rings, each of them corresponds to a dimension.
There is a central Chord ring, which integrates these dimension rings and thus provides search mechanism for
entire system. Structurally, with a central ring and many dimension rings attached on, this architecture includes
two levels of organization with different roles. Further multi-attribute query mechanism can be found in [16].
It exploited underlying DHT overlay network to support complex queries such as multi-attribute and range
queries by leveraging z-cure approximates technique to present data in multi-dimensions then transforming
them 1-dimension key space. It is also applied in IoT scope but at service level, moreover, the 1-dimension key
would be change when a new attribute is added to data (i.e. increase number of data dimensions), leading to
mismatches in highly flexible IoT environments.
Therefore, our approach in this thesis having some points similar to MAAN, each attribute of things is
allocated into a segment of Chord ring, but number of segments can be changed dynamically to adopt the
flexibility of attributes.

2.2.4

Our contributions

As compared with the works described above, our contributions in this thesis include:

• Proposing a novel virtual representation layer based on multiple peer Chord rings to provide mechanisms
to organize, control interoperability and discover things through virtual objects distributed on gateways
themselves.
• Proposing naming mechanism to identify things and rings in different key spaces.
• Enhancing multi-Chord-ring mechanism for efficient discovery things among different rings.
• Proposing attribute management mechanism to enable semantic discovery on the architecture.

20


Chapter 3

Designing Model
3.1

Overall

Figure 3.1: Convergence between Physical Layer and Virtual Layer
In this section, we describe our general approach to deal with the challenges introduced in the section 1.3.
How to manage effectively things in large-scale scopes. One of the IoT typical features is heterogeneous.
Concretely, in smart environments, there is a huge number of devices deployed together including gateways,
sensors, other electrical equipments, network hubs, and so on. Besides, there are also devices capability diversities in communication, computation, storage, energy consumption, produced data types and formats, etc..
As a result, developing IoT services on the physical device level often is extremely difficult and complicated
21


because developers should know almost all the device features before interacting with them. To solve this
problem, in this work, we propose to develop a logical layer with virtual objects, which are representations of
devices at physical layer. This design is brought forward based on the digital twin concept referred at [cite]. In
this way, the virtual objects store information of the devices such as descriptions, access ways, produced data

types, sensing data attributes (e.g. temperature, light intensity, CO2 concentration and so on). Using objects
on the virtual logical layer, IoT services have the ability of controlling devices simply without regarding to the
heterogeneities of equipments at physical layer.
For the logical layer as proposed above, using a centralized database may bring convenient for IoT developers. However, the solution is against nature decentralized feature of IoT even database service provides effective
operation functions for virtual objects (e.g. update, search, delete). In addition, the centralized database still
has other weaknesses: the storage could be received many queries from IoT services at the same time. Thus,
the database is bottleneck of whole system. Next, the storage often is deployed on cloud (to allow sharing data
among different services more easily) that requires an Internet connection. However, in IoT, not all devices
can connect directly to the Internet to transmit data. Instead, the data usually travels on many intermediate
hops (i.e. gateways) using local network before arriving the cloud. For those reasons, the storing solution for
virtual objects in our architecture is designed to operate in a strong distributed environment. In this direction,
all virtual objects data also is stored in a distributed way on physical devices.
At the physical layer, we assume that all devices belong to two types, including sensor and gateway. In
which sensors are low-resource devices with the main role is to sense surroundings (e.g. thermometers, smoke
detectors, cameras, etc.), or electronic devices (e.g. light bulbs, fans, doors, etc.), and so on. Sensors may not
have the ability of storing and processing data, they simply send their sensing and status data to other devices
(i.e. gateways). Conversely, gateways are high-resource devices which have high capabilities of communication, computation, and storage (e.g. smart phones, tablets, etc.), lightweight computers (Arduino, Raspberry
Pi, Galileo, etc.), smart household appliances (TVs, refrigerators, air conditioners, etc.), and so on. Because of
the performance limitations of sensors, gateways are responsible for receiving, storing and preprocessing data
temporarily collected from sensors before forwarding to the clouds. Similarity, in the virtual layer, we also
propose that there are two kinds of virtual objects, including virtual sensor and gateway in accordance with
sensor and gateway in physical layer.
Usually, at physical layer, a number of devices coordinate in specific smart contexts. At the proposed logical layer in our approach, we also groups virtual objects together based on the context that physical devices
participate in. For instance, at physical layer, all air-conditioners and other related equipments (fans, ventilators) in a building work together in a smart climate context. Thus, at virtual logical layer, all virtual sensors and
gateways that represent devices joining in the smart climate context are grouped together into a virtual climate
context. To organize and manage the virtual context, we employ Chord ring algorithm [cite]. In other word,
the objects of virtual climate context are arranged into a Chord ring. The overlay network provided by Chord
help make virtual principle links, create naming and discovery mechanisms for the virtual objects (i.e. sensors
and gateways).


22


The architecture of Chord overlay networks described above is called multi-Chord-ring organization. There
are three types of objects in the virtual layer, namely ring, node, and key. Ring is a Chord network that takes
shape from nodes. Node represents a gateway of the physical layer at the virtual layer. Key in the virtual layer
is a identifier for physical device (including both gateways and sensors). As presented above, an IoT context is
modeled in the virtual layer by a Chord network (ring). Chord protocol thus use these keys belonging to ring
to determine locations of virtual objects in the virtual layer.
In this way, there are maybe intersections between these contexts that is formed through common devices,
which participate in many different contexts at the same time. Concretely, at physical layer, there are two intersection cases, covering share of gateways and sensors among different contexts. The common gateways thus
enable to collect data and control many sensors that belong to several applications simultaneously. Meanwhile,
the common sensors also have the ability of providing data to many different IoT applications at the same time.
For example, a wireless router could join in both climate and fire-alarm systems with the gateway role for
transmitting data from sensors to cloud services. On the other hand, a sensor offers temperature information
in a room for both smart climate (adjusting appreciate temperature) and emergency-monitor (detecting fire)
contexts. In our proposed virtual layer, the common gateways act as share nodes among multiple Chord networks at the same time. While virtual objects of the common sensors will be stored separately and repeatedly
on Chord overlay networks. This organization helps our system can control sensor objects explicitly and the
common gateway objects are bridges between diverse Chord overlay networks (a.k.a different virtual contexts).
Thus, a node can query other nodes that are located on any Chord networks. Figure 3.1 illustrates the mapping
way between devices in the physical layer and the virtual objects in the virtual layer.
As described before, to identify objects, we propose a naming mechanism that allocates keys for both gateways and sensors in our virtual layer. The mechanism also provides identifiers for rings to distinguish them
together. Besides, to manage join and leave processes in/from a ring of sensors, we design sensor registration/unregistration procedures based on Chord protocol to assign sensor virtual objects on an appropriate ring
node. Meanwhile ring-updating function helps maintain link information on rings when a node joins or leaves
in/from system. To find objects the multi-Chord-ring architecture, a key-lookup mechanism is developed with
two sub-functions, including shared-node lookup help to route key finding query to a shared node, and ring
lookup to send the query from one ring to many other rings through found shared nodes. The multi-Chord-ring
architecture and its operational mechanisms is presented in detail at Section 3.2.
Dealing with the challenge of semantic discovery among devices and contexts, a naive solution is to use a
centralized database server to stores all devices’ keys along with their related attributes such as temperature,

humid, light, atmosphere ingredients, and so forth. Thus, all discovery queries would be processed easily on the
servers via searching function. However, the centralized database always makes the bottleneck for IoT systems
and decreases its operation performance as presented before. To resolve this, we propose a semantic discovery
mechanism built on top of multi-Chord-ring architecture that allows querying a set of objects according to their
common attributes. In this direction, each virtual sensor object is declared its attributes (e.g. location attributes
are building name, floor or room numbers, data attributes could be sensing data types). On the multi-Chord-

23


ring layer, each attribute also is assigned an identifier, notated as attributeID. Then, we partition rings into
many parts corresponding to those attributes, each part is sized 2 p , in range of [attributeID, attributeID + 2 p ).
If a device has a attribute, the device is assigned an additional key, called attribute-key, within the specified
range of that attribute. To be similar to the device’s identifier key (that is used to identify devices as mentioned
above), the attribute-key is also used to represent the device on the ring, however, the attribute-key features the
device in term of the attribute that the device has. In other word, a device now is represented by multiple keys,
including one identifier-key and many attribute-keys those match the attributes of the device. The virtual object
of the device is now also located on many appropriate nodes within many different key ranges of the attributes.
This results that a set of devices which have a same attribute can be easily queried with a given attributeID
by examining the corresponding partition of the attribute. Therefore, semantic discovery is enabled on the
multi-Chord-ring layer. We describe in details our proposed semantic discovery mechanism in Section 3.3.

3.2
3.2.1

Multi-Chord-Ring
Architecture

We start to describe the multi-Chord-ring architecture by considering how to organize things, including gateways and sensors, in a context on a Chord ring. With the purpose that things are managed through virtual
objects, and those are hosted by the gateways themselves, we deploy a node of the Chord ring on each gateway.

Due to Chord protocol, those nodes can communicate through overlay links, that makes simple and transparent
the complex underlay physical routes between gateways. In other words, when a gateway enters the smart context, it acts as a new node to join the ring, which was formed by nodes deployed on the other gateways in the
context. The node also initializes a virtual object with an identifier-key to represent its own gateway and hosts
it by itself. In contrast, the way a sensor enters the smart context is not the same as the gateway. Sensors can not
join directly the ring as gateways for lack of communication capability. In stead, they join the ring indirectly
through the gateways they connect to. Concretely, when a sensor connects to a gateway, the gateway creates
for the sensor a virtual object and assigns it an identifier-key. Then, the gateway looks for the successor node
of the key to distribute the virtual object of the sensor on it. In this direction, things management in a context is
a matter of distributing and looking up virtual objects based on their keys. The figure 3.2a is a symbolic design
of a Chord ring where sensor s is connecting to node n and its virtual object is being stored by node n’.
Dealing with the multiple smart contexts scenario as mentioned in the previous section, we can create many
Chord rings, each of them manages a smart context. However, in fact, there may be many common gateways
and common sensors which participate in multiple smart contexts at the same time. From overlay perspective,
this means that the common gateways can simultaneously work as nodes of different Chord rings, and common
sensors’ virtual objects are stored on different Chord rings, resulting intersections between rings. Therefore,
we propose an architecture, namely Multi-Chord-Ring, to represent those intersections, as well as, to manage
things in intersecting smart contexts.

24