Wireless Sensor
Network Fractal Geometry Node-Gosper
Curves Moore Curves Localization 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. INTRODUCTIONWireless 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].
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.
## 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.
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.
## 3. THE APPLICATION OF FRACTAL GEOMETRY IN WSNVarious
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 CURVEGosper Curve is a curve with fractal dimension of 2, which can fill a hexagonal area. Level-1 Gosper Curve is shown in Figure 8.
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].
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.
## 4.2. ADDRESSING OF NODE-GOSPER CURVEThe 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.
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
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.
1)
Let n be the number of levels.
Number of digits = n. The number of blocks = 7 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 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).
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.
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.
## 4.3. DATA COLLECTION OF WSN USING MOORE CURVEMany 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.
The L-Systems of Moore curve is shown in Table 4 [4].
## 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.
## 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.
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 If the
initial velocity is V 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.
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.
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.
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 FUNDINGThis research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors. ## CONFLICT OF INTERESTThe author have declared that no competing interests exist. ## ACKNOWLEDGMENTNone. ## 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.
[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
[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. [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.
This work is licensed under a: Creative Commons Attribution 4.0 International License © IJETMR 2014-2020. All Rights Reserved. |