The problem of an optimal coverage of a wireless sensor network area is considered. To solve this problem, a Cellular Automata (CA) approach is proposed. More specifically, the objective is to find CA rules which are able to cover the 2D space by a minimum number of so–called “Sensor Tiles”. A sensor tile consists of a von Neumann neighborhood of range 2 centered at sensor “point” and surrounded by 12 sensing “pixels”. Two probabilistic CA rules were designed that can perform this task. Results of an experimental study show that the first rule evolves very fast stable sub-optimal coverings, starting from a random configuration. The second rule finds optimal coverings, however it needs much more time for their evolution. The results are supported by a theoretical study on von Neumann neighborhoods and borrowing either from heuristics or from the spectral theory of circulant graphs.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Wireless sensor networks (WSNs) are one of the main components of currently developing Internet of Things technologies. They are used in many sectors of human activities, such as industry, agriculture, transport, environment protection or logistics to monitor critical, very often remote and difficult to access areas, to discover events or collect data which are used to take decisions. A typical WSN consists of a number of sensors located at the monitored area, and each sensor is equipped with a single use battery. It is expected that some Quality of Service criterion, typically a predefined level of coverage of the monitored area should be fulfilled. The problem of coverage assumes answering to the question: when a battery of a given sensor should be turned on to make it active and able to monitor (cover) its part of the area, having in mind that it will result in spending battery energy, in the situation when perhaps other neighboring sensors are turned on and cover partially the same part of monitored area. This problem is closely related to the other issue, WSN lifetime maximization: keeping the coverage on the requested level should be achieved by a minimal number of active sensors in order to minimize the total energy consumption and prolong this way a lifetime of WSN. With low battery consumption, the lifetime of WSN can be maximized by switching between optimal configurations of active sensors. These issues are known to be NP–hard, and a number of centralized optimization algorithms assuming existence of full knowledge about the problem and an offline execution of an algorithm, and distributed and localized algorithms to find a solution has been proposed (Thai et al. 2008; Ab et al. 2009). In this paper we suggest a novel approach to solve the coverage problem by applying cellular automata (CA). This approach belongs to the class of distributed algorithms and is based on using concurrently only local information, what gives a possibility to use it in real–time in online mode.
Our goal is to find a covering of the 2D space by so–called sensor tiles using CA. Our problem is one of the diverse covering problems (Snyder 2011) and it is related to the NP–complete vertex cover problem introduced by Hakimi (1965). A vertex cover is a set of nodes in a graph such that every edge of the graph has at least one end point in the set. A minimum cover is a vertex cover which has the smallest number of nodes for a given graph. Hakimi proposed a solution method based on Boolean functions, later integer linear programming (Gomes et al. 2006), branch–and–bound, genetic algorithm, and local search (Richter et al. 2007) were used, among others. Other related problems are the Location Set Covering Problem (Church and ReVelle 1976) and the Central Facilities Location Problem (Mehrez 1987). These problems aim to find the locations for P facilities that can be reached within a weighted distance from demand points, minimizing the number of P, or minimizing the average distance, or maximizing the coverage. For covering problems there are a lot of applications, in economy, urban planning, engineering, etc.
Anzeige
We assume that sensors are regularly located in an area to be covered, available at any discrete location of a superimposed grid. The question is how to turn them skillfully ON (active) or OFF (passive) to yield a sensor network with a minimum number of sensors, which we will call min point pattern. As shown in Fig. 1a, each active sensor (here also called point) senses a certain area in a circular range when battery is ON. Several sensors shall cover the whole space. A sensor with its range will be approximated by a discrete area (tile) (Fig. 1b).
Here, the idea is to treat the coverage problem as a pattern formation problem, where Parallel Substitution Algorithms (Achasova et al. 1994) served also as a source of inspiration. For the problem of forming a Domino Pattern we yielded already good results by using a probabilistic CA rule and overlapping tiles. In Hoffmann et al. (2021) the number of dominoes was maximized, whereas in Hoffmann et al. (2021) it was minimized. In Hoffmann (2022); Hoffmann and Seredyński (2020) the current problem of finding an optimal coverage in a WSN was already treated. We want here to follow this general approach of evolving patterns by applying a probabilistic cellular automata rule. Compared to Hoffmann and Seredyński (2020) additional material and a more effective First Rule is presented.
The following section provides the state–of–the–art on coverage issues in wireless sensor networks. In Sect. 3 the sensor tiling problem is described and optimal solutions are presented. In Sect. 4 the theoretical context in which this study takes place is described. In Sect. 5 two probabilistic CA rules are designed and their performance is evaluated in Sect. 6 before the conclusion where future explorations are proposed.
2 Related work
Fig. 1
a Sensors cover a certain area, b The circular range of a sensor is approximated by a discrete shape (in red)
The coverage problem in WSNs and the lifetime maximization problem related to it are subjects of intensive studies, the results of which can be found in the current literature (for an extensive overview, see, e.g. Yetgin et al. (2017)). A number of centralized and distributed algorithms have been proposed recently. The covering problem is computationally expensive, and exact solutions can be found only for relatively small instances of the problem with use of classical optimization algorithms, such as e.g. linear programming (Cardei et al. 2005) or integer programming (Cheng et al. 2005). For realistic instance sizes of the problem one can rely on applying some heuristic (see, e.g. (Saadi et al. 2020)) or metaheuristic which can deliver approximate, near–optimal solutions.
×
Anzeige
Currently, one of the most popular approaches to solve the coverage problem is one based on applying Nature-inspired metaheuristics, which belong to the class of centralized algorithms and require full information about a state of the system. Different versions of evolutionary algorithms were applied, in particular memetic algorithms (Liao and Ting 2018) and genetic algorithms (Charr et al. 2019; Manju et al. 2018). Another popular technique is particle swarm optimization. It was applied to solve the coverage problem considered either as a single objective problem (Jia et al. 2012; Jiao et al. 2019; Jawad et al. 2020) or multi objective problem (He et al. 2019). Two another optimization techniques like harmony search (Alia and Al-Ajouri 2017) and ant colonies were also recently applied (Rathee et al. 2021). A recent paper (Zhong et al. 2020) applies a novel approach called a metaheuristic, where with the use of the evolutionary technique of genetic programming, a high level heuristic to solve the problem is created on the base of a set of low–level heuristics.
During recent years, we can observe an increasing interest in designing distributed algorithms to solve the coverage / lifetime maximization problems in WSNs with use of learning automata (LA) or CA. These algorithms have a number of advantages in comparison with centralized algorithms. They consider a given problem as a distributed system consisting of a number of autonomous agents and focus on a description of local dependencies between agents and their actions to solve collectively a problem. Using this approach results in a more accurate description of a problem and may result in obtaining better results. What is also important, these algorithms do not require full information about a state of the system, can react on current changes of a system states, and therefore can be applied in real–time mode.
LA are a class of reinforcement learning machine algorithms and can be directly used to solve learning and optimization problems. They were applied to solve different variants of the coverage / lifetime maximization problems in WSNs, in particular by Mostafaei and Meybodi (2013); Razi et al. (2017) or Gąsior et al. (2018). Classical CA are not learning machines, and applying them to solve optimization problems requires some effort. The study presented in Tretyakova et al. (2016) is promising and shows that there exists a strong relationship between coverage levels and WSN lifetime, and specific CA rules describing the behavior of CA–based agents controlling the activation of node batteries. One possible way to provide CA with learning and optimization capabilities is to convert them into the Second Order CA, as it was proposed in Seredyński et al. (2021) and consider them as reinforcement learning machines operating in the Spatial Prisoner’s Dilemma environment or combining CA model with the spatial–temporal evolutionary process and learning automata theory like it was proposed in Lin et al. (2018). Another way is to find appropriate CA rules to solve the considered problem. Our recent work (Hoffmann et al. 2021) shows a potential of such an approach and in this paper we follow it. In this context, it is also worth to notice the work (Plénet et al. 2021) where CA–based approach to the observability problem was defined in the context of an autonomous network of mobile sensors considered as a control theory system, and oriented on an ability to reconstruct the initial system state.
3 Optimal covering with sensor tiles
3.1 The problem and its CA modeling
Given an array of \(N=(n\times n)\) cells, also called field. We assume that each cell contains a sensor which is either active or passive. The objective is to find a CA rule that can form a Sensor Coverage Pattern with a minimum number of active sensors that cover the whole area. An active sensor can cover (sense) a certain number of cells in its neighborhood. We can relate an active sensor with its sensed cells to a sensor tile as shown in Fig. 2a. A sensor tile is a discrete approximation of a real area sensed by an active sensor, as depicted in Fig. 1b. Note that sensor tiles are not automata cells, they are only used as a mean to find a cell rule and to define the covering of the space. We call the elements of a tile “pixels” in order to not confuse them with the cells of the space. A sensor tile consists of one center pixel (the kernel with the pixel value 1, in blue) and 12 surrounding pixels (the hull with value 0, in yellow). In short, a sensor tile is a certain von Neumann neighborhood of range 2.
Fig. 2
a The “Sensor Tile” as von Neumann neighborhood of range 2. b, c Some overlapping tiles with cover levels. b Four tiles with max. overlap \(v_{max} = 4\). c Four tiles with max. overlap \(v_{max} = 3\)
×
Hull pixels of different tiles are allowed to overlap, but not with sensor points. The sensor points are said to have a mutual repulsive action.
We call the number of overlapping pixels at a certain site (x, y) “overlap” or “cover level” v(x, y). Patterns with overlapping tiles are shown in Fig. 2b, c. The cover level is depicted here by numbers and colors. In the figures presented later, only numbers or colors will be used. Note that the cover level of an active sensor (in blue) is constant \(v=1\).
The cell state is modeled as \(q = s\) for the First Rule (see Sect. 5.1) and as \(q = (s, h)\) for the Second Rule (Sect. 5.2). The state s\(\in \{0, 1\}\) models an inactive/active sensor, and all sensor states build the pattern (a sensor configuration). The hit number \(h \in \{0, 1, 2, 3, 4, \texttt {[-1]} \}\) stores the number of template hits (explained later in Sect. 5.2); the last symbol in brackets denotes the repulsive action of kernels. We assume cyclic border conditions in order to simplify the problem. Constant zero–boundaries of width 2 could also be used in order to keep the sensor points within certain borders. In the case of a fixed border, an appropriate number of hits has to be assumed for the border cells (e.g., \(h=1\)), because the later described Second Rule reads hits from them.
3.2 Optimal solutions
Table 1
Valid sensor patterns (solutions) found for different field sizes. The table presents the number of sensor tiles, the maximum overlap in the set of solutions, and the density of sensors (point density). Notation for the max overlap values: M(a) means \(\left| {v_{{{\text{max}}}} = M} \right|\) = a; M(a; b; c) means \(\left| {v_{{{\text{max}}}} = M} \right|\) = a; b; c; M(a::b) means a _ \(\left| {v_{{{\text{max}}}} = M} \right|\) _ b, and M(+) means \(\left| {v_{{{\text{max}}}} = M} \right|\) _ 1. On the right, three solutions with 7 tiles with different \(v_{{{\text{max}}}}\) are shown. Active sensors are shown in black, inactive in white
We call a coverage valid, if the sensor tiles cover the whole space without gaps (uncovered cells). There are valid coverages/patterns with a different number of active sensors, between a minimal and a maximal number (as you can see later in Fig. 3). We call a valid coverage with a minimal number of active sensors min sensor pattern (for short min pattern), and a coverage with a maximal number max sensor pattern (for short max pattern). In this paper, we are interested in min patterns, but max patterns will also be considered. Note that there exist many equivalent sensor patterns taking into account the symmetries: translation, rotation, and reflection. When we speak of a pattern, we mean any representative in the class of equivalent patterns.
Using the CA rules described later, valid sensor patterns covering the whole space were found. They are listed in Table 1 for different field sizes. This table presents the number L of sensor tiles (equal to the number of points p), the maximum overlap \(v_{max}\) in the set of solutions, and the density \(R(N)=p/N\) of sensors (point density). E.g. for \(N= (7 \times 7)\), there are 5–tile patterns with (a) \(|v_{max}=2|\ge 1\) (several sites have overlap 2), (b) \(|v_{max}=3|=1\) (only one site has overlap 3), (c) \(|v_{max}=4|=4\) (four sites have overlap 4). The minimal point density for this example is \(R_{min}(49)=5/49=0.102\), and the maximal density is \(R_{max}(49)=8/49=0.163.\) Recall that we search for min point patterns with a minimal point density.
Fig. 3
Minimal sensor patterns (upper half), maximal sensor patterns (lower half). A black square represents a sensor point, and the numbers give the overlap level. Field sizes range from \((3 \times 3)\) to \((10 \times 10)\)
Fig. 4
a\(11 \times 11\) Min pattern with 11 points. b\(13 \times 13\) Min pattern with 13 points
×
×
Some min and max sensor patterns are shown in Fig. 3. The following min and max pattern were found (Table 1):
\((3 \times 3):\) There is only one solution.
\((4 \times 4):\) There are two solutions, each with two points. The maximal overlap level is 3 (appears twice) for the upper one (\(|v_{max}=3|=2 \Leftrightarrow v_{max}=3(2)\)), and 4 for the lower one (\(v_{max}=4(2)\)). There is no special min pattern.
\((5 \times 5):\) A min pattern with 3 and a max pattern with 5 points exist, but no pattern with 4 points. Note that there exists one cell with cover level of 3 in the min pattern, and there is no min pattern with \(v_{max}=2\) as we can find for \(n= 6\)–10.
\(n=6, 7,8\) and 9, 10, 11 : There exist min–max patterns with 4–6, 5–8, 7–10 and 8–13, 8–20, 12–22 points.
\((10 \times 10):\) It was difficult to discover the min 8 point pattern shown in Fig. 3 (top right). You can observe 4 cells there with cover level 2. They define a square of size \((5 \times 5)\), and they are placed in the middle of a horizontal or vertical pair of sensors. After extensive search, no valid pattern with 19 points could be found. It remains an open question if there exists such a pattern. The point number range is large (8–20), therefore this field size was used as a test scenario for the rules described in the following.
\((11 \times 11):\) There exists a regular min pattern (Fig. 4a) with 11 points that is difficult to evolve by the later described CA rules.
\((13 \times 13):\) There exists a regular min pattern (Fig. 4b) with 13 points with cover level 1 everywhere. So it can be named “absolute” min pattern because there exists no overlap at all. Obviously, multiples of size 13 yield such a pattern, too. The point density reaches the absolute minimum of \(R_{min}^{abs}(13)=1/13\). For comparison, the absolute maximal point density is \(R_{max}^{abs}(5,10,...)=1/5\) for \(5\times 5\)max patterns with 5 points, and multiples thereof, e.g. for the \(10\times 10\)max pattern.
4 Theoretical background
4.1 Tiling the plane with von Neumann neighborhoods of range r
In 2d cellular automata, the von Neumann neighborhood of range r at point \( ( x_0, y_0 ) \) is the set of cell centers defined by
$$\begin{aligned} {\mathcal {N}}^{\, r }_{ ( x_0,\, y_0 ) } = \{ ( x, y ) : \ | x - x_0 \ | + \ | y - y_0 \ | \le r \} \qquad ( r \in {\mathbb {N}} ) \end{aligned}$$
at a Manhattan distance \( d ( ( x, y ) , ( x_0 , y_0 ) ) \le r . \) The cardinality of this neighborhood, hereafter referred as r–neighborhood, is the centered square number
illustrated in the inset of Fig. 5 for the first usual values of \( r > 0 \) (the 0–neighborhood is the trivial point \( \{( x_0, y_0 ) \}). \) Von Neumann’s 2d neighborhoods define a family of polyominoes, that are “prototiles” which perfectly tessellate1 the plane.
The labeling scheme is defined from a generating set \( ( s_{ 1 }, s_{ 2 } ) ( r ) \) and must satisfy that \( s_{ 1 }, s_{ 2 } \) and \( {\mathbf {n}}_r \) be pairwise coprime (Yebra et al. 1985). A usual choice is to set \( ( s_{ 1 }, s_{ 2 } ( r ) ) = ( 1, 2 \, r + 1 ): \) the first direction (horizontal) is generated by the infinite sequence \( ( 0, 1, 2,... , {\mathbf {n}}_r - 1 ) \) of elements of \( {\mathbb {Z}} / {\mathbf {n}}_r {\mathbb {Z}} \) with 0 at the center of the prototile, whence the generation of the second sequence (vertical) is deduced. Thus, a cell c is adjacent to cells \( c \pm 1 \pmod {{\mathbf {n}}_r} \) according to the first direction of generators and is adjacent to cells \( c \pm (2\,r + 1) \pmod {{\mathbf {n}}_r} \) according to the second direction. This adjacency relation is formally depicted by the circulant graphs \( {\mathcal {C}}^{ s_{ 1 } s_{ 2 } ( r ) }_{ {\mathbf {n}}_r } \) – namely \( {\mathcal {C}}^{ 1, 3 }_{ 5 } \hbox { and } {\mathcal {C}}^{ 1, 5 }_{ 13 } \) – of Fig. 6. They are Cayley graphs and therefore have the property of being vertex–transitive (Boesch and Tindell 1984; Monakhova et al. 2020).
Fig. 5
Tiling the plane from prototiles as von Neumann neighborhoods: (Left) of range \( r = 1 \) and size \( {\mathbf {n}}_1 = 5 \); (Right) of range \( r = 2 \) and size \( {\mathbf {n}}_2 = 13 \)
Fig. 6
Circulant graphs \( {\mathcal {C}}^{ s_{ 1 } s_{ 2 } ( r ) }_{ {\mathbf {n}}_r } \) with \( {\mathbf {n}}_r \) vertices labeled \( ( 0, 1, 2,... , {\mathbf {n}}_r - 1 ) \) and the generating set \( \{ s_{ 1 } = 1, s_{ 2 } ( r ) = 2\,r + 1 \}. \) Any vertex c is connected to \( c \pm s_{ 1 } \) and \( c \pm s_{ 2 } ( r ) \pmod {{\mathbf {n}}_r}. \) Connectivity in \( {\mathcal {C}}^{ 1, 3 }_{ 5 } \) and \( {\mathcal {C}}^{ 1, 5 }_{ 13 } \) is the image of adjacency in the above tiling
×
×
The adjacency matrices \( M_{ {\mathbf {n}}_r } \) associated with the (von Neumann) r–circulant \( {\mathcal {C}}^{ s_{ 1 } s_{ 2 } ( r ) }_{ {\mathbf {n}}_r } \) have handsome spectral properties (Davis 1970). They are bisymmetric and the simple knowledge of coefficients \( c_{ 1 } , c_{ 2\,r + 1 } \) in the first row \( c_{ 0 } , c_{ 1 } , c_{ 2 } , \ldots , c_{ {\mathbf {n}}_r - 1 } \) suffices to determine the set of eigenvalues. Thereby \( c_{ 1 } = c_{ 2\,r + 1 } = 1 \) and
where \( \uplambda _{ {\mathbf {n}}_r , \,k } \) denotes the k–th eigenvalue of matrix \( M_{ {\mathbf {n}}_r } . \) For a given \( r > 0 \) there exists a unique maximal eigenvalue \( \uplambda _{ {\mathbf {n}}_r , \,0 } = 4 \) that denotes a 4–regular graph and there exist \( ( {\mathbf {n}}_r - 1 ) / 4 \) equivalence classes with 4 equal eigenvalues and such that
for \( M_{ 13 } \). In particular, the spectrum highlights the rotational symmetry of the prototiles in Fig. 5 and by comparing with (Yebra et al. 1985), one could verify that the set of eigenvalues does not depend on the chosen labeling scheme.
The vertex–transitivity implies that any window of size \( {\mathbf {n}}_r \times {\mathbf {n}}_r \) and embedded into this cellular space will contain exactly \( {\mathbf {n}}_r \) distinct cells \( c \in {\mathbb {Z}} / {\mathbf {n}}_r {\mathbb {Z}} \) whatever the position of the window. Moving the window by a vector \( (\alpha ,\beta ) \) turns into the automorphism \( \tau _{ \alpha \beta } \) mapping \( {\mathbb {Z}} / {\mathbf {n}}_r {\mathbb {Z}} \) into itself as
$$\begin{aligned} c \mapsto \tau _{ \alpha \beta } ( c ) = c + ( \alpha s_1 + \beta s_2 ( r ) ) = c + \alpha + ( 2\, r + 1 ) \beta \pmod {{\mathbf {n}}_r} \end{aligned}$$
for any \( c \in {\mathbb {Z}} / {\mathbf {n}}_r {\mathbb {Z}}. \) This therefore defines a \( {\mathbf {n}}_r \times {\mathbf {n}}_r \) wrap–around toroidal topology that provides the exact number \( {\mathbf {n}}_r \) of required sensor points. For any multiple \( n = p \cdot {\mathbf {n}}_r \) this property remains true, that is, with \( p^{\,2\, } {\mathbf {n}}_r \) sensor points.
4.2 Min–coverage problem
For other sizes \( n \times n \) further analysis should be carried out. The perfect tiling will then give way to patterns with overlapped prototiles. Let \( V_n = ( v_{ i j })_{ \, 1 \le \, i, j \, \le n } \) therefore be the coverage matrix where element \( v_{ i j } = v \, ( x, y ) \) denotes the cover level at site (x, y) . Let \( \sigma _{ n } \) be the number of “\( {\mathbf {0}} \)” in the \( n \times n \) field –the number of “sensor points”– for a given configuration. Then \( \sigma _{ n } \) also denotes the number of prototiles and we consider the rational \( n^2 / {\mathbf {n}}_2 \) surrounded by the two consecutive integers \( \sigma _{ n } - 1 \) and \( \sigma _{ n } \) such that
$$\begin{aligned} \sigma _{ n } - 1 < \frac{ n^2 }{ {\mathbf {n}}_2 } \le \sigma _{ n } \hbox { with } \quad \quad {\mathbf {n}}_2 \, \sigma _{ n } = \sum _{ i, j } v_{ i j } \end{aligned}$$
(3)
and where the sum in matrix \( V_n \) denotes the global cover index with \( \sigma _{ n } \) points. It follows that \( \sigma _{ n } \) defines a lower bound for the required number of points in the \( n \times n \) field. However, in most cases this rough lower bound is not a tight bound and the values of \( \sigma _{ n } \) displayed in Table 2 are often lower than those provided by the simulation. This theoretical inadequacy results from the fact that the toroidal constraint is not taking into account. A heuristic framework is presented, applied for any n\( ( 3 \le n < 13 ) \) and illustrated in Appendix \( A_1 \). The four following primitives are stated thereafter. The result is the formation of valid min patterns for almost all values of n.
The heuristic evolves more or less easily depending on whether or not there exists some “affinity” between n and \( {\mathbf {n}}_2 \). The 4–fold rotational symmetry initiated at the beginning is conserved throughout evolution for \( n = 3, 7, 10 \) and is eventually achieved for \( n = 6 \). It can be checked that the relation \( {\mathbf {n}}_2 \cdot \sigma ^{ *}_{ n } \equiv _4 n^2 \) holds for those cases.
For \( n = 4 \) the case is somewhat trivial: at least 2 points are expected from (3), now a \( n \times n \) torus has diameter n for n even and there exist \( \sigma ^{ *}_{ 4 } = 2 \) antipodals at distance 4.
The symmetry is broken for \( n = 5, 8, 9 \) but an optimal pattern is easy to achieve.
For \( n = 12 \) the symmetry holds until the penultimate step, that is, until a single point is added. Indeed, we can observe that \( {\mathbf {n}}_2 \cdot ( \sigma ^{ *}_{ n } - 1 ) \equiv _4 n^2 \) holds for this case.
————————————–
Initialize (n, \( \sigma _{ n }( 0 ) \))
————————————–
// Define a \( n \times n \) window with 4–fold rotational symmetry :
// For n odd the center is the \( {\mathbf {0}} \)–kernel of a centered prototile, surrounded by a maximum of prototiles whose kernels are strictly inner to the \( n \times n \) window
// For n even (\( n > 4\)) the center is the \(\left[ \mathbf {2,3,10,11}\right] \)\( 2 \times 2 \) square, surrounded by a maximum of prototiles whose kernels are strictly inner to the \( n \times n \) window; for \( n = 4 \) the pattern is empty
\( \sigma ^{ *}_{ n } = \sigma _{ n }( 0 ) \) // initial number of points
————————————–
Set_PBC (\( n, \{( i, j )\} [, \texttt {pbcl} ] \))
————————————–
// From the inner (i, j) kernel, fix the periodic boundary conditions (PBC) generating the four N–S and E–W outer images \(( i, j \pm n)\) and \(( i \pm n, j )\) as well as the four NW–SE–NE–SW\(( i \pm n,j \pm n)\) outer images
// {( i, j )} : List of kernels
// pbcl: Number of points lost by PBC sequence ;
the empty parameter is the default ( pbcl = 0 )
\( \sigma ^{ *}_{ n } \leftarrow \sigma ^{ *}_{ n } - \texttt {pbcl} \)
————————————–
Add_P (n, (i, j) )
————————————–
// Add a new prototile centered at (i, j) and propagate PBC
\( \sigma ^{ *}_{ n } \leftarrow \sigma ^{ *}_{ n } + 1 \)
————————————–
Move_P (\( n, \{ ( i, j ) \), dir })
————————————–
// Move the (i, j) –prototile to one of the N–S–E–W direction dir and propagate PBC
// {(i, j), dir } : List of movings
————————————–
Surprisingly, this heuristic evolves badly for \( n = 11 \). Although it could lead to a pattern with \( \sigma '^{ *}_{ 11 } = 13 \) points without too much difficulty (it can be checked that relation \( {\mathbf {n}}_2 \cdot \sigma '^{ *}_{ n } \equiv _4 n^2 \) holds), this pattern is far from optimal. The question arises whether this complexity could explain the excessive time required by the simulations for this particular value, as highlighted in the sequel, in Table 5.
Observing for \( n = 11 \) that \( n^2 = n\, ( {\mathbf {n}}_2 - 2 ) \) could suggest a possible tessellation of the \( n \times n \) field by some n–prototile. Again, the adjacency matrices \( M_{ 11 } \) are bisymmetric and the simple knowledge of the two first coefficients is needed. An exhaustive examination shows that there exist exactly \( \sum _{ k = 1 }^{ 4} k = 10 \) circulants
$$\begin{aligned} \uplambda _{ n, \,k }= & {} 2 \cos \left( \frac{ 2 \, \mu \, k \, \pi }{ n } \right) + 2 \cos \left( \frac{ \, 2 \, \nu \, k \, \pi }{ n } \right) \\&\quad ( 0 \le k \le n - 1 ) \ \ \ ( n = 11 ) \end{aligned}$$
where \( \uplambda _{ n, \,k } \) denotes the k–th eigenvalue of matrix \( M_{ n }^{ \, \mu , \, \nu } . \) Dividing the circulants into the two classes \( \overline{ {\mathcal {C}}}_{ 1 }, \overline{ {\mathcal {C}}}_{ 2 } \) results from simple trigonometric transformations. Each class \( \overline{ {\mathcal {C}}}_{ 1 } ( \hbox {resp. } \overline{ {\mathcal {C}}}_{ 2 } ) \) has its own minimum (negative) eigenvalue \( {\overline{\uplambda }}_{ 1 } ( \hbox {resp. } {\overline{\uplambda }}_{ 2 } ) \) and the criterion \( {\overline{\uplambda }}_{ 2 } < {\overline{\uplambda }}_{ 1 } \) yields the min valid patterns in \( \overline{ {\mathcal {C}}}_{ 2 } . \) The whole set of circulant \( {\mathcal {C}}_{ 11 } \) with their respective pattern is displayed in Appendix \( A_2 \) (Figs 24, 25).
Fig. 7
Valid \( n \times n \)min patterns \( ( 3 \le n < 13 ) \) resulting either from heuristic or from spectral theory. Each cell is “decorated” from its von Neumann label of Fig. 5. The number of labels at site (x, y) is the cover level \( v_{ i j } = v \, ( x, y ) \) with one color per eigenvalue in matrix \( M_{ {\mathbf {n}}_2 }. \) The patterns are consistent with the results of the simulations in Figs. 3–4. They perfectly match for \( n = 3 \), \( n = 6 \), \( n = 10 \) and now \( n = 11 \)
Fig. 8
Decorated pattern of the max problem in the infinite plane. Each tile is decorated from its 2–von Neumann label of Fig. 5. The number of labels is the cover level, namely \( v_{ i j } = 1 \) for the kernel and \( v_{ i j } = 3 \) for the hull everywhere and with one color per eigenvalue in matrix \( M_{ {\mathbf {n}}_2 }. \) This tiling is isomorphic to the 1–von Neumann tiling of Fig. 5
Table 2
Exact minimal number \( \sigma _n^{*} \) of “points” expected from the simulation model. A first estimation of the lower bound \( \sigma _{ n } \) is derived from (3). The quantity \( \sigma _{ n }( 0 ) \) denotes the initial value in the heuristic. The sum of cover levels in the penultimate row equals the global cover index \( {\mathbf {n}}_r \cdot \sigma _n^{*} \). All \( \sigma _n^{*} \) result from heuristic except \( \sigma _{ 11 }^{*} \)
n
3
4
5
6
7
8
9
10
11
12
13
\( n^2 / {\mathbf {n}}_2 \)
0.69
1.23
1.92
2.77
3.77
4.92
6.23
7.69
9.31
11.08
13.00
\( \sigma _{ n } \)
1
2
2
3
4
5
7
8
10
12
13
\( \sigma _{ n }( 0 ) \)
1
0
1
4
5
4
5
8
9
12
13
\( \sum _{ i, j } v_{ i j } \)
13
26
39
52
65
91
104
104
143
169
169
\( \sigma _n^{*} \)
\( {\mathbf {1}} \)
\( {\mathbf {2}} \)
\( {\mathbf {3}} \)
\( {\mathbf {4}} \)
\( {\mathbf {5}} \)
\( {\mathbf {7}} \)
\( {\mathbf {8}} \)
\( {\mathbf {8}} \)
\( {\mathbf {11}}\)
\( \mathbf { 13 }\)
\( \mathbf { 13 } \)
×
×
Resulting either from heuristic or from spectral theory, a set of min valid patterns \( ( 3 \le n < 13 ) \) is displayed in Fig. 7. Each cell is “decorated” from its von Neumann label of Fig. 5. The number of labels at site (x, y) is the cover level \( v_{ i j } = v \, ( x, y ) \) with one color per eigenvalue in \( M_{ {\mathbf {n}}_2 }. \) The patterns are consistent with the results of the simulations in Figs. 3–4. They perfectly match for \( n = 3 \), \( n = 6 \), \( n = 10 \) and now \( n = 11 \). The number \( \sigma _n^{*} \) of points appears in the last row of Table 2.
4.3 Equivalence between Min and Max coverage problems
We close this theoretical framework by pointing out a relation between our problems of minimization and maximization. Basically, our min problem could be associated with a physical distancing configuration while our max problem could be associated with a tightly–coupled configuration and the objective function thus becomes the search for the optimal number \( \sigma _{ n } \) of points in both cases. For simplicity we consider the infinite plane and assert thereby that the pattern must be biperiodic. Obviously for the max problem, trying a 4–fold coverage of the whole hull will prove to be impossible due to the repulsive action of the kernel. Therefore the maximal suitable solution is a 3–fold coverage of the whole hull as suggested in Fig. 3 and illustrated on the decorated pattern of Fig. 8. It follows that solving the min–problem in the 1–neighborhood amounts to solve the max–problem in the 2–neighborhood. By extension, we conjecture that there would exist a close relationship between solving the min–problem in a r–neighborhood and solving the max–problem in the \( ( r + 1 ) \)–neighborhood, shortly: \( min_{ r } \cong max_{ r + 1 } \) with of course an additional condition for a finite field.
We refer back to inequalities in (3) and assume that equality holds for \( {\mathbf {n}}_r = {\mathbf {n}}_1. \) On the other hand, let
that means (i) for the min–problem, all \( n \times n \) sites take on value “1” regardless of their state either of kernel or of hull (ii) for the max–problem, all \( \sigma _{ n } \) kernel points take on value “1” while the remaining \( ( n^2 - \sigma _{ n } ) \) hull sites take on value “3”. It follows that
First, as a matter of principle, we have to decide (i) whether to use a synchronous or an asynchronous updating scheme, and (ii) whether to use a deterministic or a probabilistic rule. This makes four options: (1) synchronous updating & deterministic rule, (2) synchronous updating & probabilistic rule, (3) asynchronous updating & deterministic rule, and (4) asynchronous updating & probabilistic rule.
We have to keep in mind that we search for a CA rule that converges always or with a high probability to optimal or near–optimal patterns. From our previous work we have learned that it is very difficult or even impossible to design such a rule with Option 1 because we may have to avoid or dissolve conflicts, deadlocks, live–locks, and emerging oscillating, moving or clustering structures, as we know, e.g. from the Game of Life, in order to drive the pattern continuously to an optimum (not to get stuck in suboptimal solution areas).
The remaining options (2–4) are related because the computation of a new configuration is stochastic. It seems that they can be transformed into each other to a certain extent. Here we want to use Option 4 because we have gained good results in solving another problem (Hoffmann et al. 2019) in this way. Moreover, we don’t need a clock for synchronization and buffering for the configuration, which is closer to the modeling of natural processes. In contrast to that former solved problem, we address here another difficult problem where the number of tiles is minimized and not maximized.
5.1 The first rule
Fig. 9
a The 13 templates \(A_i\) of the sensor tile. The value \(\textit{refval}(A_i)\) of the reference pixel (marked in red) is used for cell updating in the case that all remaining template pixels (the neighborhood template) match with the corresponding cells of the current configuration. b The neighborhood templates \(A_i^*\). The dotted box marks the \((5 \times 5)\)–window used for matching. The remaining neighborhood templates result from rotation of the shown ones. c\(A_{10}^*\) represented as an array reduced from \((9 \times 9)\) to \((5 \times 5)\)
The idea is to modify the current configuration systematically such that valid patterns appear and at last a min pattern. To do this, the CA configuration is searched for tile parts (specific local patterns) and if an almost correct tile part is found, it is corrected, otherwise some random noise is injected.
×
The tile parts are called templates\(A_i\). They are systematically derived from the sensor tile (Fig. 9a). For each of the 13 tile pixels (so–called derivation pixels, marked in red) a template is defined by shifting the tile in a way that the derivation pixel appears in the center. Note that many of these templates are similar under various symmetries: \(A_3, A_4, A_5\) are rotations of \(A_2\); \(A_7, A_8, A_9\) are rotations of \(A_6\) and \(A_{11}, A_{12}, A_{13}\) are rotations of \(A_{10}\).
We represent a template\(\mathbf{A} _\mathbf{i} \) as an array of size \((k \times k)\) of pixels, where \(k = 2m-1\) and \((m \times m)\) is the size of the tile, enlarged to a square box embedding it. Our tile is of size \((5 \times 5)\) including empty pixels, and the templates are larger because of shifting, maximal of size \((9 \times 9)\). The pixels within a template are identified by relative coordinates \((\varDelta x ,\varDelta y)\). The center pixel at \((\varDelta x ,\varDelta y) = (0,0)\) is called “reference pixel”. Each template pixel carries a value \(val(A_i, \varDelta x ,\varDelta y) \in \{0,1,\#\}\). The value of the reference pixel is called “reference value”, \(refval (A_i)= val (A_i, 0 ,0) \in \{0,1\}\), which is equal to the value of the derivation pixel. The symbol # represents “Don’t Care”, meaning that a pixel with such a value is not used for matching (or does not exist (empty pixel) in another interpretation). Pixels with a value 0 or 1 are valid pixels, their values are equal to the values derived from the original tile. Some templates can be embedded into arrays smaller than \((k \times k)\) when they have Don’t Care symbols at their borders.
We need also to define the term “neighborhood template” that is later used in the matching procedure. The neighborhood template \(A_i^*\) is the template \(A_i\) in which the reference value is set to #, in order to exclude the reference pixel from the matching process. The cell processing scheme is:
At time–step t a new configuration is formed by updating N cells in a random order. For each time–step a new random permutation is used. The new configuration is complete after N cell updates (each cell is updated once during this period) and it defines the next configuration at time–step \(t+1\).
The rule is applied asynchronously. The new cell state \(s'=f(s, B^*)\) is computed and immediately updated without buffering. \(B^*\) denotes the states of the neighbors within a local window, where the center cell s(x, y) is excluded for matching.
The neighborhood templates \(A_i^*\) are tested against the corresponding CA cell neighbors \(B^*(x,y)\) in the current \((5 \times 5)\)–window at position (x, y). Thereby the marked reference position \((\varDelta x ,\varDelta y) = (0,0)\) of a neighborhood template is aligned with the center of the window. Note that we use for testing a window of size \((5 \times 5)\) which is smaller than the full size \((9 \times 9)\) of the neighborhood templates. Therefore, some valid pixels outside the \((5 \times 5)\)–window are not tested (e.g. the bottom 4 yellow pixels of \(A_{10}^*\) in Fig. 9b). The implementation with these incomplete neighborhood templates worked very well, but further investigations are necessary for proving to which extent they can be incomplete.
If all values of a neighborhood template \(A_i^*\) match with \(B^*(x,y)\) then we register a hit that is stored only temporarily. There can be several hits equal to the number of matching templates. The number of hits approximates the cover level and is equal to it when the pattern becomes stable. If we have at least one hit (Rule part (b)), the sensor state of the current cell s(x, y) is set to the reference value \(\textit{refval}(A_i)\) and then we create or validate a correct tile part in the current \((5 \times 5)\)–window. Otherwise we could not find or adjust a correct tile and the local pattern is noisy. Then we inject additional noise (Rule parts (c),(d)) at the current cell position (x, y) in expectation to form a valid tile.
If the current state is 0 we change it to 1 with probability \(\pi _0\), and if it is 1 we change it to 0 with probability \(1-\pi _0\). The idea behind is to inject “asymmetric” noise in order to force the evolution into more white or more black cells. Using a low probability \(\pi _0\) means that white cells mainly stay white, whereas black cells (sensor points) are mainly forced to get white in order to disappear. Note that the cell’s state may remain unchanged as default (Rule part (a)) if none of the conditions in (b), (c), (d) triggers an update. The lowest point density have min pattern of field size (\(13 \times 13\)) or multiples thereof, with a point density of \(1/13=0.077\). So we may choose this density for \(\pi _0\) in order to drive (hopefully) the evolution to min patterns.
There can be no conflicts, because the reference value is the same (uniquely derived from the tile) if there are several hits. (Examples: If \(A_1^*\) matches, there is one hit only, and the reference value is 1. If \(A_{10}^*, A_{11}^*, A_{12}^*, A_{13}^*\) match, we get 4 hits with reference values 0). As no conflicts can arise, the sequence of testing the templates does not matter, and one could skip further tests after a first hit.
It is important to note that this rule obeys the criterion of stability, which means that a valid pattern without gaps (uncovered cells) is stable because we have matching hits at every site. Otherwise, some asymmetric random noise is injected in order to drive the evolution to the aimed pattern.
5.1.1 Testing the first rule
Fig. 10
A \((10 \times 10)\) simulation sequence yielding a stable pattern with 15 points, using the First Rule with \(\pi _0=0.5\). Colors: blue (active sensor), white (not covered by a tile), yellow (cover level 1), light green (cover level 2), green (cover level 3)
Table 3
10 000 runs were performed on \((10 \times 10)\) fields with the First Rule for different probabilities \(\pi _0\). The pattern frequency (the number of evolved patterns with a certain number of points) is given. The average number of points \(p_{average}\) and the average number of time–steps \(t_{average}\) are also presented. The patterns evolve very quickly and remain stable. In order to evolve patterns with a few points the probability \(\pi _0\) should be kept low
Points
Pattern frequency [1/1000]
\(\pi _{0}=0.5\)
\(\pi _{0}= 0.2\)
\(\pi _{0}=0.09\)
\(\pi _{0}=0.077 = 1/13\)
\(\pi _{0}= 0.02\)
\(\pi _{0}= 0.01\)
8
0
0
0
0
0
0
9
0
0
0
0
0
0
10
0
0
3
2
1
4
11
0
16
31
36
32
38
12
10
314
470
461
514
540
13
396
2002
2415
2446
2600
2626
14
2470
4238
4142
4219
4146
4123
15
4590
2858
2475
2399
2333
2261
16
2249
540
446
417
358
385
17
205
28
15
18
14
21
18
62
3
3
2
2
2
20
18
1
0
0
0
0
Average # of points
14.96
14.13
13.99
13.98
13.93
13.92
t\(_{average}\)
16.72
3.21
2.30
2.22
2.00
1.99
10,000 runs were performed on (\(10 \times 10\))–fields with random initial configurations and a time–limit of 100 iterations, with different probabilities \(\pi _{0}=0.5, \, 0.2, \, 0.09, \, 0.077, \, 0.02, \, 0.01\). The CA system converges quickly to a stable sub–optimal sensor pattern after \(t_{average}=16.72 - 1.99\) time–steps on average (Table 3). We observe in Fig. 10 how fast a stable pattern with 15 points can evolve. The evolution is faster for lower \(\pi _0\).
×
All patterns cover the space as required. Most often the patterns contained 14 points. The average number of points (\(14.96 \rightarrow 13.92\)) decreases with the probability \(\pi _0\). The reason is that the probability \(1-\pi _0\) for injecting zeroes is then higher (favoring low cover levels) than the probability \(\pi _0\) for injecting ones (favoring points). No min pattern with 8 points and even no pattern with 9 points was found during 10 000 runs. A few near–min patterns with 10 points evolved for \(\pi _0=0.09 - 0.01\). Max patterns were found only for high probabilities \(\pi _0=0.5, 0.2\). We can conclude that min sensor patterns are very rare in the whole set of all valid patterns covering the space. We have chosen the probability \(\pi _0=0.01\) for the following work because the average number of points is lower than for \(\pi _0=1/13\), the value that we first expected to give the best results.
We can conclude that we have found a CA rule that can evolve valid sensor point patterns, but unfortunately the number of active sensors is not necessarily minimal. What is the reason? The rule evolves patterns that fulfill one of the two conditions for each cell at (x, y):
1.
\(s(x,y)=1 \wedge \forall (\varDelta x,\varDelta y): s(x+\varDelta x,y+\varDelta y)=0\), where \((\varDelta x,\varDelta y) \in \) set of relative coordinates of the hull pixels, and where the point tile’s center \((\varDelta x,\varDelta y)=(0,0)\) is excluded. This condition means that a sensor point finds only zero–state cells in its beams.
2.
\(s(x,y)=0 \wedge \exists (\varDelta x,\varDelta y): s(x+\varDelta x,y+\varDelta y)=1\), where \((\varDelta x,\varDelta y) \in \) set of relative pixel coordinates of any template (centered at \((\varDelta x,\varDelta y)=(0,0)\)), and where the templates’ centers \((\varDelta x=0,\varDelta y=0)\) are excluded. Don’t Care pixels shall not contribute to this set. This condition means that each zero–state cell is at least covered by one sensor point’s beam, or in other words a zero–state cell is connected to a sensor that senses it.
These two conditions are only necessary conditions for valid coverages, but not sufficient to define min patterns. It seems to be quite difficult to find local logical conditions that ensure a global minimum of points, except for special cases like \(n=13\) where there is only one optimal solution with cover level \(v=1\) everywhere (Fig. 4b). For that special case the second condition can be defined more strictly (“... exists exactly one...”) as
Now we need to improve our CA rule in order to evolve min patterns with a high probability.
5.2 The second, improved rule
The purpose of this enhancement is to improve the rule in such a way that the number of points reaches a minimum. Whereas the first rule works with the state \(q = s\) only, now the state is extended by the number of hits h, thus the full state \(q = (s,h)\) is used. Now all neighborhood templates are tested and all hits are stored for every site (x, y). The number of hits h(x, y) is:
0 : no neighborhood template matches or there is a gap.
1 : one neighborhood template matches where the reference value is zero (yellow colored).
2–4 : h neighborhood templates match with reference values zero, that means that 2–4 tiles (yellow hull pixels) are overlapping.
[-1] : the neighborhood template \(A_1^*\) matches where the reference value is 1 (blue). Recall that blue pixels are not allowed to overlap. The symbol in brackets denotes the repulsive action of kernels.
The hit number h(x, y) holds the actual value after matching with all the neighborhood templates. Because of the random sequential updating scheme, the h–values in the (x, y)–neighborhood may not be up–to–date and can carry old values from the former configuration at time–step \( t-1\). Nevertheless, the h–values correspond mainly to the cover levels v, especially when the pattern becomes more stable. This inaccuracy introduces some additional small noise which can even speed–up the evolution. And when the pattern becomes stable, the hit number equals the cover level: \(\forall (x,y):h(x,y)=v(x,y)\).
The idea is to minimize the overlap between tiles by destroying cell states with high overlap level (\(h > 1\)) through noise, allowing reordering with a lower number of points. In order to find a rule, we need to study the min point patterns with respect to their overlap values and local situations. From Table 1 and Fig. 3 we can see that min patterns contain some cells with a max overlap \(v_{max} = 2, 3\). (There is a special case with \(n = 13\) or multiples of 13 where there exists a pattern with \(v_{max} = 1\) that we will not be taken into consideration here.)
First the new state \(s'(x,y)\) is computed according to the First Rule, and additionally, the number of all hits h(x, y) is computed and stored. Then the new state is modified to \(s''(x,y)\):
The conditions \(C_{1..3}\) add additional noise in order to drive the evolution to the optimum when the local hit density is above a certain level. It was quite difficult to find these conditions through many trial and error simulations taking into account the local patterns in \((3 \times 3)\)–windows of valid optimal and near–optimal solutions. It would be interesting to find better conditions through further research. The ultimate goal is to find a rule that always drives to a stableoptimal solution, not excluding any solution from the set of all possible solutions.
The function \(hits3\texttt {x}3(x,y)\) computes the sum of the hits of inactive cells in a local \((3 \times 3)\)–window with its center at (x, y), where active sensor cells and the center are discarded. The function \(Active3\texttt {x}3(x,y)\) computes the sum of active cells in a \((3 \times 3)\)–window.
Now, for this improved rule, it is not clear whether the stability criterion is still fulfilled because of the additional noise. In fact, it turned out that reached min patterns are often stable, although some non–min patterns can be stable, too. Extensive simulations showed that noise injection under these additional conditions drive non–min patterns to min patterns. Unfortunately, at the moment, we cannot show that the evolution always ends up with a stable min pattern, because (a) we cannot prove that all reached valid non–min patterns are transient (meaning that then further noise will still be injected), and (b) that all reached min patterns are stable (meaning that then noise injection is always stopped).
A deeper analysis is a subject to further research. It remains an open question, whether a local CA rule can be found that always drives the evolution to a min point pattern, and preferably to any of all possible min patterns, not excluding solutions with a certain max cover level or certain local sensor arrangements.
During a simulation, the number of complete tiles / points L is increasing, decreasing and fluctuating, and at the end the evolution often is driving towards a valid stable pattern, which often is a min pattern. Many experiments showed that optimal min patterns can successfully be found with the Second Rule if (a) the maximal number of time–steps \(T_{Limit}\) is chosen large enough and / or (b) several runs with random initial states are performed.
6 Simulation and performance evaluation
Fig. 11
Snapshots of an evolution yielding a \((10 \times 10)\)min pattern with 8 points. Only valid patterns with \(L\ge 8\) points are shown. The final pattern is stable for \(t \ge 179\)
×
6.1 Performance for field size \((10 \times 10\))
Table 4
The improved rule was tested on \((10 \times 10)\)–fields for different time limits \(T_{limit}\) and for 1000 or 100 runs. During each run the lowest number of points reached and the related time was stored and used for the statistics. With an increasing budget of \(T_{limit}\) the probability to find min patterns increases
Points
Pattern frequency [1/100]
T\(_{Limit}\)
800
1 600
3 200
6 400
12 800
25 600
51 200
102 400
# of runs
1000
1000
1000
1000
100
100
100
100
8
0
0.1
0.3
0
1
1
2
3
9
1.4
2.5
5.8
10.6
21
30
39
36
10
11.2
19.2
35.5
50.6
73
64
57
61
11
62.4
72.0
57.8
38.8
5
5
2
0
12
25.0
6.2
0.6
0
0
0
0
0
13 .. 20
0
0
0
0
0
0
0
0
Average # of points
11.11
10.81
10.52
10.28
9.82
9.73
9.59
9.58
t\(_{Average}\)
255
531
942
1 972
4 521
6 756
7 898
11 237
The improved rule was tested 10 000 times on \((10 \times 10)\)–fields with random initial states (\(s\in {0,1}\)), for \(T_{Limit}=1~000\) time–steps, with \(\pi _4=0.1\), \(\pi _3=0.9\), and \(\pi _0=0.01\) (yielding best results). For each run, several parameters were recorded, such as the time–stamp for reaching the greatest or smallest number of points in valid patterns. The pattern frequency (the number of evolved patterns with a certain number of points) is given in Table 4. The average number of points \(p_{average}\) and the average number of time–steps \(t_{average}\) needed are also presented. In order to evolve patterns with a few points, the probability \(\pi _0\) should be kept low.
Now we were able to evolve min patterns with 8 points for a high \(T_{Limit}\). Most of the evolved patterns are close to the optimum, and lie between 9 and 12 for a small computational budget of \(T_{Limit}=800\). For a high budget of \(T_{Limit}=102~400\) the average number of points is only \(p_{average}=9.58\) with \(t_{average}=11~237\). Compared to the First Rule, the Second Rule (together with the First Rule) performs significantly better and the probability is high to reach an optimal min pattern. Fig. 11 shows the evolution of a stable min pattern with 8 sensors. During the evolution, other valid transient patterns with a different number of complete tiles L appear. The transient patterns between the shown time–steps are not valid, they usually show some tiles but are partially noisy.
6.2 Performance for other field sizes
The Improved Rule was also tested on other field sizes and a different number of runs and time limits (Table 5). For sizes up to \((8 \times 8)\) all runs yielded optimal min patterns. For fields larger than \((8 \times 8)\), min patterns were found among others.
Table 5
Simulation for different time limits and number of runs. Percentage of found optimal min patterns, and time–steps needed (\(t_{average}, t_{min}, t_{max}\))
\(\text{N} = \text{n} \times \text{n}\) n x n
Min points
Runs
TLimit
Found min patterns [%]
taverage of found min pat.
tmin
tmax
T\(_{\mathbf {3}}\% \,\)3%found
E \(=\) T\(_{\mathbf {3}}\% \) /N
3 × 3
1
1000
8
100
0.97
0
1
0.1
0.011
4 × 4
2
1000
10
100
1.22
1
2
1
0.063
5 × 5
3
1000
20
100
3.11
1
13
1
0.040
6 × 6
4
1000
120
100
12.4
1
89
1
0.028
7 × 7
5
1000
1 000
100
111
1
607
1.53
0.031
8 × 8
7
1000
3 000
100
407
1
2 851
4.53
0.071
9 × 9
8
100
50 000
76
2 226
12
15 048
12.5
0.154
10 × 10
8
100
100 000
3
3 741
944
9 210
3 741
37.41
11 × 11
11
100
1 000 000
3
419 961
281 031
681 050
16 803
3 471
12 × 12
13
100
300 000
5
163 098
96 764
291 384
93 584
650
Most significant values are in bold
Fig. 12
The effort (number of timesteps per cell) vs. the number of cells (size of the field). It is very low for \(N\le 81\). The trend line shows an exponential growth. The peak for \(N=121\) means that the related regular absolute min pattern is one which is difficult to evolve
×
In order to assess the time complexity, we define the computing effort per cell to evolve \(\delta \% \times R\)min patterns during R runs within time \( t\le T_{\delta \%}(N)\) as \(E(T_{\delta \%}, N)= (T_{\delta \%}(N))/N\), where the maximal needed time \(T_{\delta \%}(N)\) was extracted from the simulation data. If \(E(N)=const. \), then the needed time would be in O(N) to reach \(\delta \%\) min patterns on average of R runs. We have chosen \(\delta =3\) because this was the lowest rate of found min patterns, for \(n=10\) and \(n=11\) (Table 5). In our experiments, this effort increases exponential with N as shown in Fig. 12. Therefore, it is costly to compute optimal solutions for large N. But as the CA model is inherently parallel regarding N, we can reduce the computation time significantly on a parallel computer. For large N the algorithm is still applicable, though we need to terminate it due to a restricted computing budget when having found a near–optimal solution. In order to reduce the computational effort in principle, one could try to find a more sophisticated rule or to follow a divide–and–conquer approach.
7 Conclusion
In this paper, the problem of an optimal coverage of a wireless sensor network area was considered and solved by means of a probabilistic Cellular Automata (CA). Two CA rules were designed, that can find non–optimal and optimal min sensor patterns. The first rule evolves very fast stable valid patterns, with a peak number of points lying between minimum and maximum. The design principle behind is methodical and based on a set of templates derived from all pixels of the sensor tile. The second rule was designed especially to find min patterns, and it can do so, although the time to evolve an optimal min pattern can exceed the available processing capabilities. Moreover, regarding the r–von Neumann neighborhoods that serve as templates, it has been shown that there is a close relationship between min and max problems, depending only on their objective function. In addition, it has already been shown elsewhere (Hoffmann et al. 2021) that the core of the CA transition rule changes only slightly whatever it is a min problem or a max problem.
Regarding the required minimal number of sensor points, the results of the simulation (in Table 4) have been supported by a theoretical study (in Table 1) on von Neumann neighborhoods and borrowing either from heuristics (for almost all values of n) or from the spectral theory of circulant graphs (for \( n = 11 \)). For this particular size, the question arises whether this complexity could explain the excessive time required by the simulations (in Table 4) or the atypical effort highlighted in Fig. 12.
The “artificial” intelligence of this model, based on the power of its template–based system, therefore has its counterpart, namely its limitation in processing power to handle large–scale computing fields, a very time–consuming process. As already mentioned in other words, this weakness therefore makes it a good candidate for implementation on parallel processing environments.
In further work the possible sensor locations could be restricted, the charge of batteries could be taken into account, or this approach could be related to the vertex cover problem in order to compare time complexity.
Finally, as introduced through the first figure of this paper, in order to approximate the circular sensing area better, a hexagonal lattice could be more favorable. Two families would then be under study: either a still circulant topology based on Eisenstein–Jacobi networks (Huber 1994; Martínez et al. 2008) or a fractal topology based on the figure of Sierpiński arrowhead (Sierpiński 1916; Désérable 1999).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix \( A_1 \) – Heuristic construction of valid min\( n \times n \) patterns
A sample of patterns for \( n \times n \) fields ( \( 3 \le n < 13 \) ) is constructed from heuristics. The stepwise construction is illustrated with the primitives in Sect. 4.2. All patterns are valid min patterns except for \( n = 11 \). For clarity’s sake, the field is surrounded by a \( ( n + 2 ) \times ( n + 2 ) \) bounding box. The Initialize primitive, starting from a centered von Neumann neighborhood as initial configuration, has a very important influence to quickly reach an optimal pattern. When defining boundary conditions (Set_PBC), the interior reference point (circled in red) implies four N–S–E–W and four NW–SE–NE–SW image points (circled in black). It may happen that the images are outside the bounding box; however, their impact is still visible on the boundaries. The same happens when adding (Add_P) or moving (Move_P) a point since the boundary conditions follow (Figs. 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23).
Fig. 13
Formation of a valid balanced pattern for \( n = 3 \). The 2–step sequence gives:Initialize (3, 1) \( \rightarrow \)Set_PBC (3, (2, 2) ). The sequence yields \( \sigma ^{ *}_{ 3 } = 1 \)
Fig. 14
Formation of a valid balanced pattern for \( n = 4 \). The 3–step sequence gives: Initialize (4, 0) \( \rightarrow \)Add_P (4, (1, 1) ) \( \rightarrow \)Add_P (4, (3, 3) ). The sequence yields \( \sigma ^{ *}_{ 4 } = 2 \)
Fig. 15
Formation of a valid pattern for \( n = 5 \). The 4–step sequence gives: Initialize (5, 1) \( \rightarrow \)Set_PBC (5, (3, 3) ) \( \rightarrow \)Add_P (5, (1, 1) ) \( \rightarrow \)Add_P (5, (4, 5) ). The sequence yields \( \sigma ^{ *}_{ 5 } = 3 \)
Fig. 16
Formation of a valid balanced pattern for \( n = 6 \). The 4–step sequence gives: Initialize (6, 4) \( \rightarrow \)Set_PBC (6, (1, 4), (3, 1), 2) \( \rightarrow \)Add_P (6, (6, 1) ) \( \rightarrow \)Add_P (6, (4, 4) ). The sequence yields \( \sigma ^{ *}_{ 6 } = 4 \). Two points are lost during PBC sequence but two new points are injected afterwards
Fig. 17
Formation of a valid balanced pattern for \( n = 7 \). The 3–step sequence gives: Initialize (7, 5) \( \rightarrow \)Set_PBC (7, (1, 2), (2, 7), (7, 6), (6, 1)) \( \rightarrow \)Move_P (7, ((1, 2) , N),((2, 7), E),((7, 6), S),((6, 1), W)). The sequence yields \( \sigma ^{ *}_{ 7 } = 5 \)
Fig. 18
Moving effect on the 7–pattern from Step 2 to Step 3: the 4–cluster of points emerging at the junction of 4 adjacent 7–patterns is released
Fig. 19
Formation of a valid pattern for \( n = 8 \). The 6–step sequence gives: Initialize (8, 4) \( \rightarrow \)Set_PBC (8, (4, 2), (2, 5), (5, 7), (7, 4)) \( \rightarrow \)Add_P (8, (1, 1) ) \( \rightarrow \)Add_P (8, (8, 7) ) \( \rightarrow \)Move_P (8, ((5, 7) , N) \( \rightarrow \)Add_P (8, (4, 6) ). The sequence yields \( \sigma ^{ *}_{ 8 } = 7 \). The moving fills the two isolated gaps, even if it means producing a cluster of gaps
Formation of a valid balanced pattern for \( n = 10 \). The 5–step sequence gives: Initialize (10, 8) \( \rightarrow \)Set_PBC (10, (2, 1), (1, 9), (9, 10), (10, 2)) \( \rightarrow \)Set_PBC (10, (5, 3), (3, 6), (6, 8), (8, 5)) \( \rightarrow \)Move_P (10, ((2, 1) , S),((1,9), W),((9,10), N),((10,2), E)) \( \rightarrow \)Move_P (10, ((1, 2) , N),((2,10), E),((10,9), S),((9,1), W)). The sequence yields \( \sigma ^{ *}_{ 10 } = 8 \). Moving fills in gaps and relieve congested areas
Fig. 22
Formation of a non–optimal pattern for \( n = 11 \). The 4–step sequence gives: Initialize (11, 9) \( \rightarrow \)Set_PBC (11, (1, 7), (7, 11), (11, 5), (5, 1)) \( \rightarrow \)Set_PBC (11, (3, 4), (4, 9), (9, 8), (8, 3)) \( \rightarrow \)Add_P (11, (2, 2) ), Add_P (11, (2, 10) ), Add_P (11, (10, 10) ), Add_P (11, (10, 2) ). The sequence yields \( \sigma '^{ *}_{ 11 } = 13 \) (the required optimal result must be \( \sigma ^{ *}_{ 11 } = 11 \) as explained thereafter)
Fig. 23
Formation of a valid pattern for \( n = 12 \). The 5–step sequence gives: Initialize (12, 12) \( \rightarrow \)Set_PBC (12, (1, 5), (5, 12), (12, 8), (8, 1)) \( \rightarrow \)Set_PBC (12, (2, 10), (10, 11), (11, 3), (3, 2)) \( \rightarrow \)Add_P (12, (1, 12)) \( \rightarrow \)Move_P (12, ((2, 10) , E). The sequence yields \( \sigma ^{ *}_{ 12 } = 13 \). The last move just gives a slightly better pattern
×
×
×
×
×
×
×
×
×
×
×
Appendix \( A_2 \) Spectral detection of valid min\( n \times n \) patterns for \( n = 11 \)
Fig. 24
Isospectral class \( \overline{ {\mathcal {C}}}_{ 1 } = \{ \, {\mathcal {C}}^{ 1,2 }_{ 11 } , \ {\mathcal {C}}^{ 1,5 }_{ 11 } , \ {\mathcal {C}}^{ 2,4 }_{ 11 } , \ {\mathcal {C}}^{ 3,4 }_{ 11 } , \ {\mathcal {C}}^{ 3,5 }_{ 11 } \, \} \) of 11–circulants with their associated patterns. These patterns are not suitable for the minimum coverage problem. Last image: the pattern of \( {\mathcal {C}}^{ 1,2 }_{ 11 } \) is decorated from the \( {\mathbf {n}}_2 \)–prototile, with n prototiles and 2n gaps \(( n = 11 )\). Each cell is “decorated” from its von Neumann label of Fig. 5. The number of labels at site (x, y) is the cover level \( v_{ i j } = v \, ( x, y ) \) with one color per eigenvalue in \( M_{ {\mathbf {n}}_2 }. \)
Fig. 25
Isospectral class \( \overline{ {\mathcal {C}}}_{ 2 } = \{ \, {\mathcal {C}}^{ 1,3 }_{ 11 } , \ {\mathcal {C}}^{ 1,4 }_{ 11 } , \ {\mathcal {C}}^{ 2,3 }_{ 11 } , \ {\mathcal {C}}^{ 2,5 }_{ 11 } , \ {\mathcal {C}}^{ 4,5 }_{ 11 } \, \} \) of 11–circulants with their associated patterns. These patterns are optimal for the minimum coverage problem. Last image: the pattern of \( {\mathcal {C}}^{ 1,3 }_{ 11 } \) is decorated from the \( {\mathbf {n}}_2 \)–prototile, with n prototiles and 2n (colored) overlaps \(( n = 11 )\). Each cell is “decorated” from its von Neumann label of Fig. 5. The number of labels at site (x, y) is the cover level \( v_{ i j } = v \, ( x, y ) \) with one color per eigenvalue in \( M_{ {\mathbf {n}}_2 }. \)
In the algorithmic and practical context outside this section, the synonymy \( prototile \leftrightarrow \hbox {``tile'' } \) and \( tile \leftrightarrow \hbox {``pixel'' } \) will be used, without any confusion being to be feared.
