An Experimental Study of Small World Network Models for Wireless Networks

Received 27 January 2016; Accepted 30 January 2016;
Publication October 2015

Ziqian Dong¹, Zheng Wang¹, Wen Xie¹, Obinna Emelumadu¹, Chuan-Bi Lin²and Roberto Rojas-Cessa³

¹Department of Electrical and Computer Engineering, New York Institute of Technology, New York, NY 10023
²Department of Information and Communication Engineering Chaoyang University of Technology, Taichung, Taiwan 41349
³Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102Email: ziqian.dong@nyit.edu; cblin@cyut.edu.tw; rojas@njit.edu

Abstract

The concept of small world phenomenon has been observed and applied in many types of networks. This paper presents a study of two small-world network models in clustering formation and routing in wireless network, the Watts and Stragtz’s (WS) and the Newman and Watts (NW) models and evaluates their properties in term of average node degree and path length. We tested the small world phenomenon in wireless networks by simulating a wireless mobile ad hoc network with distributed routing protocols. We present the research challenges of bridging the gap between theoretical models and practical wireless network implementation. This study provides insights on how wireless networks behave under small world network models with distributed routing protocols.

Keywords

Wireless networks
small world
experiment
routing
performance

1 Introduction

The increasing interest in and development of Internet of Things have motivated an exponential growth of devices that are connected and communicated over the Internet. The advancement in wireless technologies is also enabling flexible connections among these devices. Bandwidth for wireless communication is becoming scarce and new avenues are being explored to increase the capacity of the wireless networks. It is becoming increasingly possible to offload communication of a conventional cellular network connection to Wi-Fi, bluetooth and other wireless communication [1]. The large number of devices and the heterogeneous wireless communication links form complex networks making it challenging to measure their performance and diagnose faults.

It has been of interest to model and understand the behavior of complex networks in the past decades [2–4]. Small-world phenomenon is first identified by Milgram in the 1960s to study the connectedness of people in social networks [5]. This study led to the idea that popularized the statement of “six degrees of separation” where there are no more than six connections apart between each pair of people in the world. A general property of the small world phenomenon is that nodes can be reached from others by a small number of hops in a connected network where most nodes are not connected to each other but with only a small number of well-connected nodes (also referred to as hubs) [4]. This phenomenon is observed in social networks, connectivity of the Internet, and gene regulatory networks [6–9].

The increasing complexity of wireless networks has attracted research interests in exploring properties of other complex networks through small world network models [10–11]. It is shown that by adding a few links in wireless networks, the average path length of the network can be reduced drastically[10]. This observation can facilitate the design of practical distributed routing algorithms and improve the performance of resource discovery in wireless networks. A small world in-motion model for ad-hoc networks was proposed to generate synthetic traces that have the same statistical properties of real traces [11]. This model further proves the possibility of using small world network model in the study of real world wireless networks.

In this paper, we explore the small world network model in a mobile ad hoc network (MANET). We simulate the Watts and Stragtz’s (WS) and the Newman and Watts (NW) small-world models, in Matlab and study the degree distribution and average shortest path length between nodes. We implemented a small network in OPNET, compared distance-vector and link-state routing protocols and show that the number of hops using link-state routing protocol is smaller than four. Each node represents a device that connects to others in a one-to-many peer-to-peer relationship. In this paper, every device may communicate with any other device in the network directly or indirectly. Preliminary results were presented in [15]. This study provides insights on how the network behaves when nodes are clustered with distributed routing protocols and challenges in applying small world network models with heterogeneous wireless communication links.

The remainder of this paper is organized as follows. Section 2 presents the Watts and Strogatz’s and Newman and Watts models adopted in this study and the routing protocols used for small-world networks. Section 3 presents the experimental study and simulation results. Section 4 presents discussion on future application of small world models in wireless networks. Section 5 presents our conclusions.

2 Small-World Network Models

2.1 Terminology and Definitions

In this paper, we consider a network of n nodes. The characteristic path length L is defined as the average number of edges that must be taken in the shortest path between any two pairs of devices in the graph. Here, k is the average degree of the node, L is a measure of the global (entire) structure of the graph. Assume a vertex v has k_v neighbors, this neighborhood defines a sub-graph in which there are at most k_v (k_v− 1)/1 edges while the neighbourhood is fully connected. In this paper, every vertex can be considered as a device. The clustering coefficient C for a vertex is defined by the fraction of links between the vertices within its neighborhood and the total number of links that could possibly exist between them. The clustering coefficient C is a measure of the local (neighbor) graph structure. In this paper, C is defined as the probability that two mobile devices (u, v) are connected and each of them is also connected to another mobile device w.

Here, C and L change as more edges are added to the graph. Small-world networks must be highly clustered with small Ls to achieve a small degree of separation.

In this study, the small network model requires the network possess the following four criteria:

The network should be large enough to contain n 1 devices where n also denotes the number of devices in the network.
Each device in the network is connected to an average of k devices where k must satisfy the condition k n.
The network is decentralized. There is no dedicated routers or cell towers to relay messages from mobile devices in the network.
The network is highly clustered. This means devices are either neighbours to other devices or that devices can be reached by others within a small number of steps.

2.2 Small World Network Model

In this paper, we evaluated two popular small world network (SWN) models, namely, the Watts and Strogatz’s (WS) and Newman and Watts (NW), as shown in Figure 1 [7].

For the WS model, N nodes form a network in a ring formation, N ∈ N. Each node is directly connected to other k/2 nodes in its neighborhood. The parameter, k, is an even number, which represents the degree of the nodes. All the nodes will be randomly re-connected. In the WS SWN model, each edge is re-connected with a random probability p. We assume that the vertex at one end of each edge is fixed, and the other end is connected to a randomly selected node in the network. We also assume that there is only one edge between any two randomly selected nodes in the network and no nodes in the network can be connected to itself through its own connected edges. The probability p defines the framework of the WS model. When p = 0, each node is connected to k/2 nodes in its neighborhood directly and there is no re-connection between any two nodes. The WS SMN model with p = 0 is a completely regular network. When p = 1, each node is connected with every other node in the network. The WS SWN model is a completely random network, as shown in Figure 1(a). As a result, we can adjust the framework of this model or convert the framework of the model between two types of network by changing the value of p.

Figure 1 SmallWorld Models [7].

For NW SWN model, the rules of setting up the framework is similar to that of the WS SWN model. However, the connection rules are different. As the propagation of the network continues, based on k, NW model follows the rule of randomly adding an edge between any two nodes with the probability p. Similarly, there is only one edge that can be added between any two randomly selected nodes and no nodes in the network can be connected to itself through its own connected edges. Similar to the WS SWN model, we use p to define the framework. When p = 0, the model presents a regular network. When p = 1, the NW SWN model is the superposition of a regular network and a random network as shown in Figure 1(b).

2.3 Distributed Routing and Routing Protocols in Small-World Networks

In this paper, we evaluated two types of routing protocols, namely Geographical Routing Protocols (GRP) and Optimized Link State Routing (OLSR) protocols, to make forwarding decisions based on the device’s current and future locations. We introduce the routing protocols in this section and presented the simulation results using OPNET in Section 3. We adopt the Greedy Perimeter Stateless Routing (GPSR) [12] and the ellipsoid algorithm as GRP-based distributed routing protocols in this study [13]. These two algorithms focus on collecting and transferring local (neighbor) information to make efficient usage of network resources.

Figure 2 shows an example of the GPSR routing protocol. The selected next hop of a given node with GPSR routing is the node closest to the destination that is within the sender’s range. In this example, the next hop of node S will be the node closest to the destination, which is node B. The distance from all nodes to a destination is depicted by a dashed circle centered at node D. This protocol also has some disadvantages. When the sender node is in close proximity to the destination, even if there are some detour routes, the sender cannot construct a route that will cause an unlimited delay on the network traffic called “dead end.” Furthermore, GPSR cannot work in a three dimensional space, because it utilizes perimeter forwarding, which only uses a two-dimensional space.

Figure 2 Example of geographical routing protocols.

In the ellipsoid algorithm, the positions of the destination node D and the sender node S are used as the two foci of an ellipse. To decide the next hop in this example with this protocol, the sender chooses a node B, which is on the ellipse, aligned in an almost straight line that minimizes SB+BD. According to this rule, the physical distance of the constructed route is close to the actual distance between the source and destination. For example, in Figure 2, node A will be selected as the next hop because it is the closest node to the straight line between sender node S and destination node D. Compared to GPSR, the ellipsoid protocol does not the utilize the perimeter forwarding in forwarding decisions, which allows it to work seamlessly in three dimensional scenarios.

The Optimized Link State Routing (OLSR) protocol [14] is a link state routing protocol tailored towards mobile wireless LAN where multipoint relays (MPRs) are selected to forward broadcast messages during a flooding process. Nodes that are selected as MPR announce the link-state information periodically in their control message. Other nodes report to MPRs to update their status. The adoption of MPRs ensures a smaller overhead on flooding message and fast convergence of generating shortest paths.

3 Simulation Results

3.1 Comparison of the NW and WS Network Models

We first evaluated the WS and NW network models using Matlab simulation without considering the routing algorithms. Figure 3 shows the average path length, clustering coefficient, and probability of degree distribution for an NW and WS network models with N = 1000 and k = 10.

From the simulation results of the WS model, we can see that the average shortest path drops rapidly when p increases. However, clustering coefficient drops slowly. This means WS complex network has small-world features and high clustering characteristics. The degree distribution probability when p is 0.2, 0.6, and 0.9, respectively, is similar to an Erd˝os Rényi (ER) random graph and follows a Poisson distribution. It is possible to create an isolated node when a random reconnection occurs. The isolated nodes will make the shortest path become infinite. Therefore, its necessary to remove the isolated nodes when we calculate the average shortest path.

For the NW network, when p is small, NW has a similar performance as that of the WS network. When p increases, the shortest path drops rapidly and the clustering coefficient drops slowly. When p is big enough, the clustering coefficient starts dropping quickly. When p = 1, the network becomes an overlay network of a regular network and a random network. Both the shortest path and clustering coefficient reach their minimum values.

3.2 Comparison of the NW and WS Network Models

In this experiment, we assume a small network, consisting of no more than one hundred nodes, all trying to communicate with each other. Each node has the capability of playing the role of both a mobile device and a router, and unable to connect to an external network. If one device needs to communicate with any other device within the same network, the device should be able to do so by using any of the other devices communication capabilities. This property is enabled by wireless communication technologies such as WiFi, Bluetooth, and cellular networks.

To verify the Matlab results, we use OPNET (Riverbed Modeler 17) to implement a network. The ability of creating custom models that possess parameters that mimic real world mobile routers in OPNET is the main reason we choose this platform. In our experiment, our system is constrained to the following:

Figure 3 Performance comparison of the NW and WS network models.

All nodes are assumed to be in motion. The cost between nodes is defined by number-of-hops rather than actual distance.
All nodes have limited communication range. This limitation prevents a complete connected network where all nodes are connected to each other.
All nodes are connected in an ad-hoc fashion. This means that they must use MANET protocols and specifications.
All nodes possess an address table of all the other nodes within range. This table is updated as the nodes move.
The connection behavior between nodes (for the sake of the simulation) is peer-to-peer.

We first test the behavior of individual nodes to ensure that they are able to reach other nodes in the network. The simulation includes up to 20 nodes with the same specifications. Then a node on one end of the network is randomly selected to communicate with another random node on the other end. The performance of the system is measured by transmission time and number of hops from a source node to a destination node.

Additionally, we compared the distance vector-based and link-state based routing protocols, namely, Ad hoc On-demand Vector Routing (AODV) and Optimized Link State Routing (OLSR) protocols in our experiments. Both protocols are proactive routing protocols, meaning they periodically update their routing tables. In addition, we added Single-Band Jammers, designed to add noise and interference to further add realism to the simulation.

OPNET places a limit on the number of mobile devices simulated. This means that no more than 80 nodes (with no more than 20 of them being mobile) can be simulated in this software. This limitation may pose concerns of validating a small world network because such a network usually consists of a large number of nodes. In this case, it is reasonable for mobile routing because the nodes are constrained by the range of signals. If a large number of devices are clustered together, signal interference would be another research problem to address, which is out of the scope of this paper.

We configured the nodes to have properties of wireless LAN nodes with some modifications. Table 1 shows the parameters for the simulation. Since all devices can communicate directly with each other, we placed them on the same subnet. The IP addresses are 192.0.0.x. 2 nodes (0 and 6) were selected as the source and destination with IP addresses 192.0.0.1 and 192.0.0.7 respectively. The other nodes were configured as “auto-assign IP.” All nodes were configured to use the AODV and OLSR protocols, on different tests. Figure 4 shows the device layout with their trajectory paths in the experiment. Figure 5 shows the topology with jammers. Figure 6 shows a sample routing table set up for each node.

Table 1 Simulation Parameters

Technology	MANET
Number of nodes	20–80
Number of jammers	7–11
Simulation time	10 minutes
Number of Pings	3 (at 80th, 290th, and 500th seconds)
Jammer base frequency	30 MHz
Jammer bandwidth	10 kHz
Jammer transmission power	10 Watts
IP class	Class C
IP address mode	IPv4
Routing protocol	AODV/GRP, OLSR
Maximum range per node	600 m (approx.)
Simulation range	2000 m (approx.)
Data rate	24 Mbps
X and Y coordinates	varies
Mobile node transmission power	0.005W

The range of the devices was tested to see if they follow design parameters. In this simulation, the devices can detect a device at a 600 m radius. If the device is any further it is unable to update its routing table and is thus not considered part of the network. We use Ping [16] packets to evaluate the communication between a source and a destination node in the experiments.

Figure 7 shows the Pings sent from a source node and the Pings received at the destination node using AODV and OLSR protocols, respectively. It is observed that the ping response times for AODV are longer than OLSR. The average response time for OLSR is less than 100 ms. However, AODV experiences a smaller packet loss as compared to OLSR at the receiving node, making AODV more reliable despite of its slow response time. Figure 8 shows the number of hops from a source node to a destination node in the experiment for OLSR protocol. It is observed that the average hop count is bounded by four hops.

4 Discussion

The fast development and adoption of wireless networks have enabled heterogeneous wireless access technologies. Various transmission ranges can be achieved by different access technologies (e.g., bluetooth, Wi-Fi, 3G, 4G, and 5G cellular, microwave, and satellite communications) ranging from a few meters to thousands of kilometers. The interoperability among these networks are also enabled by software defined radio (SDR) and software defined network (SDN), where new protocols can be tested and deployed with lower cost and at a much higher speed. It is becoming more feasible to test complex network behaviors with experimental approaches.

Figure 4 Device layout with trajectory paths.

Figure 5 Device layout with jammers.

Figure 6 Sample routing table set up.

As we observe from this experimental study on a small scale mobile ad hoc network, the number of the hops are bounded, which validates the existence of small world phenomenon where a node can reach another node within a small number of hops. However, the challenge of realizing these networks remain in the practical consideration of the implementation. Issues such as delay among different networks, geolocation of network nodes, interoperability, and the dynamic nature of the wireless links need to be taken into consideration. The complexity of these interconnected networks may be reduced by adopting the small world phenomenon in social networks to reduce routing complexity. Distributed routing can benefit large-scale distributed networks, which may be well widespread in the future Internet of Things. Multi-dimensional routing may need to be incorporated in multi-scale network implementations when different wireless access technologies are incorporated into one complex network.

Figure 7 A comparison of received ping packets.

Figure 8 Number of hops from a source to a destination for OLSR.

5 Conclusions

This paper presents an experimental study of small world network models in wireless networks. We simulated two small world network models, the Watts and Stragtz’s and the Newman and Watts models and compared the performance of the two models using Matlab. Simulation results show that the Newman Watts model is better suited for modeling a small world phenomenon in wireless networks. We further validated the results in OPNET with a small size network using standard mobile ad-hoc network routing protocols. The results also showed that the number of hops each node experience is capped at four under different clustering and mobility settings. We present the challenges and future direction in small world model in practical implementation of heterogeneous wireless networks.

Ackowledgement

This project is partially supported by MOST of Taiwan, Grant No. MOST103-2632-E-324-001-MY3.

References

[1] Middleton, J. 3 UK offloads network traffic onto WiFi. [Online].Available at: http://telecoms.com/268022/3-uk-offloads-network-traffic-onto-wifi/

[2] Watts, D. J., and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393, 440–442.

[3] Barabási, A.-L., and Albert, R. (1999). Emergence of scaling in random networks. Science, 286, 509–512.

[4] Watts, D. J. (1999). Small worlds: the dynamics of networks between order and randomness. Princeton university press, Princeton.

[5] Travers, J., and Milgram, S. (1969) An experimental study of the small world problem. Sociometry, 32, 425–443.

[6] Liu, C.-Y., Hu, X.-F., Si, G.-Y., and Luo. (2006). Public opinion propagation model based on small world networks. J. Syst. Simul. 12, 070.

[7] Wang, B., Wang, W.-L., and Yang, X.-H., et al. (2009). Research of modeling and simulation on WS and NW small-world network model. J. Zhejiang Univ. Technol. 37, 179–189, 2009.

[8] Humphries, M. D., and Gurney, K. (2008). Network smallworld-ness: a quantitative method for determining canonical network equivalence. PloS One, 3, p. e0002051

[9] Small world exercises. [Online]. Available at: http://pages.physics.corn ell.edu/∼myers/teaching/ComputationalMethods/ComputerExercises/S mallWorld/SmallWorld.html

[10] Helmy, A. (2003). Small worlds in wireless networks. Commun. Lett. IEEE, 710, 490–492.

[11] Mei, A., and Stefa, J. (2009). “Swim: A simple model to generate small mobile worlds,” in INFOCOM 2009, IEEE 2009, 2106–2113.

[12] Karp, B., and Kung, H.-T. (2000). “GPSR: Greedy perimeter stateless routing for wireless networks,” in Proceedings of the 6th annual international conference on Mobile computing and networking, ACM, 243–254.

[13] Yamazaki, K. (2002). Geographical routing protocol for the location-aware services. IEICE, Japan.

[14] N. working group. Optimized link state routing protocol (OLSR). [Online]. Available at: https://tools.ietf.org/html/rfc3626

[15] Dong, Z., Wang, Z., Xie, W., Emelumadu, O., Lin, C., and Rojas-Cessa,R. (2015). “An experimental study of small world network model for wireless networks,” in Proceeding of the Sarnoff Symposium, 2015 36th IEEE, 70–75, 20–22 September 2015, New York, NY.

[16] Ping program. [Online]. Available at: http://linux.die.net/man/8/ping

Biographies

Z. Dong received the B.S. degree in electrical engineering from Beihang University (formerly Beijing University of Aeronautics and Astronautics), Beijing, China, in 1999, the M.S. degree in electrical engineering from New Jersey Institute of Technology, Newark, NJ in 2002, and the Ph.D. degree in electrical engineering from New Jersey Institute of Technology in 2008. She is an Assistant Professor of Electrical and Computer Engineering at New York Institute of Technology (NYIT). Her research interests include architecture design and analysis of practical high-performance packet switches, network security and forensics, and wireless sensor networks. She was associated with Networking Research Laboratory at New Jersey Institute of Technology and MySYNC Laboratory at Stevens Institute of Technology for her postdoctoral research. She is the Principal Investigator and a faculty mentor for the Research Experience for Undergraduates (REU) Program on smartphone and wireless network security at NYIT funded by the U.S. National Science Foundation. Dr. Dong was awarded the Hashimoto Prize for the best Ph.D. dissertation in electrical engineering at NJIT. She is the recipient of 2006 and 2007 Hashimoto Fellowship for outstanding scholarship, and recipient of the New Jersey Inventors Hall of Fame Graduate Student Award for her inventions in network switches. She received the NYIT Presidential Engagement Award for engaging students in research and scholarship. She is a senior member of IEEE, a member of the IEEE Communications Society, IEEE Women in Engineering, the American Society for Engineering Education (ASEE), ACM, and the Environmental Sensing, Networking and Decision-Making (ESND) technical committee. She has served in technical program committee of IEEE Globecom, ICC, HPSR, Sarnoff, GreenCom, and ChinaCom, and as a reviewer for IEEE journals, conferences, and NSF panels.

Z. Wang is a graduate student in the department of Electrical and Computer Engineering at New York Institute of Technology. He received his dual B.S. degree in electrical engineering from Nanjing University of Posts and Telecommunications and New York Institute of Technology. His researches focus on small world network, self-healing materials, control system with high-speed and real-time communication link, and optical time-domain reflectometer.

W. Xie is a graduate student in the department of Electrical and Computer Engineering at New York Institute of Technology. She received her dual B.S. degree in electrical engineering from Nanjing University of Posts and Telecommunications and New York Institute of Technology. Her research interest is in computer networks. She is inspired by her father to become an engineer.

O. Emelumadu received his M.S. in Electrical and Computer Engineering at New York Institute of Technology in 2016. Born in Nigeria, Obinna came to the United States and earned his B.S. in Electrical and Computer Engineering at New York Institute of Technology. He enjoys working on mobile technologies such as smartphones and tablets. His areas of research include mobile computing and wireless networks.

C.-B. Lin received his Ph.D. degree in the electrical and computer engineering from New Jersey Institute of Technology, Newark in 2008. He was a postdoctoral researcher with the Department of Electrical and Computer Engineering, New Jersey Institute of Technology in 2008 to 2009. Currently, he is an assistant professor with the Department of Information and Communication Engineering, Chaoyang University of Technology, Taichung. His current research interests include design and analysis of Internet of thing (IOT), software-defined networks, and Apps of smartphone.

R. Rojas-Cessa (S’97–M’01–SM’11) received the Ph.D. degree in electrical engineering from Polytechnic Institute of New York University, Brooklyn, NY, USA. Currently, he is an Associate Professor in the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, USA. He has been involved in design and implementation of application-specific integrated circuits (ASIC) for biomedical applications and high-speed computer communications, and in the development of high-performance and scalable packet switches and reliable switches. He was part of a team designing a 40 Tb/s core router in Coree, Inc, in Tinton Falls, NJ. His research interests include data center networks, high-speed switching and routing, fault tolerance, quality-of-service networks, network measurements, and distributed systems. He was an Invited Fellow of the Japanese Society for the Advancement of Science in 2009. He visited the University of Electro-Communications, Japan. He was a Visiting Professor in Thammasat University, Thailand. He is a co-author of the book Advanced Internet Protocols, Services, and Applications (Wiley and Sons, 2012). His research has been funded by U.S. National Science Foundation and private companies. He has served in technical committees for numerous IEEE conferences, as a reviewer for several IEEE journals, and as a reviewer and panelist for U.S. National Science Foundation and U.S. Department of Energy. He is the recipient of the Excellence in Teaching Award 2013 of the Newark College of Engineering. He is a recipient of New Jersey Inventors Hall of Fame – Innovators Award in 2013.