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 - HOÀ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 HOÀ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 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 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 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 Contents Acknowledgments Commitment Co-author declaration and confirmation Abstract List of acronyms and symbols List of Figures 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 3.3 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 Semantic Discovery Conclusion 48 References 49 Author’s Publications 51 Appendix 52 List of acronyms and symbols IoT Internet of Things DHT Distributed Hash Table P2P Peer-to-Peer SHA1 Secure Hash Algorithm SHA256 Secure Hash Algorithm 256 MD5 Message-Digest algorithm 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 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 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 shared-nodes and 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 47 3.3.2 Applying semantic discovery to ring management One highlight feature of multi-Chord-ring architecture is that rings can intersect through shared-nodes and from there, requests for discovering things can be forwarded among rings To that, nodes in a ring must find shared-nodes In the previous chapter, we presented a solution for marking neighbor rings in neighborring-table, which are synchronized among all shared-nodes in a ring Therefore, once a shared-node is found, requests can immediately be forwarded from the current ring to its neighbor rings, then from those neighbor rings to their neighbor rings, and so on, according to ring-propagation algorithm However, synchronization of neighbor-ring-table when a new shared-node joins is a matter of concern when the number of existing sharednodes in the ring increases For example, there are 10 buildings in BKTown, each building has 100 rooms, and each room is managed by a ring There is a resource monitoring service to monitor the infrastructure resources of the whole BKTown such as power consumption, device status, etc deployed on a gateway in each room-ring For the convenience of monitoring resources, those gateways will be made into a ring, which would has 1000 shared-nodes with rings managing things in rooms As such, when a new shared-node joins the resource-monitor-ring, neighbor-ring-table synchronization is performed among 1000 share-nodes, this sounds impractical Therefore, we take advantage of the attribute management mechanism to manage the information about neighbor rings In other words, neighbor rings can be considered as things having attribute ”neighbor-ring”, thus, can be represented by attribute keys In this direction, when a new shared-node joins, it just needs to register the neighbor ring, which the shared-node bridges to, with an attribute keyword ”neighbor-ring” in the similar way as registering the attribute key of a thing In addition, the attribute key of a neighbor ring can contain more information than just ringID and a route to the corresponding shared-node as in neighborring-table Semantic attributes of the neighbor ring can be added in to its attribute key, for example, which context it represents, geographic location it deployed, and so on By this way, a ring can be lookup not only by its identifier ringID, but also by its semantic attributes This supports request transition among rings more accurate 38 Chapter Experiment and Evaluation Experimental Method Due to the difficulties to have a real testbed with full hardware and software for a large IoT environment, we build a simulation tool, where ring, node, sensor are considered as programming objects In this approach, a strong configuration and control interface was developed using Python language for all our tests as well as evaluations For each of test, we propose different topologies that have diverse characteristics The different number of nodes and sensors also are created for these topologies in order to gain generality for the tests Otherwise, although in a strong distributed IoT environment, physical communication cost among things plays the important role in performance assessment for entire system, but with the goal of experimenting the virtual representation layer based on multiple peer Chord ring architecture, in this work, we focus on measuring the proposal effects by using the path length in measure of hops and the network load in measure of number of message as the main metrics In order to evaluate the proposed architecture and mechanisms, we carried out some groups of tests as follows: • Key Management: includes some tests to analyze the performance of key-lookup, fault-tolerance and semantic-query mechanisms on a single ring • Node Mobility: experiments joining operation of single-node and shared-node • Ring Lookup: evaluates the operability of ring propagation mechanism in two cases of using neighborring-table and using attribute query on Multi-Chord-Ring architecture 4.1 4.1.1 Key Management Key Lookup In this experiment, we aim to evaluate key lookup operation on a single ring Because rings in the multi-Chordring may have different key space sizes, we tested three cases of rings’ key spaces including: 2128 by using MD5 hash function, 2160 by using SHA1 hash function, and 2256 by using SHA256 hash function In each case, 39 we simulated a single ring with number of nodes in the ring varies exponentially from 16 to 1024 We also simulate randomly from to 10 sensors connecting to each node Then, we let each node in the ring to lookup all sensors’ keys and measure lookup costs Cost (hop/message) KeySpace=2128 (MD5) KeySpace=2160 (SHA1) KeySpace=2256 (SHA256) log(N) 16 32 64 128 Number of nodes 256 512 1024 Figure 4.1: Mean key lookup costs on a single ring in three cases of key space sizes using MD5, SHA1, and SHA256 hash functions Figure 4.1 show the mean lookup costs for each case of key space size and each case of node number in the ring It can be seen that the mean cost in all three cases of key space sizes are similar for every change of node number Meanwhile, it can make an important observation here: the mean lookup cost is about 21 log N with N is the node number This proves that the cost of key lookup does not depend on the key space size, but depends on the number of nodes in the ring KeySpace=2128 (MD5) KeySpace=2160 (SHA1) KeySpace=2256 (SHA256) 10 1.0 0.8 Success Rate Path length (hop) 0.6 0.4 0.2 0% 10% 20% 30% 40% 50% 60% Percentage of faulty nodes(%) 70% 80% 0.0 90% KeySpace=2128 (MD5) KeySpace=2160 (SHA1) KeySpace=2256 (SHA256) 0% 10% 20% 30% 40% 50% 60% Percentage of faulty nodes(%) 70% 80% Figure 4.2: Mean key lookup cost on 1024-node Figure 4.3: Success rate of key lookup on 1024- rings with increasing faulty node number node rings with increasing faulty node number 90% We continue by testing fault tolerance capability of Chord ring On the 1024-node rings, we set some nodes become faulty and increase the percentage of faulty nodes from 0% to 90% Then, we conduct keys lookups like the above test The mean costs are showed in figure 4.2 and the success rates are displayed in figure 4.3 It can be observed that up to 50% of faulty nodes, success rates in all three cases of key space sizes are still close to 100%, and the mean lookup costs only slightly increase to about (hops/messages) Up to 70% of faulty nodes, the success rates are around 80% and the mean costs rise to about 89˜ hops This can be obtained due to the feature of the successor-list of each node - where keys are backed up on With high fault tolerance 40 capability and the negligible increases of key lookup cost like that, Chord shows suitability when applied in an IoT environment, where the stabilities of nodes are not guaranteed 4.1.2 Semantic Query 4.1.3 Querying an attribute on a single ring In this test, we aim to evaluate the efficient of attribute query based on Attribute-Distribution-Tree (ADT) The test is conducted on a 2160 -key-space ring having N = 1024 nodes We vary the attribute segment key-space to 2152 , 2153 , 2154 , 2155 , and 2156 , meaning that each segment has an average of 4, 8, 16, 32, and 64 nodes respectively In order to ensure the generality, we generate 1000 random attributeID values, creating 1000 corresponding attribute segments on the ring Then, we measure how an attribute query costs, in average, in case of stable state (i.e there is no node join or leave) and initial state (i.e the first time an attribute is query) 32 16 2 152 153 154 Attribute segment key-space size 155 156 240 220 200 180 160 140 120 100 80 60 40 20 ADT stable-state query (NumLeaf = NumNode) ADT stable-state query (NumLeaf = NumNode/2) ADT stable-state query (NumLeaf = NumNode/4) ADT init-state query (NumLeaf = NumNode) ADT init-state query (NumLeaf = NumNode/2) ADT init-state query (NumLeaf = NumNode/4) Partition broadcast 152 153 240 220 200 180 160 140 120 100 80 60 40 20 Network load (message) Number of nodes in a segment 64 ADT stable-state query ADT init-state query Partition broadcast Path length (hop) Number of nodes in a segment (log-scale) We also perform partition-broadcast on each segment to make the comparison 154 Attribute segment key-space size 155 156 Figure 4.4: Path length cost for a single attribute Figure 4.5: Network load cost for a single attribute query on a single ring query on a single ring In figure 4.4, the bars illustrate the mean number of nodes in a segment (in log2 scale) and the lines visualize the path length cost of the query from the attributes’ root nodes The cost for lookup a root node from any node on the ring is not showed in the figure but it is about 12 logN (N = 1024 is the number of nodes in the ring) in average In stable state, any attribute query based on ADT from the attribute root node always costs hops The reason is that an attribute root node already cached the responsible nodes of its ADT-leafs before, so it only needs to ask them at once However, in initial state, it must find successor nodes for those ADT-leafs first, thus, the path length cost is considered as the highest cost of the successor finding for a leaf The path length cost in in initial state is also around 12 logN in average and fluctuated depending on the distribution of nodes in the segment In case of churning state, meaning some leafs’ successor nodes join or leave in the segment, the root node must find them again and the path length cost for this task is not greater than the one in initial state Meanwhile, the path length costs of attribute queries based on partition-broadcast are stable depending the number of nodes in the segments The counted hops for any attribute queries are under log(SN) with SN is the number of nodes in the corresponding segment The corresponding network load for the attribute queries is illustrated in figure 4.4 For the queries based on 41 ADT in stable state, the network load is equal the number of ADT-leafs’ successor From the figure, it is seen that the network loads in this case are significantly less than the number of nodes in the segments The cause is that there may be some ADT-leafs having the same successor In contrast, the network loads in initial state are ADT many times higher, and they can be exactly calculated as ∑ network load f ind successor(lea f ) In general, with lea f number of leafs is t, the mean network loads can be theoretically estimated to be not greater than t × 12 logN For instance, in case of a segment having key-space 2156 and 64 nodes, the ADT has 16 leafs, thus, the network load is nearly 16 × 12 log1024 = 80 messages In contrast, any partition-broadcast always costs the network load equal the number of nodes in the segment In summary, although the attribute query based on Attribute-Distribution-Tree expenses quite high cost at initial state, it brings very light weight query later on when the ring becomes stable or has a small churn In contrast, partition-broadcast gives an acceptable path length cost, but huge network load for every queries 4.2 Node Mobility 4.2.1 Single Node Join In order to evaluate join operation of a single node, we performed a test to analyze the update cost so that the ring reaches stable state and the number of nodes are updated Similar to the key lookup experiment, we also considered cases of key space sizes 2128 , 2160 , 2256 , corresponding to MD5, SHA1, and SHA256 hash functions The initial state of this test is a ring containing N = 16, 32, 64, 128, 256, 512, 1024 nodes respectively Then, we randomly and repeatedly created a new node to join the ring The results of the test are illustrated in figure 4.6 Overall, the cost of updating is larger when the key space size is larger, while the numbers of updated nodes are similar, around logN According to the theory in [19], the update cost is O(log2 N), but in fact, this is just the cost of updating at the newly joined node For ring to reach stable state, the previous nodes whose ith finger’s successor is the newly joined node, should be updated Those nodes are found by calling f ind predecessor(n − 2i−1 ) with n is key of new node and i from to m (2m is key space size), resulting total 1400 1300 1200 1100 1000 900 800 700 600 500 400 300 200 100 KeySpace=2128 (MD5) KeySpace=2160 (SHA1) KeySpace=2256 (SHA256) 14 12 Number of Updated Nodes Cost (hop/message) updating cost is about 21 logN × m KeySpace=2128 (MD5) KeySpace=2160 (SHA1) KeySpace=2256 (SHA256) 10 16 32 64 128 Number of Nodes 256 512 1024 (a) Mean path length and network load 16 32 64 128 Number of Nodes 256 (b) Mean number of updated nodes Figure 4.6: Single node join cost 42 512 1024 4.2.2 Shared Nodes Join Shared-Node-Lookup In the join process of a shared-node, looking up another shared-node in the ring to update neighbor-ring-table is an important process In addition, hared-node lookup is also a step to propagation the request from one ring to another We investigated the cost of finding a shared-node at any node in a single ring with different neighbor selection options in the shared-node-lookup algorithm We simulate a 2160 -key-space ring having N = 1024 nodes and vary the number of existing shared-nodes in the ring to 4, 8, 16, 32, 64, 128 respectively Then, we let all single-nodes to find any shared-node by conducting shared-node-lookup algorithm There are also options of neighbor selection (i.e which node will be next selected if a node not find any shared-node on its shared-node-table) in this test, including: stride to the nearest neighbor, stride to the furthest neighbor, stride to the 2nd furthest neighbor, and stride to the 3rd furthest neighbor The mean path length cost for each shared-node-lookup process is measured and displayed intuitively as in figure 4.7 We also analyze in detail the path length cost for each case of shared-nodes number and stride strategy by the histogram charts as illustrated in figure 4.8 stride to nearest neighbor stride to 1st furthest neighbor stride to 2nd furthest neighbor stride to 3nd furthest neighbor 10 Path Length (hop) 28 26 24 22 16 32 Number of Shared-Nodes (node) 64 128 Figure 4.7: Shared-Node Lookup Cost From the results showed in figure 4.7, it can be seen in overall that the shared-node lookup mean costs of all four stride selection strategies in the case of shared-nodes are quite large and these costs significantly decreases as the number of shared-nodes grows (under 10 hops in case of number of shared-nodes is greater than 32) This is perfectly understandable because the ring has more shared-nodes, each node has the greater chance of finding them in its own shared-node-table However, in details, histogram charts in figure 4.8 show that it is a high probability that shared-node is found just after 40 hops for shared-nodes case, 20 hops for and 16 shared-nodes cases and under 10 hops for the greater than 32 number of shared-nodes This means that if the number of shared-nodes is greater than 3% of total nodes number, the path length costs are under 10 hops in general, especially, under hops as the percent of shared-nodes number ups to 10% In comparison among stride-selection strategies, striding to the nearest neighbor tends to give the worst path length costs because adjacent nodes seem to have quite similar neighbors However, striding to the furthest neighbor also does not produce the best results because the theoretical minimum distance between adjacent neighbors is exponentially increased according to the finger-table, leading that shared-nodes locating between 43 adjacent neighbors may be undiscovered That why striding to the 2nd furthest neighbor and the 3rd furthest neighbor bring about better path length costs In summary, selecting neighbor to stride to in shared-node-lookup process depends much on the number of shared-nodes and the distribution of them on the ring Optimizing this selecting is what we surely will in our future plan 20% stride to 1st furthest neighbor 10% 5% 0% Density 15% Density Density 15% 10% 5% 0% 20 40 60 80 100 120 140 Path Length (hops) 20 40 60 80 100 120 140 Path Length (hops) 16% stride to 2nd furthest neighbor 14% 12% 10% 8% 6% 4% 2% 0% 10 20 30 40 50 60 70 80 90 Path Length (hops) 12% stride to 3rd furthest neighbor 10% Density stride to nearest neighbor 20% 8% 6% 4% 2% 0% 10 15 20 25 30 35 40 45 Path Length (hops) 10 15 Path Length (hops) 20 80% stride to 2nd furthest neighbor 70% 60% 50% 40% 30% 20% 10% 0% 10 15 20 Path Length (hops) Density 80% stride to 1st furthest neighbor 70% 60% 50% 40% 30% 20% 10% 0% 10 15 20 Path Length (hops) Density 80% 70% 60% 50% 40% 30% 20% 10% 0% Density Density (a) shared-nodes stride to nearest neighbor 80% stride to 3rd furthest neighbor 70% 60% 50% 40% 30% 20% 10% 0% 10 15 20 Path Length (hops) (b) 128 shared-nodes Figure 4.8: Cost of shared-node lookup in two cases shared-nodes and shared-nodes with different strides Shared node join enhancement by applying semantic discovery In this experiment, we performed a shared-node join test according to the proposed mechanism of the multi-Chord-ring, in which we specifically analyzed the cost of each step: updating the finger-table and find another shared-node to update the neighborring-table Then, we conduct a shared-node join test on the same dataset but applying semantic discovery mechanism to prove the enhancement Similar to the previous experiment, we use the same dataset of 2160 -key-space rings having N = 1024 nodes with various the number of existing shared-nodes (4, 8, 16, 32, 64, 128) Then, we repeatedly let a random node on another ring to join the investigated ring The out coming results are visualized in figure 4.9 44 Network Load (message) Network Load (message) Update Finger-Table and Shared-Node-Table Update Finger-Table 140 120 100 80 60 40 20 800 Find Shared-Node Register "Ring" Attribute Update Neighbor-Ring-Table 600 400 200 16 32 Number of Shared-Nodes 64 128 Figure 4.9: Shared node join enhancement by indexing attribute ”ring” instead of using neighbor-ring-table Because before performing the role of forwarding requests among rings, a shared-node also acts as a singlenode to distribute and lookup keys in a ring Therefore, the finger-table update process is mandatory and the cost of this process is as same as a single-node join With the change in the number of shared-nodes, this cost is not affected, it only depends on the number of nodes in the ring The difference comes from the way a new ring is discovered In the first case, where the new ring is managed by using neighbor-ring-table, the newly joined shared-node need to lookup another shared-node to synchronize neighbor-ring-table among all shared-nodes in the ring From the figure, it can be seen that shared-node lookup process’s cost reduce in the direction of increasing shared-nodes number (as analyzed in the previous experiment) However, the cost of synchronizing neighbor-ring-table increases linearly by the number of shared-nodes In contrast, in the second case, where the new ring is managed as a attribute key with the attribute keyword ”neighbor-ring”, the cost is much lower In details, this process including about 12 logN messages to lookup the root node of the attribute-distribution-tree corresponding to the attribute keyword ”neighbor-ring”, then message from the root node to the appropriate leaf’s successor (because the successor is cached on the root node) 4.3 Ring Propagation In this experiment, we built an experimental topology for BKTown (as described in the scenario 1.2) with a lot of rings that manage things in various contexts Concretely, there are many building, each building contains a set of rings representing room, floor and other common areas On BKcampus, there are a number of services such as smart learning service to serve learning activities, identifying service to monitor students and teachers, and control their permissions when using other services, resource monitoring service to monitor the infrastructure resources of the whole BKTown such as power consumption, device status, etc and so on These 45 services are deployed on gateways in many rooms in buildings, creating service rings that help discovery things, which serve the services, more efficiently In order to manage things belonging many intersected rings like that, multi-Chord-ring architecture is applied Figure 4.10 describes the experimental topology for BKCampus used in this experiment Given an experimental situation, in the context of smart learning, an upcoming class will be held in room 401 in building D9 A server - a shared-node between a room-ring and smart-learning-ring - located on a different building, which is responsible for preparing the class, will send requests to some things in room D9401 for executing smart activities To that, the server needs use ring propagation mechanism to reach virtual objects of those things, which are distributed on ring D9-401 Dealing with the experimental situation, we performed two cases supporting ring propagation including: one uses neighbor-ring-table to route to other rings, then lookup ring D9-401 with a given ringID; and another uses attribute query to obtain neighbor rings’ attribute keys, then lookup ring D9-401 with a given semantic description ”building=D9; room=401” We also scale the topology by changing some parameters such as number of rings, number of nodes to verify the operation and cost of the mechanism Network load costs are measured and grouped into depth level which expresses how far the request is forwarded in ring unit (for example, depth level from a ring and its neighbor ring is 1, and to neighbor of its neighbor ring is 2) Discover things located in room D9-R401 Room(s) Room(s) Floor(s) Floor(s) Common area Common area Room(s) Room D9-R401 Floor(s) Common area Smart Learning Identifying Resources Monitoring Building B1 Other Building (s) Building D9 Figure 4.10: Experimental topology of a multi-chord-ring architecture 46 10 buildings, 10 rooms/building, contexts, 20 nodes/room, 100 nodes/contexts 50 buildings, 50 rooms/building, contexts, 20 nodes/room, 100 nodes/contexts 50 buildings, 50 rooms/building, contexts, 50 nodes/room, 200 nodes/contexts Network Load (message) - log scale Network Load (message) - log scale 8192 4096 2048 1024 512 256 128 64 32 16 2 Depth level 8192 4096 2048 1024 512 256 128 64 32 16 (a) Looking up ring by using ring-propagation 10 buildings, 10 rooms/building, contexts, 20 nodes/room, 100 nodes/contexts 50 buildings, 50 rooms/building, contexts, 20 nodes/room, 100 nodes/contexts 50 buildings, 50 rooms/building, contexts, 50 nodes/room, 200 nodes/contexts Depth level (b) Looking up ring by using attribute-query Figure 4.11: Network load cost of the testing ring-propagation operation in two cases of using ring-propagation and attribute-query mechanisms Figure 4.11a shows the network load costs of the first case, where ring propagation is used; and figure 4.11b illustrates the second case’s one, where attribute query mechanism is used In the first case, the server can immediately discover a number of neighbor ring leveraging its neighbor-ring-table, whereas, in the second case, the server has to query ”neighbor-ring” attribute to find out neighbor rings, resulting there are cost at depth level At depth level 1, the costs increase only when number of neighbor rings rises in the first case, while the costs for the second case are affected by number of nodes in ring At depth level and level 3, the costs in the first case are quite huge because of only looking for the desired ring by ringID, leading a lot of redundant requests at rings inside every building In contrast, semantic discovery helps route requests right to building B1 by checking rings’ attribute keys This proves the efficient of applying semantic discovery not only in things management but also in routing requests among rings 47 Chapter Conclusion This works presented in the thesis concentrate on proposing a virtual representation layer to manage and discover things based on semantic in large-scale IoT environment The virtual representation layer consists of: an overlay network architecture providing mechanisms to organize, control interaction and discover virtual objects represented physical things; and a semantic discovery mechanism to manage things attributes in a distributed way on the overlay network architecture In our proposal, the architecture, namely multi-Chord-ring, is employed to suit the fact that it may have different smart contexts intersecting each other in a large space of IoT environment In this direction, we define a way to dispose and manage things on those logical rings using node and sensor objects corresponding with gateways and sensors Together with building rings, operation mechanisms for the multi-ring architecture also are proposed, consisting of thing naming based on consistent hashing, key insert/remove, key lookup for nodes and sensors, which is not only inside a ring but also over multiple rings based on a proposed ring propagation operation, and node joining/leave Moreover, thing discovery based on semantic is enabled, including attribute management mechanism providing attribute register and query operations The architecture is tested by simulating a large-scale environment with a large number of nodes and sensors to evaluate performance and operation costs of the entire system with various topologies and properties The achieved results prove that our proposal has operability and feasibility to apply to practice Although this study has brought forward a novel logical architecture in managing things, however there are still scopes of this work that can be continued to improve in the near future, namely optimizing fault-tolerance and stabilization functionalities, finding out the shortest path on multiple rings for thing discovery problem to reduce redundant cost, and enabling multi-attribute and range query to enhance semantic discovery Besides, the energy cost for thing control also affects system performance, especially in IoT environment Hence, an energy monitoring model for the architecture will be designed in our plan 48 References [1] Antonopoulos, N., Salter, J., Peel, R.M.: A multi-ring method for efficient multi-dimensional data lookup in p2p networks In: FCS pp 10–16 (2005) [2] Bharambe, A.R., Agrawal, M., Seshan, S.: Mercury: supporting scalable multi-attribute range queries In: ACM SIGCOMM computer communication review vol 34, pp 353–366 ACM (2004) [3] Binh Minh, N., Hong-Nhat, H., Hluch`y, L., Tuyet Trinh, V., Hieu, L.: Multiple peer chord rings approach for device discovery in iot environment Procedia Computer Science 110, 125–134 (2017) [4] Boschert, S., Rosen, R.: Digital Twin—The Simulation Aspect, pp 59–74 Springer International Publishing, Cham (2016), https://doi.org/10.1007/978-3-319-32156-1_5 [5] Cai, M., Frank, M., Chen, J., Szekely, P.: Maan: A multi-attribute addressable network for grid information services Journal of Grid Computing 2(1), 3–14 (2004) [6] Cao, T.D., Hoang, H.H., Huynh, H.X., Nguyen, B.M., Pham, T.V., Tran-Minh, Q., Tran, V.T., Truong, H.L.: Iot services for solving critical problems in vietnam: A research landscape and directions IEEE Internet Computing 20(5), 76–81 (Sept 2016) [7] Cirani, S., Davoli, L., Ferrari, G., Lone, R., Medagliani, P., Picone, M., Veltri, L.: A scalable and selfconfiguring architecture for service discovery in the internet of things IEEE Internet of Things Journal 1(5), 508–521 (Oct 2014) [8] Dahbi, A., Mouftah, H.T.: A hierarchical architecture for distributed epcglobal discovery services In: Global Communications Conference (GLOBECOM), 2015 IEEE pp 1–7 IEEE (2015) [9] Dan, Nguyen; Quoc Hong-Nhat, H.B.M.N., Viet, T.: Pspchord - a novel fault tolerance approach for p2p overlay network In: Lecture Notes in Computer Science (LNCS), Springer, 3rd International Conference on Smart Computing and Communication (SmartCom), Tokyo, 2018 Accepted [10] El-Ansary, S., Alima, L.O., Brand, P., Haridi, S.: Efficient broadcast in structured p2p networks In: International workshop on Peer-to-Peer systems pp 304–314 Springer (2003) [11] Fredj, S.B., Boussard, M., Kofman, D., Noirie, L.: Efficient semantic-based iot service discovery mechanism for dynamic environments In: Personal, Indoor, and Mobile Radio Communication (PIMRC), 2014 IEEE 25th Annual International Symposium on pp 2088–2092 IEEE (2014) 49 [12] Grieves, M.: Digital twin: manufacturing excellence through virtual factory replication White paper (2014) [13] Kiljander, J., Delia, A., Morandi, F., Hyttinen, P., Takalo-Mattila, J., Ylisaukko-Oja, A., Soininen, J.P., Cinotti, T.S.: Semantic interoperability architecture for pervasive computing and internet of things IEEE access 2, 856–873 (2014) [14] Liu, P., Kong, N., Tian, Y., Lee, X., Yan, B.: A dht-based discovery service for rfid network In: 2014 IEEE International Conference on Internet of Things (iThings), and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) pp 344–347 (Sept 2014) [15] Negri, E., Fumagalli, L., Macchi, M.: A review of the roles of digital twin in cps-based production systems Procedia Manufacturing 11, 939–948 (2017) [16] Paganelli, F., Parlanti, D.: A dht-based discovery service for the internet of things Journal of Computer Networks and Communications 2012 (2012) [17] Shelby, Z., Hartke, K., Bormann, C.: The constrained application protocol (coap) Tech rep (2014) [18] Singh, D., Tripathi, G., Jara, A.J.: A survey of internet-of-things: Future vision, architecture, challenges and services In: 2014 IEEE World Forum on Internet of Things (WF-IoT) pp 287–292 (March 2014) [19] Stoica, I., Morris, R., Karger, D., Kaashoek, M.F., Balakrishnan, H.: Chord: A scalable peer-to-peer lookup service for internet applications SIGCOMM Comput Commun Rev 31(4), 149–160 (Aug 2001), http://doi.acm.org/10.1145/964723.383071 [20] Tao, F., Zhang, M.: Digital twin shop-floor: A new shop-floor paradigm towards smart manufacturing IEEE Access 5, 20418–20427 (2017) [21] Tian, L.: Lightweight m2m (oma lwm2m) OMA device management working group (OMA DM WG), Open Mobile Alliance (OMA) (2012) [22] Wenyan, L., Qing, L.: A kind of p2p-based method of dynamic discovery of resources in iot (Nov 2012) 50 Author’s Publication Binh Minh, Nguyen; Hong-Nhat, Hoang and Hluch`y, Ladislav and Tuyet Trinh, Vu and Hieu, Le (2017) Multiple Peer Chord Rings Approach for Device Discovery in IoT Environment Procedia Computer Science, 110, 125-134 Dan, Nguyen; Quoc Hong-Nhat, Hoang; Binh Minh, Nguyen; and Viet, Tran PSPChord - A Novel Fault Tolerance Approach for P2P Overlay Network In Lecture Notes in Computer Science (LNCS), Springer, 3rd International Conference on Smart Computing and Communication (SmartCom), Tokyo, 2018 Accepted 51 Appendix The source code of the simulator has been published at the author’s Github repository: https://github.com/nhatbkk57/python-multi-chord-semantic 52 ... DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI HOÀ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... 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... 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