Article Citation: Chi-Chang Chen, and Zheng-Da Xie. (2021). A STUDY OF FRACTAL GEOMETRY IN WIRELESS SENSOR NETWORKS. International Journal of Engineering Technologies and Management Research, 8(4), 58-70. https://doi.org/10.29121/ijetmr.v8.i4.2021.925

 

Published Date: 24 April 2021

 

Keywords:

Wireless Sensor Network

Fractal Geometry

Node-Gosper Curves

Moore Curves

Localization
ABSTRACT

Fractal geometry is a subject that studies non-integer dimensional figures. Most of the fractal geometry figures have a nested or recursive structure. This paper attempts to apply the nested or recursive structure characteristics of fractal geometry to wireless sensor networks. We selected two filling curves, Node-Gosper and Moore, as our research subjects. Node-Gosper Curve is a curve based on node-replacement with a fractal dimension of two. Its first-order graph consists of seven basic line segments. When the hierarchy becomes larger, it can be filled with a hexagonal-like shape. To allow the mobile anchor node of wireless sensor networks to walk along this curve, the number of levels of the Node-Gosper Curve can be adjusted according to parameters such as the sensing area and transmission range. Many space-filling curves have the common shortcoming that they cannot loop on their own, that is, the starting point and the end point are not close, which will cause the mobile anchor node to use extra paths from the end point back to the starting point. The Moore curve has a self-loop, i.e., the starting point and the ending point are almost at the same position. This paper applies Moore curve to the path planning of the mobile anchor node. We can use this path to traverse the entire sensing area and stay in the central point of each square cluster to collect the information of the nodes where the events occurred. The self-loop characteristic of the Moore curve is expected to reach each sensor to collect data faster than other space filling curves, that is, the transmission latency of the sensor traversal will be reduced.

1.     INTRODUCTION

 

Wireless sensor networks (WSNs) use a large number of sensors to cooperate with each other to sense and transmit data. The sensor has the characteristics of small size, low power consumption, short transmission distance and low cost. First, a large number of sensors are randomly deployed in the area to be sensed to collect various data in the environment. The detection data can be temperature, humidity, luminosity, pressure, carbon dioxide concentration, etc.[1]. Then wireless or wired networks (such as infrared, radio waves, fiber optic media, etc.) send the collected information back to the administrator or user through wireless data collector [1].

The entire universe, including the earth on which we live, is composed of fractal geometries of various non-integer dimensions. We hope to have a linear object that can be repeatedly bent and recursive, and hope that it can fill the entire space. The well-known space-filling curve Node-Gosper Curve is shown in Figure 1. It has been proposed a lot of research and applications regarding Node-Gopser Curve [2],[3]. Node-Gosper Curve can be applied to the localization of wireless sensor networks[2].

 

Figure 1: A level-2 Node-Gosper Curve.

 

This paper addresses the cluster number of the moving trajectory of the Node-Gosper Curve. Meanwhile, we will use the Hilbert Curve as shown in Figure 2, and then improve it to the Moore Curve, a space filling curve as shown in Figure 3. In this paper, we use the moving anchor node to collect the data of the entire sensing area of WSNs.

 

Figure 2: Level 1 to level 4 Hibert Curves

 

Figure 3: Level 1 to level 4 Moore Curve

 

2.     FRACTAL GEOMETRY

 

Most creatures and objects in the world are constructed or arranged according to fractal geometry. They appear to be multiple identical enlarged versions of themselves, such as trees, blood vessels, bronchi, etc. The above objects cannot be derived from the traditional Euclidean dimension. The fractal geometry is the result of Mandelbrot's hard work and challenges the traditional concept of Euclidean integer dimensions. It is the result of research on objects of non-integer dimensions and inconsistent dimensions [4].

 

2.1. THE SELF-SIMILARITY OF FRACTAL GEOMETRY

 

One of the most important characteristics of fractals is self-similarity, which means that no matter how much these fractals are enlarged, they look very similar. A small part of its structure looks like the whole object [5],[6].

2.2. THE GENERATOR OF FRACTAL GEOMETRY

 

The principle of the generator is to perform certain operations on the original pattern, such as lengthening, deforming, etc., to obtain a level 2 pattern. Then perform the same operation on it again to enter the third level; the more times you perform, the higher the level, and the smaller the original graph (first level). Finally, when the number of layers is close to infinity, the resulting graph is called a fractal [6].

We define the aforementioned "space-filling curve" as a curve that can be continuously drawn from a low-dimensional space (such as a one-dimensional straight line) and converted into a high-dimensional space (such as two-dimensional). This curve will be drawn in a specific way to describe the shape of the plane. If this "space filling curve" can completely fill a two-dimensional area, it is called a "plane filling curve" or "Peano curve"[7].

 

2.3. THE GENERATION METHODS OF FRACTAL GEOMETRIES

 

There are several common generation methods of fractal geometries, for example, Edge-replacement curves, Recursive function systems, Node-replacement curves, Iterated function systems, Branching Fractal Trees, and L-­Systems. The following is a detailed introduction to the Edge-replacement curves, Node-replacement curves, and L-Systems that we will use in the later section.

Edge-replacement curves: Replace all edges with smaller first-level graph and repeat recursively.

Node-replacement curves: Replace all nodes with smaller first-level graph and repeat recursively. Take the Hilbert Curves in Figure 4 and Figure 5 as an example. For the first-order Hilbert Curve, the curve divides the plane into four squares of equal area, and then connects the center points. The second-order Hilbert Curve is to divide the plane into sixteen squares of equal area, then turn the first order appropriately and connect the center points. But pay special attention to the second-order Hilbert Curve in Figure 5, if you want to connect the entire graph, you need to use additional line segments to connect them (red line segments). This is one of the major characteristics of the node-replacement curves.

 

Figure 4: The creation of the first-order Hilbert Curve

 

Figure 5: The creation of the first second-order Hilbert Curve

 

L-Systems: This system was invented by botanists when describing the growth process of plants. It can use a set of simple symbolic recursion rules to describe the production process of complex fractal geometry, as shown in the Table 1 [7].

Table 1: An example of L-system

In Table 1, F represents the symbol of the figure, + represents left turn, - represents right turn, 60 represents the angle when turning, and rule represents the generation process of the iteration of its fractal geometry. When returning to the first-order graph, the F on the right of the rule arrow only needs to be brought into a straight line, as shown in Figure 6 for the first-order graph produced by its rule.

To generate the second-order graph, substitute the F on the right of the rule arrow into the entire first-order process. The rule will become

Rule 1:

F+F--F+F+F+F--F+F--F+F--F+F+F+F-- F+F

and the resulting graph is shown in Figure 7.

 

Figure 6: The first order graph generated by Rule 1.

 

Figure 7: The second order graph generated by Rule 1.

 

3.     THE APPLICATION OF FRACTAL GEOMETRY IN WSN

 

Various fractal geometries have their unique characteristics. Their characteristics can be used in some applications of wireless sensor networks after studying and analyzing them.

 

3.1.  NODE-GOSPER CURVE IN LOCALIZATION IN WSN

 

Reference [3] uses a variant of Gosper Curve, which uses the center points of the regular hexagons as the vertexes. The principle is the node-replacement curves introduced in section 2.3, which is named Node-Gosper Curve. Let the GPS-equipped mobile anchor node move along this trajectory, and broadcast its current position to its neighbor sensors at the center of each hexagonal cluster. Each sensor can estimate the distance between itself and the mobile anchor node based on RSSI. When the sensor has more than three estimated distances, it can use the Newton approximation method/least square method of reference [9] to determine its own position.

 

3.2.  DATA COLLECTION OF NODE-GOSPER CURVE

 

Reference [10] uses a mobile anchor node along the Node-Gosper curve to collect data. The mobile anchor node broadcasts at the center of each hexagon along a predetermined trajectory. Sensors within its range will receive the broadcast. After receiving the broadcast, the sensors will send the data to the mobile anchor node at the central point. If the mobile anchor node is used to collect sensor data, the transmission distance of the sensor will be greatly reduced. The mobile anchor node will contact each sensor in the entire sensing area with a predetermined trajectory, so there will be no sensors that cannot be routed to.

 

 

 

4.     THE LOCALIZATION OF SENSORS USING NODE-GOSPER CURVE AND THE DATA COLLECTION OF SENSORS USING MOORE CURVE

 

Through the L-Systems of Node-Gosper Curve, we know its walking route in a certain level, but we don’t know the cluster number it walks on. Therefore, this paper will study Node-Gosper Curve and write it as L-Systems to achieve the addressing of Node-Gosper Curve. We also studied a space-filling curve, Moore Curve. We researched and analyzed it, and applied it to data collection in wireless sensor networks according to its characteristics and advantages.

 

4.1. CHARACTERISTICS OF NODE-GOSPER CURVE

 

Gosper Curve is a curve with fractal dimension of 2, which can fill a hexagonal area. Level-1 Gosper Curve is shown in Figure 8.

 

Figure 8: Level-1 Gosper Curve

 

Figure 9: G-type and R-type of level-1 Node-Gopser Curve

   

Taking the center point of the regular hexagon cell as the vertex, we can use the node introduced in 2.3 to replace the curve and name it as Node-Gosper Curve. Node-Gosper curves can be divided into two types: G-type and R-type, as shown in Figure 9. The L-Systems rules of Node-Gosper Curve are shown in Table 2 [4].

 

Table 2: The L-Systems rules of Node-Gosper Curve

 

In the rules, r means turning to the right by 60°, l means turning to the left by 60°, and ­ means moving straight to the next area. According to this rule, the line segment of Gosper Curve of any level of G-type or R-type can be obtained. Figure 10 shows the level-2 G type.

Figure 10: Level-2 G-type Node-Gosper Curve

 

4.2.  ADDRESSING OF NODE-GOSPER CURVE

 

The numbering method of the Node-Gosper Curve is described in Reference [11], and we use the level-1 Node-Gosper Curve in Figure 11 to illustrate.

 

Figure 11: Cluster number of Level-1 Node-Gosper Curve

 

First, determine the number of digits, because the number of levels in Figure 11 is one, so the number of digits is also one. The next step is to determine the number of blocks. Since the Node-Gosper Curve of the nth level is composed of seven (n-1) Node-Gosper Curves, Figure 11 is composed of 7 Node-Gosper Curves of the zeroth order blocks. Therefore, seven one-digit numbers are used to address the level one Node-Gosper Curve in Figure 11. The number starts from 0 in the center, 1 at the top, and then numbered counterclockwise in sequence. The result of the numbering is shown in Figure 11.

Then take the level-2 Node-Gosper Curve in Figure 12 to illustrate. First, determine the number of digits, because the number of levels in Figure 12 is two, so the number of digits is also two. Next, determine the number of blocks. Since the Node-Gosper Curve of the n-th level is composed of seven level-(n-1) Node-Gosper Curves, Figure 12 is composed of 7 Node-Gosper Curves of the first level blocks. Therefore, 49 two-digit numbers are used to address the level-2 Node-Gosper Curve in Figure 12. The number starts from the center (0,0), the first digit represents the cluster number of the second level, and the second digit represents the cluster number level-1. The result numbering is shown in Figure 12.

Figure 12: Numbering of level-2 Node-Gosper Curve

 

Then, as mentioned before, the Node-Gosper Curve is divided into G-type and R-type, and after substituting into L-System, a path of either G-type or R-type can be generated. We define the following rules.

 

Definition Rules:

1)     Let n be the number of levels. Number of digits = n. The number of blocks = 7ⁿ. Symbol G2=G-type second-order path. Symbol R2=R-type second-order path.

2)     The G-type rule of the path after the second order is G, R, R, G, G, G, R (as shown on the left in Figure 13).

        The R-type rule for the path after the second order is G, R, R, R, G, G, R (as shown on the right in Figure 13).

3)     The first G of G-type is the first block, the second R is the second block, ..., the seventh R is the seventh block.

         The first G of the R type is the first block, the second R is the second block, ..., the seventh R is the seventh    block.

4)     Define operation y (x₁, x₂, x₃, x₄, x₅, x₆, x₇) = (yx₁, yx₂, yx₃, yx₄, yx₅, yx₆, yx₇). For example, 5(5,4,0,6,1,2,3) = (55,54,50,56,51,52,53)

       The number of digits increases from right to left. For example, 3 in number 53 is the first digit and 5 is the second digit.

5)     Use a base-7 number system to subtract (add) the last n-1 digit. The rules are as follows:

Type G: The third block of R requires -2, the fourth block of G requires -2, and the seventh piece of R requires +2.

Type R: The fourth block of R needs -2, the fifth block of G needs +2, and the sixth block of G needs -2.

 

For example: (65,64,60,66,61,62,63) - 2= (63,62,65,64,66,60,61).

 

Figure 13: Level-2 G-type and R-Type of Node-Gosper Curve

Therefore, the L-Systems rules for Node-Gosper Curve addressing are as follows.

 

 

Because the Node-Gosper Curve of the nth level is composed of seven (n-1) levels of Node-Gosper Curve, the +2 or -2 is changed for its n-1 digits (the number of the previous level)). The reason for this change is that as the number of levels of the Node-Gosper Curve increases, its G or R type will rotate accordingly. When rotating, only the part with the center number 0 will not rotate. Therefore, the zero-free hexadecimal system is adopted. The rotation situation is shown in Figure 14.

 

Figure 14: Schematic description of L-Systems of Node-Gosper Curve

 

For example, if you want to know the addressing of the level-2 G-type and R-type Node-Gosper Curve path, you can get the following addressing path after substituting it into L-Systems, as shown in Table 3. The graph is shown in Figure 15.

 

Table 3: Addressing path of level-2 G-type and R-type of Node-Gosper Curve

 

Figure 15: Addressing path of G-type and R-type of Node-Gosper Curve

 

4.3. DATA COLLECTION OF WSN USING MOORE CURVE

 

Many space-filling curves are introduced in reference [2]. In most of the space-filling curves, it is found that they have a common point, that is, the start point and the end point are far away. If the anchor node is moved according to the pre-defined space filling curve, when collecting sensor data repeatedly in the entire sensing area, it will consume extra power to go back to the starting point again after reaching the end point.

    However, there is a very special filling curve called Moore curve. Its starting point and ending point are very close (the higher order is almost connected together), so it can collect sensing data along this route repeatedly without taking additional paths, as shown in Figure 16. The Moore curve is a deformation of the Hilbert curve in Figure 17, so it is also called the recursive Hilbert curve.

 

                 

Figure 16: Level 1 to level 6 Moore curves

 

Figure 17: Level 1 to level 6 Hibert curves

 

The L-Systems of Moore curve is shown in Table 4 [4].

Table 3: L-Systems of Moore curves

 

5.     SIMULATIONS

 

Because the mobile anchor node can repeatedly collect sensor data along the Moore curve without redundant paths. Therefore, we estimate that among many space-filling curves, the Moore curve will have good performance in terms of delay in collecting data. Under the same sensing area, we divide it into several square clusters. Let the moving anchor node moves along the three space filling curves of SCAN, Hilbert curve and Moore curve, as shown in Figure 18. The mobile anchor node moves along a predetermined trajectory and broadcasts at each cluster center point. The sensors within the sensing range of the mobile anchor receive the broadcast message and send the data to the mobile anchor node at the central point. The mobile anchor node repeatedly walks in the sensing area and collects sensor data. We study the delay performance of several space filling curves when applied to data collection.

 

Figure 18: Three space filling curves of SCAN, Hilbert curve, and Moore curve

 

5.1. SIMULATION ENVIRONMENT

 

 

 

5.2. SIMULATION RESULTS

 

The moving speed description of the mobile anchor node is shown in Figure 19, where the distance from point A to point C is the distance from the center of right cluster to the center of the left cluster, and its length is 14.1421 meters. The distances from Point A to Point B and Point B to Point Care half of the distance from point A to point C, which is 7.0710 meters.

 

Figure 19: the description of moving speed

 

At the beginning, the mobile anchor node stays at point A for 1 second to collect the sensing data of this cluster, then it starts at a speed of 0m/s, and accelerate in the middle. When it reaches point B, the speed will reach exactly 5m/s. The mobile anchor node is at Point B continues to advance at a speed of 5m/s and decelerates all the way. When it reaches point C, the speed drops to 0m/s. At this time, it stays for 1 second to collect the sensing data of this cluster.

The mobile anchor node will repeatedly walk in the entire sensing area in this way and collect sensing data. Next, we will calculate how much time it takes to move the anchor node from point A to point C. Using the following formula provided in Reference [13] will help us to perform the calculatation. First, let V₂ be the final velocity, a be the acceleration, t be the time, and x be the moving distance. Assuming the original velocity is 0:

 

 

If the initial velocity is V₁ ¹ 0, then

 

Calculating based on our simulation parameters, it takes a total of 5.6568 seconds from point A to point B.

 

One round means that the mobile anchor node starts from the starting point and returns to the starting point again after traversing the entire sensing area. However, because SCAN and Hilbert curve require additional paths to go back to the starting point, we choose the shortest straight path to let it go back to the starting point, as shown in the green straight line in Figure 20.

 

Figure 20: The returning paths (green lines) of SCAN and Hilbert curve

Therefore, we calculate the total path length of the three space filling curves for one round, and the results are shown in Table 5. The total path length of the Moore curve is the shortest.

 

Table 5: The total path length of three space filling curves for one round

 

In the simulation, we create 500 sensors generating events randomly. If the mobile anchor node walks for a round, there will be 10 sensors generating events, then the event frequency is 10. We simulated a total of five different event frequencies, each of which is a different network topology. When the three space filling curves are simulated under the same frequency of events, they all walk under the same network topology for a total of 500 rounds. We measured how long the sensor was delayed from generating an event until it sent the data to the mobile anchor node. The results are shown in Table 6 and Figure 21.

 

Table 6: the delay simulation results of the three space-filling curves

 

Figure 21: Delay simulation of the three space filling curves

It was previously calculated that the total path length of the Moore curve was the shortest. The simulation results are in line with expectations, and the delay of the Moore curve is the lowest.

 

6.     CONCLUSION

 

In this thesis, we analyzed the Node-Gosper Curve, proposed the addressing rules of its path, and applied it to the path planning of the mobile anchor node. It helped the localization of sensors and operation of data collection. In addition, we apply Moore curve to path planning of the mobile anchor nodes in WSN and to regularly collect data of the target node in the sensor network. Due to the self-loop characteristics of the Moore curve, through our simulation experiment, it proves that the Moore curve can reach each sensor to collect data faster than other space filling curves. This reduces the transmission delay of the sensor. In the future, we will change the simulation parameters, such as the speed of the mobile anchor node in the sensing network, the position of point B in Figure 19, the number of sensors, the size of the sensing area, and the radius of the cluster circumcircle. We will further analyze its impact on the collection of sensing data by mobile anchor nodes in the Moore curve.

 

SOURCES OF FUNDING

 

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

 

CONFLICT OF INTEREST

 

The author have declared that no competing interests exist.

 

ACKNOWLEDGMENT

 

None.

 

REFERENCES

 

    [1]       You-Chiun Wang, Chun-Chi Hu, and Yu-Chee Tseng, Introduction to wireless sensor networks, Communication Magazine, vol. 116, 2003 (in Chinese)

    [2]       C.-C. Chen and S.-B. Wang, “Node-gosper curve-based unknown sensor localization using single mobile anchor in wireless sensor networks,” International Journal of Distributed Sensor Networks, vol. 7, p. 13, 2016.

    [3]       V. Uher, P. Gajdoš and V. Snášel, "Proposal of Effective Orthogonal and Hexagonal Hierarchical Structures for Disc Queries," 2018 3rd International Conference on Control, Robotics and Cybernetics (CRC), Penang, Malaysia, 2018, pp. 20-26, doi: 10.1109/CRC.2018.00013.

    [4]       J. Ventrella, Brain-filling Curves - A Fractal Bestiary, http://www.brainfillingcurves.com, access on 3/21/2021.

    [5]       Richard P. Taylor & Yi-Yu Chen, Is this art or chaos, http://sa.ylib.com/MagCont.aspx? Unit=featurearticles&id=175, accessed on 4/4/2021

    [6]       You-Ching Chang, how much do you know about fractals? http://web.phys.ntu.edu.tw/physhistory/spacetime/vol_25/v25_p30.pdf, accessed on 4/4/2021

    [7]       Wikipedia, Moore curve, https://en.wikipedia.org/wiki/Moore_curve, accessed on 3/21/2021.

    [8]       Jacques M. Bahi, Abdallah Makhoul and Ahmed Mostefaoui, Hilbert mobile beacon for localisation and coverage in sensor networks, International Journal of Systems Science, No. 11, Vol. 39, 2008

    [9]       Wikipedia, Hilbert curve, https://en.wikipedia.org/wiki/Hilbert_curve, access on 4/4/2021.

  [10]     C.-C. Chen and T.-C. Lin, A Low-Cost Anchor Placement Strategy for Range-Free Localization Problems in Wireless Sensor Networks, International Journal of Distributed Sensor Networks, vol. 2013, pp. 1-12, 2013

  [11]     Chi-Chang Chen, Yukon Chang, Jui-Ying Hung, Jin-Hung Liang, "Scalable Routing Protocol for Wireless Sensor Networks Based on Gosper Islands", The Proceedings of International Computer Symposium (ICS) 2014, pp.145-154, Taichung, Taiwan, Dec. 2014.

  [12]     C. C. Chen, Y. K. Chang, J. Y. Hung, and J. H. Liang, Scalable Routing Protocol for Wireless Sensor Networks Based on Gosper Islands, The Proceedings of International Computer Symposium, pp. 145–154, 2014.

  [13]     William Moebs, Samuel J. Ling, Jeff Sanny, University Physics Volume 1, OpenStax, Houston, Texas, 2016.