Abstract

It is expected that Internet of Things (IoT) revolution will enable new solutions and business for consumers and entrepreneurs by connecting billions of physical world devices with varying capabilities. However, for successful realization of IoT, challenges such as heterogeneous connectivity, ubiquitous coverage, reduced network and device complexity, enhanced power savings, and enhanced resource management have to be solved. All these challenges are heavily impacted by the IoT network topology supported by massive number of connected devices. Small-world networks and scale-free networks are important complex network models with massive number of nodes and have been actively used to study the network topology of brain networks, social networks, and wireless networks. These models, also, have been applied to IoT networks to enhance synchronization, error tolerance, and more. However, due to interdisciplinary nature of the network science, with heavy emphasis on graph theory, it is not easy to study the various tools provided by complex network models. Therefore, in this paper, we attempt to introduce basic concepts of graph theory, including small-world networks and scale-free networks, and provide system models that can be easily implemented to be used as a powerful tool in solving various research problems related to IoT.

1. Introduction

We are experiencing explosive growth in digital data and connected devices today. The estimated number of connected devices connected to the Internet is predicted to reach approximately 6.4 billion in 2016 and 20.8 billion by the year 2020 according to Gartner. Since the inception of the term Internet of Things (IoT), which was intended originally for radio frequency identification (RFID) network, in 1999 by the Auto-ID Center of MIT [1], the concept has evolved into a network that is exponentially larger and more complex, supporting a large number of devices with services such as automotive, utilities, logistics, healthcare, and public safety using various technologies such as wireless sensor network, Wi-Fi, ZigBee, and cellular network to connect to the Internet backbone.

To realize the IoT revolution that will enable new solutions and business for consumers and entrepreneurs by connecting billions of physical world devices with varying capabilities, many major standards development organizations (SDOs) such as ITU-T, IETF, IEEE, and 3GPP have been very active on IoT standardization. In 2012, Recommendation ITU-T Y.2060, “Overview of the Internet of Things” was approved by ITU-T Study Group 13 (SG 13) that provides an IoT reference model and defines IoT as a global infrastructure for the information society, enabling advanced services by interconnecting things based on existing and evolving interoperable information and communications technologies [2]. IETF is actively working on a set of IoT standards focusing on IP transmission over NFC, Bluetooth, and WPAN [1]. IEEE P2413 WG is working on IoT architectural framework standardization that includes IoT domains, abstractions, and commonalities [1]. Finally, 3GPP is working on a narrowband evolution of LTE for IoT (NB-IoT) to be included in Rel. 13 that will further reduce cost and power but provide extended coverage compared to the LTE-M introduced in Rel. 12. Despite the different views on the IoT standardization by different SDOs, there is a general consensus on the technical challenges the IoT needs to solve. These challenges are to provide heterogeneous connectivity, ubiquitous coverage, reduced network and device complexity, enhanced power savings, and enhanced resource management. All these challenges are heavily impacted by the IoT network topology supported by massive number of connected devices.

Network science is a branch of science of interdisciplinary nature based on graph theory, statistical mechanics, data mining, and more [3]. Network science utilizes various models and tools to study complex networks’ topology such as brain networks, social networks, and wireless networks. For decades, random network or Erdös-Rényi network has been the main network model for studying real world complex networks. A random network of nodes is constructed by connecting node pairs if a randomly generated number is greater than a probability . Recently, the “small-world effect” or “six degrees of separation” principle, which was first discovered by the social psychologist Milgram in [4], was first studied by Watts and Strogatz in [5]. In small-world networks, by randomly reconnecting a small number of links in a regular lattice network, the average path length is reduced significantly [612]. Both the random network and small-world network have homogeneous network topology where the nodes have approximately the same number of links. In recent years, scientists have discovered that many real world networks such as world wide web (WWW), social networks, and metabolic networks are not random with node connection or edge distribution approximated by Poisson distribution but have power-law distribution [1321]. In contrast to the Poisson distribution, the power-law distribution has higher peaks and “fat” tails describing the existence of few nodes with massive links observed in real networks. In 1999, Barabási and Albert proposed the scale-free network that has edge distribution equal to power-law nature. The two main features of the scale-free network are that it is an evolving network with incoming nodes and that these nodes are attached preferentially to the existing nodes with a large number of links.

Due to interdisciplinary nature of the network science, with heavy emphasis on graph theory, it is not easy to study the various tools provided by complex network models. There are numerous small-world and scale-free network introductory research papers from statistical mechanics branch, but there are very few introductory research papers from information and communications technology branch that can be used for wireless network optimization. Therefore, in this paper, we attempt to introduce basic concepts of graph theory, including small-world networks and scale-free networks, and provide system models with wireless channel characteristics that can be easily implemented to be used as a powerful tool in solving various research problems related to IoT. Furthermore, we evaluate the proposed system models of small-world networks and scale-free networks based on various complex network metrics, such as average path length and clustering coefficient.

The remainder of the paper is organized as follows. Section 2 presents recent research activities related to applications of small-world and scale-free concepts to IoT networks. Section 3 provides an overview on basic concepts related to complex networks. In Section 4, we describe the proposed system model for small-world networks and system model for scale-free network in Section 5. In Section 6, we present various network characteristics that are needed to be added to the conventional complex network models for IoT modeling. The numerical results are presented in Section 7. Finally, we conclude in Section 8.

Small-world network and scale-free network models have been applied to various wireless networks, serving as different basis to the IoT platform, to solve various problems. We briefly describe recent research activities devoted to improving the wireless networks’ performance based on the small-world and scale-free concepts. One of the first known works that has applied the small-world concept to wireless networks research is the work done in [22] by Helmy. It was shown that the path length of wireless networks can be drastically reduced by rewiring a small number of links between the wireless nodes. Furthermore, a novel resource discovery method was proposed for small-world concept based wireless networks. Authors in [23] proposed to improve synchronization in wireless sensor networks by applying small-world concepts. The proposed model utilizes a small number of high end sensors (H-sensors) with long communication range in addition to the large number of low end sensors (L-sensors) in the network. Using a modified flooding time synchronization protocol in the proposed heterogeneous sensor network, a small-world topology is realized. Experimental results have shown that the synchronization error can be reduced by more than 50% compared to the conventional methods. Another important application of the small-world concept is in improving the energy efficiency in wireless networks. In designing an ad hoc network with improved energy efficiency, the authors in [24] used a new energy efficiency metric of the wireless nodes for the proposed small-world network. The small-world properties were verified through simulation analysis and the proposed model was shown to be more energy efficient than the conventional random network. One of the advantages of scale-free network is the robustness against node failures. In [25], the authors proposed two protocols for constructing scale-free networks. The two protocols are called preferential attachment with time varying feedback and opportunistic two-stage random attachment. Based on degree distribution analysis, it was shown that the proposed network model is scale-free. Authors in [26] proposed a new scale-free network that includes node removal process with compensation mechanism compared to the conventional Barabási and Albert (BA) network that only considers node addition step for node evolution process. The new model is called neighborhood log-on and log-off (NLL) model due to the similar mechanism as in the action of logging on and logging off a system. It was shown that the proposed NLL model achieves decreased average path length and enhanced network connectivity compared to the BA model. In [27], a new scale-free network called flow-aware scale-free (FASF) model is proposed. In this work, the wireless sensor network is modeled as a weighted network and the traffic of the nodes is modeled as the weight. The performance of the proposed model was compared to the BA and NLL models and was shown to achieve increased network lifetime and reduced average path length. Authors in [28] proposed a new shortcut strategy based on local importance of nodes. The proposed method was evaluated in a sensor network with regular sensor nodes and super sensor nodes and was shown to have small-world features. In [29], small-world network models were applied to mobile ad hoc network (MANET) and were implemented based on routing protocols in OPNET. The distance vector based routing protocols and link-state based routing protocols were compared and it was shown that link-state based protocols converge faster. Authors in [30] proposed an energy aware BA model for wireless sensor networks (WSN). The key idea of the proposed method is to consider both node degree and residual energy in preferential attachment. In [31], the authors proposed two protocols to construct energy-efficient and robust large-scale WSN with scale-free properties. The first scheme modifies the BA model by integrating clustering and degree constraint. The second scheme improves energy efficiency through avoiding links to hub-nodes with large potential degrees. The performance of the proposed protocols was verified based on scale-free property, average path length, energy efficiency, and network robustness.

3. Basic Concepts

Complex networks such as computer networks, sensor networks, brain networks, and social networks can be represented as a graph. A graph consists of vertices, nodes, or points connected by edges, links, or lines. Mathematically, a graph can be represented by ordered paired sets , where is a set of vertices and is a set of edges connecting elements of . Furthermore, the degree of a vertex is defined as the total number of edges connected to that vertex. Figure 1 shows a graph consisting of 7 vertices and 7 edges. The degree of node 4 is equal to = 3, since there are 3 edges connected to nodes 2, 3, and 5. The graph in Figure 1 can be described as a network with a set of vertices and a set of edges .

An important model of complex network is the random network or Erdös-Rényi network model. Random network model is commonly used as a network reference model to compare a newly proposed network model. A random network can be characterized by the total number of nodes and the probability that two nodes are connected. A random network can be constructed by the following procedure with nodes and connection probability .

Step 1. Start with a ring of nodes.

Step 2. Choose a node pair .

Step 3. If a randomly generated number between 0 and 1 is less than , then connect the two nodes and .

Step 4. Repeat Steps and for all possible node pairs .

To evaluate the size of a network, the average path length is used and is defined as the average distance between two vertices, averaged over all possible pair of vertices. The distance between a pair of vertices is defined to be the number of minimum edges or hops connecting the two vertices. For example, the distance between vertices 1 and 5 in the network in Figure 1 is equal to 3. The average path length is determined as follows:where is the total number of vertices in the network, is the minimum distance between vertices and , and represents all possible numbers of pairs of vertices. Figure 2 shows a ring of vertices with = 4 and = 3. All possible pairs of vertices for = 4 network are with 6 pairs of possible edges. As shown in the figure, all the possible connections have been implemented in the network. Using (1), the average distance is calculated as . The clustering coefficient is defined as the average fraction of pairs of neighbor vertices that are also neighbors of each other. The clustering coefficient measures the cliquishness of a typical friendship circle. The average clustering coefficient averaged over all vertices is given bywhere is the clustering coefficient for vertex defined aswhere is the actual number of edges connecting the neighbors of vertex , is the total number of neighbor vertices connected to vertex , and is the maximum number of possible connections between the neighbor vertices. Therefore, represents a ratio of actual neighbor node connections to the maximum possible connections. For the network shown in Figure 2, for vertex 1, and , and the maximum number of connections between the neighbor vertices is equal to . Thus, .

The degree distribution is another important metric used for network topology analysis. It is defined as the probability that a randomly chosen node has a degree . A network’s degree distribution depends on the total number of vertices in the network and the node connection probability . A random graph with large and has a degree distribution that can be approximated as Poisson distribution represented as follows:where is the degree and is the average degree. Figure 3 shows the degree distribution for a random network with = 1000, = 0.01, and = 10. It is seen from the figure that the shape of the distribution has a peak around = 10 and falls off exponentially to the sides. In contrast to degree distribution of random networks and small-world networks following Poisson distribution, scale-free networks have degree distribution that follows power-law distribution defined aswhere is the degree and is the scale-free exponent. Many real networks have scale-free property with power-law distribution. For example, Internet, actor casting, and paper citation have power-law distribution with = 2.1, = 2.3, and = 3, respectively.

4. Small-World Network

In this section, we discuss the design and implementation issues related to modeling small-world networks through algorithm description, system model presentation, and metric calculation module overview.

4.1. Algorithm

The small-world model has been actively applied to the communications networks research due to resulting network topology with features such as smaller average transmission delay and more robust network connectivity. The small-world network is constructed by randomly rewiring the edges of a ring lattice with nodes. The following procedure describes the basic steps of the small-world network construction. By varying the rewiring probability , one can analyze the transition of the network from a lattice structure to a random structure with .

Step 1. Start with a ring of nodes.

Step 2. Connect nearest nodes for all the nodes .

Step 3. Reconnect the edges to a randomly chosen node with probability .

Step 4. Repeat Step for all edges in the ring network.

4.2. System Model

Figure 4 shows the system model for implementing a small-world network. The system contains five major blocks: node initialization block, node connection block, rewiring block, average path length calculation block, and clustering coefficient calculation block. Parameters , , and correspond to total number of nodes, initial degree of all the nodes, and rewiring probability, respectively. Furthermore, the node connection matrix or adjacency matrix gives information about all the node connections after the completion of the rewiring process. The node connection matrix shown in equation (6) describes the node connections for the graph example in Figure 1. Note that the small-world network is modeled by a relational graph where the distance is based on edges or hops rather than the absolute distance used in spatial graphs.

4.3. Metric Calculation Modules

In average path length calculation block, based on the node connectional matrix, which contains all the connections between the nodes, the number of hops needed to reach a node from node needs to be calculated. The first step in this module is to find all possible node pair index . For all the node pairs indices, we start by checking if there is a direct connection between nodes and . If there is no direct connection, we check for 2-hop connection where node is connected through an intermediate node. We continue this process with increasing number of hops until all the numbers of connections for all the node pair indices have been found. Finally, all the numbers of hops found for all the node pairs are added and divided by the total number of node pairs. For a network with very large number of nodes, breadth-first search (BFS) algorithm [32] is recommended for average path length calculation. The basic idea of BFS algorithm is to label a reference node as “0” and then “ripple” the labeling process until all the nodes have been labeled. The labels provide the distance with reference to node 0.

In clustering coefficient calculation block, based on the node connectional matrix, the total number of neighbor nodes connected to node is found. Using the number of neighbor nodes found, the maximum number of possible connections is calculated by . The next step is to find the actual number of edges connecting the neighbors of node . We continue this process for all nodes. Finally, we use (3) to calculate the clustering coefficient for node using the information found in the previous steps and get the final clustering coefficient using (2).

5. Scale-Free Network

In this section, we discuss the design and implementation issues related to modeling scale-free networks through algorithm description, system model presentation, and metric calculation module overview.

5.1. Algorithm

Major features of scale-free networks that are different compared to random networks and small-world networks are dynamic addition of new nodes and preferential attachment to existing nodes with rich connections. Due to these features, in contrast to random networks and small-world networks with Poisson distribution, scale-free networks have degree distribution following power-law nature, resulting in higher probability of finding nodes with a large number of links. The following algorithm shows the steps towards construction of a scale-free network.

Step 1. Start with a small number nodes with degree .

Step 2. Introduce a new node into the network.

Step 3. Connect the new node to existing nodes based on maximum degree probability shown as follows: where is the probability of selecting node , is the degree of node , and is the total number of edges in the current network.

Step 4. Repeat Steps and , until a network with nodes and edges has been constructed.

5.2. System Model

The system model for constructing a scale-free network is shown in Figure 5. The main modules are initialization modules, node connection modules, and metric calculation modules. The system model starts by initially connecting nodes with edges. The node connection matrix is generated based on the initial network topology. Based on the node connection matrix, an edge vector is created. We implement the preferential attachment step or Step of the scale-free network algorithm by using the edge vector. The edge vector contains multiple node indices, where the number of index repetitions indicates the number of edges of that node. The edge vector based method is further described based on Figure 6 and equations (8), (9), (10), and (11).

(i) Initial Node Connection

Connection Matrix

Edge Vector

(ii) Network with New Node 4

Connection Matrix

Edge Vector

In Figure 6, an initial graph is shown with 3 vertices and 2 edges for each vertex. Equations (8), (9), (10), and (11) show the connection matrix with connection information of the initial graph topology. Furthermore, an edge vector includes node indices of all the nodes in the graph in multiples of twos, since all the nodes have 2 links connected to the neighbor nodes. To implement the maximum degree based node selection with target nodes, two random numbers between 1 and the total number of elements in the edge vector, which is 6, are generated. Let us assume that the numbers generated are 3 and 6. Since the 3rd and 6th elements of the edge vector are node indices 2 and 3, the new node 4 will connect to the existing nodes 2 and 3 as shown in Figure 6. The updated connection matrix and edge vector due to the new node connection are shown in equations (8), (9), (10), and (11). From the updated edge vector, we can see that the number of node indices 2 and 3 has increased from 2 to 3. Thus, nodes 2 and 3 have higher probability of being selected by the new node 5 compared to nodes 1 and 4. The dynamic addition of a new node and preferential attachment processes are implemented based on three blocks: new node generation block, target node selection block, and connection matrix/edge vector update block, as shown in Figure 5. When a network construction with nodes and edges has been completed, the final node connection matrix is used in the metric calculation blocks: average path length block and degree distribution block.

5.3. Metric Calculation Modules

In average path length calculation block, after completion of a scale-free network construction, the node connection matrix that contains the link information between all the nodes is used for average path length calculation. The steps used in the average path length calculation block for small-world network are also used in the scale-free network system model. Furthermore, the BFS algorithm is recommended for average path length calculation of scale-free networks with a large number of nodes and edges.

Degree distribution calculation is an important factor in studying the power-law nature of the constructed scale-free network. In degree distribution calculation block, the first step is to gather degree for all the nodes in the network using node connection matrix. The range of the degree is defined based on the minimum and maximum degree values found in the first step. The next step is to bin the degree data covering all the degree range. In the last step, the power-law nature of the network is verified by plotting the binned degree data in log-log scale.

6. IoT Model

In contrast to the relational graphs used in general complex network models, spatial graphs are more appropriate models for wireless sensor networks (WSNs). This is because in WSN, due to practical constraints, such as energy capacity and radio transmission range, the links are restricted by the distance between nodes, rather than relational factors as in small-world networks and scale-free networks. Thus, a new incoming node will have a limited number of candidate target nodes to be connected subject to required power consumption to communicate between nodes and that can be simply defined as , where is the path loss exponent and is the minimum power for acceptable reception quality. Furthermore, in heterogeneous WSN, the nodes will have different communication and energy capabilities. Possible WSN nodes are a sink node, a small number of cluster head nodes with high hardware capabilities and energy capacity, and a large number of low cost sensor nodes that are continuously added to the network over time.

Important optimization criteria of WSN are energy efficiency, average path length based on geographical distance, and network tolerance. Based on these WSN optimization criteria, the rewiring scheme in the conventional small-world network algorithm is modified to include performance metric such as energy efficiency as shown below.

Step 1. Start with a ring of nodes.

Step 2. Connect nearest nodes for all the nodes .

Step 3. Reconnect or add new edges based on probability function that is dependent on performance optimization parameters.

Step 4. Repeat Step for all edges in the ring network.

As for the WSN based on scale-free properties, the preferential attachment in the conventional scale-free network algorithm is modified to include performance metric such as energy efficiency as shown below.

Step 1. Start with a small number nodes with degree .

Step 2. Introduce a new node into the network.

Step 3. Connect the new node to existing nodes based on probability that will maximize performance optimization criteria.

Step 4. Repeat Steps and , until a network with nodes and edges has been constructed.

7. Simulation Results

7.1. Small-World Network

In this section, we study the behavior of the small-world network implemented based on the system architecture with metric calculation modules described in Section 4. We initially assumed a regular ring lattice model with = 24 nodes and initial degree = 4 for all the nodes. The small-world network was created according to the system architecture described previously with various rewiring probability ranging from 0 to 1. Figure 7 shows the average path length of the implemented small-world network. One could observe that the average path length is around 4.2 for = 0 (without rewiring) and decreases to 2.6 for high rewiring probability (random network). Even with small number of random rewiring, there is a drastic decrease in average path length. Note that the theoretical average path length value for random network ( = 1) can be calculated as . Figure 8 shows the clustering coefficient of the implemented small-world network. One could observe that the clustering coefficient remains relatively constant with value around 0.5. However, there is rapid drop in the clustering coefficient for rewiring probability greater than 0.1. Thus, we can observe that the small-world network remains highly clustered like regular lattice for less than 0.1. From Figures 7 and 8, we can conclude that the behavior of the small-world network was fully confirmed, having highly clustered behavior as the regular lattice and small average path length as the random graphs, based on the proposed system architecture.

7.2. Scale-Free Network

In this section, we study the behavior of the scale-free network implemented based on the system architecture described in Section 5. Figure 9 compares the average path length for random networks, denoted as RN in the plot, and scale-free networks, denoted as SFN in the plot, for different number of nodes in the network with = 4. The random network was constructed based on the algorithm described in Section 3. As for the scale-free network, the initial number of nodes was set to = 2 and the number of target nodes for preferential attachment by the incoming node was set to . To calculate the average path length, the BFS algorithm was utilized. As shown in Figure 9, with increase in network size , substantial decrease in average path length in scale-free network is observed compared to a random network. Figure 10 shows the degree distribution of a scale-free network with total number of nodes in the network equal to = 500 for different number of initial nodes and target nodes set as , 5, and 7. The degree distribution was calculated using the degree distribution calculation block described in Section 5. As seen in Figure 10, the degree distribution generated by the proposed system model follows the power-law distribution for all different values of and proving that the generated network evolves into a scale-free network. Note that the noise in the tail occurs due to limited number of data to average out the noise. One of the advantages of the scale-free network is the error and attack tolerance. Figure 11 shows the error tolerance performance as a function number of nodes removed from the network. To study the error tolerance performance of the generated scale-free network, out of = 1000 nodes, randomly selected nodes were removed with removal of all the connected edges to that node. Average path length metric was used to study the disruption effect to the scale-free network and random network due to removal of nodes. We can see that when 20% of the nodes in the network are removed, the average path length of the network increases around 16% and 12% in random network and scale-free network, respectively. Note that a peak point can be observed from the figure. This point is called a critical point where the network breaks into numerous isolated clusters, resulting in rapid drop in average path length. From the small average path length, power-law degree distribution, and error tolerance performance shown in Figures 9, 10, and 11, we can conclude that the generated network fully satisfies the scale-free characteristics.

8. Conclusions

In this paper, we introduced basic concepts of complex networks, including small-world networks and scale-free networks. Then, separate system models for small-world networks and scale-free networks were proposed that can be easily implemented and applied to IoT network optimizations. The small-world networks model contains five major blocks: node initialization block, node connection block, rewiring block, average path length calculation block, and clustering coefficient calculation block. As for the scale-free networks model, major blocks are node initialization block, new node generation block, target node selection block, average path length calculation block, and degree distribution calculation block. The proposed system models were evaluated based on various complex network metrics. The simulation results show that one can confirm the small-world characteristics showing highly clustered behavior and small average path length based on the proposed system architecture. Furthermore, the degree distribution generated by the proposed system model followed the power-law distribution for all different values of and proving that the generated network evolves into a scale-free network.

Competing Interests

The author declares that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work was supported by the Dongguk University Research Fund.