# Elements of Hyperstructure Theory in UWSN Design and Data Aggregation
## 3 Use of the Theory of Quasi-Automata
A sub quasi-automaton \(\mathbb{B}=(I,S_{1},\delta_{1})\) of a quasi-automaton \(\mathbb{A}=(I,S,\delta)\) is called separated if \(\delta(S\setminus S_{1},I^{*})\cap S_{1}=\emptyset\). A quasi-automaton is called connected if it does not posses any separated proper subautomaton. A quasi-automaton \(\mathbb{A}=(I,S,\delta)\) is called strongly connected if for any states \(s,t\in S\) there exists a word \(a\in I^{*}\) such that \(\delta(a,s)=t\). If in quasi-automata we suppose that the input set \(I\) is a semihypergroup instead of a free monoid, we arrive at the concept of a quasi-multiautomaton. When defining this concept, caution must be exercised when adjusting the conditions imposed on the transition function \(\delta\) as on the left-hand side of condition 2 we get a state while on the right-hand side we get _a set of states_. However, in the dichotomy _deterministic -- nondeterministic_, quasi-multiautomata still are deterministic because the range of \(\delta\) is \(S\). The difference between the transition function of a quasi-automaton and the transition function of a quasi-multiautomaton is that in quasi-automata the state achieved by applying \(y\) in a state, which is the result of application of \(x\) in \(s\), is the same as the state achieved by applying \(xy\) in \(s\), while condition (4) says that it is one of the many states achievable by applying any command from \(x*y\) in state \(s\). Definition 7: A quasi-multiautomaton is a triad \(\mathbb{A}=(I,S,\delta)\), where \((I,*)\) is a semihypergroup, \(S\) is a non-empty set, and \(\delta:\ I\times S\to S\) is a transition map satisfying the condition:  
\[\delta(b,\delta(a,\ s))\in\delta(a*b,\ s)\text{ for all }a,b\in I,\ s\in S. \tag{4}\]  
The hyperstructure \((I,*)\) is called the input semihypergroup of the quasi-multiautomaton \(\mathbb{A}\) (\(I\) alone is called the input set or input alphabet), the set \(S\) is called the state set of the quasi-multiautomaton \(\mathbb{A}\), and \(\delta\) is called next-state or transition function. Elements of the set \(S\) are called states, elements of the set \(I\) are called input symbols. Further on, we will make use of the above mentioned concepts to model the process of data aggregation. Notice that in [PERSON] et al. (2018), Cartesian composition of automata resulting in a quasi-multiautomaton is used to describe a task from collective robotics. Moreover, in [PERSON] et al. (2018), the issue of state sets and input sets having the form of vectors and matrices (of both numbers and special classes of functions) is discussed in the context of quasi-multiautomata. In Figure 2 we can see that the elements of the UWSN are divided into several tiers. Also, the nodes are grouped into clusters. The process of data aggregation happens as follows: First, data is collected in cluster heads and then transmitted between cluster heads towards the surface, i.e., \"upwards\". Obviously, we can only transmit the amount of data that the capacity of available memory allows. Suppose that clusters cover areas of more or less the same size, i.e., it does not matter how many nodes there are in respective clusters. Now, regard a set of vectors:  
\[S_{v}=\{\vec{v}=(v_{1},v_{2},\ldots,v_{n})\mid v_{i}\in\langle 0;1\rangle;i\in \{1,\ldots,n\}\} \tag{5}\]  
of such a number of components that corresponds to the number of tiers (with index 1 meaning surface and index \(n\) meaning seabed or the deepest tier). The components \(v_{i}\) carry information about how much total memory all cluster heads at a given tier has been used. In other words, \(v_{2}=0.6\) means that at the second tier 60% memory capacity has been used, regardless of whether this 60% means that every cluster head at this level has 40% free capacity or whether 6 out of 10 cluster heads already have no available memory while 4 are 100% free. The process of data aggregation starts with \(\vec{v}=(0,\ldots,0)\), i.e., at the moment when all cluster heads have empty memory. Since, at first data are collected within clusters, \(\vec{v}\) immediately becomes non-zero.