Adv Syst Sci Appl 2018; 02:84–92 Published online at http://ijassa.ipu.ru/index.php/ijassa/article/view/542. Segregation model for dynamic frequency allocation Alexander Kuznetsov1∗, 1Voronezh State University, Voronezh, Russia Abstract: We apply the Schelling type II segregation model to the dynamic frequency allocation. An algorithm is introduced for agents segregation over initially unknown radio channels. We relate the number of algorithm iterations until complete agents’ segregation to the number of agents, networks, and the other parameters via numerical experiment. Also, there are some parallels with the continuous-time model of segregation used in sociology. Keywords: segregation model, dynamic frequency allocation, cellular automaton 1. INTRODUCTION Nowadays, the number of robotic systems consisting of a large number of autonomous mobile agents (terrestrial robots, UAVs, etc.) with wireless radio communication network constantly increases. Agents interact with each other to perform a common task, for example, for emergency response, intrusion detection to a protected area, reconnaissance or networking in areas where it is difficult to organize a communication network in the usual ways [4] and so on. Human-mediated deployment or restoration of the communication system of such agents can be extremely difficult – for example, in an emergency situation it can be too dangerous for human operators. For this reason, it is necessary to provide the agents themselves with all the logic necessary to maintain the communication network, initially setting only the basic principles of agents’ interaction. This problem is investigated in detail in [5], and below we introduce a simple model of such self-organization. Briefly, agent periodically scans radio channels to discover other agents or stops at one of the channels and transmits a beacons sequence in order to be discovered by other agents. The problem we consider is one of Cognitive Radio ad hoc networks problems. The article [8] introduces dynamic spectrum access (DSA) which uses spectrum policy reasoning to determine allowed frequencies, requesting sensing periods on those frequencies, classifying the results from sensing events, then providing the list of allowed frequencies for use in frequency assignment. The papers [3, 10] describe different physical and informational aspects of the dynamic spectrum access. According to these works, two main approaches to DSA exists: dynamic spectrum allocation and opportunistic spectrum access. Dynamic spectrum allocation exploits temporal and spatial traffic statistics and aims at improving spectrum efficiency through time- and space-dependent spectrum sharing among coexisting radio services. Different from dynamic spectrum allocation, which uses the statistics of spectrum occupancy, opportunistic spectrum access uses the instantaneous spectrum availability by opening the licensed spectrum to secondary users. The idea is to allow ∗Corresponding author: avkuz@bk.ru SEGREGATION MODEL FOR DYNAMIC FREQUENCY ALLOCATION 85 secondary users to identify available spectrum resources and communicate opportunistically in a manner that limits the level of interference perceived by primary users. This article is motivated by the question, whether it is possible to create a completely autonomous Cognitive Radio network, without any Base Station or initial spectrum allocations, or coordination from a Base Station is necessary for agents to distribute over radio channels in a finite number of iterations? The purpose of the present article is the attempt to disconnect network self-organization from its radio-physics ground and to study it as a purely mathematical segregation problem. The dynamical network organization is, in its essence, a segregation model related to the Schelling segregation model [9]. The Schelling cellular automaton (Fig. 1.1) is a grid where each cell corresponds to a person. A person can have one of several “colours” that symbolizes her belonging to a particular social group. Colours are distributed randomly on the grid, and there is also some amount of unoccupied cells. Every person wants a certain part of people around him to be like him. If the number of adjacent cells of the same colour is below the specified threshold, then the person goes to the next free cell, otherwise, it remains in place. However, unlike the two-dimensional classical Schelling model, the proposed automaton is practically one-dimensional: we need the coordinate n of an agent only to simplify the description of the dynamics of the automaton. Fig. 1.1. The Schelling segregation model 2. THE CELLULAR AUTOMATON MODEL Denote as ID ⊂ Z, 0 ∈ ID the set of possible agent’s identifiers, asQ ⊂ N the set of channel qualities. Definition 2.1: Let us define the set of channels as the simply connected domain C ⊆ Z2 where each (n, f) ∈ C associated with the cell (qnf , idnf ) ∈ Q× ID and qkf = qlf for every (k, f), (l, f) ∈ C. We assume that if idnf = 0 there is no agent in the cell (n, f). Therefore, the f th column of cells {(i, f)} corresponds to the f th channel. The number Nf of cells in the f th column corresponds to the maximum possible number of agents using the f th channel. Definition 2.2: Let us call the agent the following vector ag = (idag, colag, fself , fold, nself ; ftarget, rag,Qag; sensed; t), Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) 86 A. KUZNETSOV where idag ∈ ID is the unique agent’s identifier, fself is the current channel number, nself is the position of the agent on the current channel fself , ftarget is the number of a target channel, fold is the auxiliary variable. Further, colorag ∈ COL is the agent’s colour, rag : COL × ID → {0, 1} is the grouping predicate, Qag : Q → [0, 1] is the agent preferences function, t is an agent’s overall functioning discrete time. The set of all agents we denote as AG. The sensed is the agent’s knowledge of environment (see below). Define the predicate R : AG ×AG → {0, 1} as following R(ag1, ag2) = rag1(colag2 , idag2), ag1, ag2 ∈ AG. If agents ag1, ag2 ∈ AG need to occupy the same channel, then R(ag1, ag2) = 1, otherwise R(ag1, ag2) = 0. It is clear, rag1 should be defined that rag1(ag2) = rag2(ag1) for any ag1, ag2 ∈ AG. Note that R determines the communication graph for AG. Definition 2.3: Let p, x are functions. We shall write p ∼ x, if it exists such monotonically non-negative increasing function ϕ that p(x) = ϕ(x). For simplification, assume that C = {(f, n)|f = 1, Fmax, n = 1, Nmax}. Also, we denote qnf = qf , AGf ⊆ AG is the set of agents on the channel f (i.e. with fself = f ), AGag = {ãg ∈ AG|R(ag, ãg) = 1} is the set of agents from the same network as the agent ag, and AGag f = {ãg ∈ AGf |R(ag, ãg) = 1} is the set of agents on the channel f from the same network as the agent ag. Discovering of agents can be unsuccessful. By this reason, introduce the function D : 2AG → 2AG . The agent ag ∈ AGf falls into the D(AGf ) with probability p1 ∼ qf . Our automaton will function in a discrete time. An agent’s tact behaviour can be described by the following algorithm. 0. Initialization. The agent ag scans all channels in C and randomly selects (n, f) with probability p0(n, f) ∼ Qag(qnf ) and such that the cell (n, f) is not already occupied. 1. Sensing. The agent ag senses the channel f . The agent sets fself := f, nself := n, t := t+ 1, sensed[f ] := {qf ,D(AGf )}. 2. If fself = Fmax, then the agent chooses a channel f̃ from sensed with probability p0(n, f). For example, p0 can be defined so that the agent selects the channel with the best quality. The agent sets ftarget := f̃ . 3. Decision. If |D(AGag f )| = |AG ag|, then go to the step 6, else if |D(AGag f )| > |AGag| α0 ∧ |D(AGag f )| > |D(AGf )| − |D(AG ag f )|, α0 > 1, then go to 5, else go to 4. 4. Channel change. The agent ag memorizes the current frequency fold := fself Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) SEGREGATION MODEL FOR DYNAMIC FREQUENCY ALLOCATION 87 and chooses a new frequency fself := fself + dir, 1 ≤ fself + dir ≤ Fmax, Fmax, fself + dir = 0, 1, fself + dir > Fmax. If an arbitrary coordinate n such that the cell (fself , n) is unoccupied exists, the agent chooses the cell (fself , n) and occupies it. If there is no such cell, then the agent does not occupy any cell on this turn and remains on its old cell. In this case, the agent sets fself := fold, go to 1. If fself = ftarget, then go to 5 else go to 1. 5. Waiting for agents. The agent waits twait = α1Fmax + α2τ(|D(AGag f )|, |AG ag|, |D(AGf )|), α1 ≥ 0, α2 ≥ 0, (2.1) τ(x, y, z) ∼ min { x y , x z } , (2.2) turns and selects dir randomly from the set {−1, 1}. Go to 1. 6. Wait. The main problem is to find model’s parameters αi, i = 1, 3 and a function τ such that the segregation process would complete in a reasonable time. We should note that an unlucky choice of parameters will result in the algorithm not converging at all. Physically, agents get information about other agents and about a state of channels, scanning the spectrum and exchanging beacons, as described in [5]. One tact of the cellular automaton corresponds to the full cycle of the pilot and beacons exchange. A detailed technical solution corresponding to the proposed model is described in the patent “Telecommunication network data transmission means and telecommunication network” # RU 2 549 120. Fig. 2.1. Final configuration of the automaton The example of the automaton’s final state is shown on Fig. 2.1. The lighter tone of cells in the picture corresponds to the better quality of corresponding channels. We can see the network Net1 = {agi|i = 1, 4} formed on the channel f1, and Net2 = {agi|i = 5, 6} formed on the channel f2. Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) 88 A. KUZNETSOV 3. NUMERICAL EXPERIMENT AND DISCUSSION We performed simulation of the proposed algorithm with the “Psychohod” simulator [7]. For these purposes, we introduced the new operating mode of the program (see Fig. 3.1). Fig. 3.1. “Psychohod” program in the process of agents segregation We defined p1 = 1, the grouping predicate as the following R(ag1, ag2) = { 1, colag1 = colag2 , 0, colag1 6= colag2 . Fig. 3.2 contains simulation results for 5 networks, 50 agents in each network, and for α1 = Fmax + 1, α2 = (Fmax + 1)β, τ(x, y, z) = min { x y , x z } , where α1, α2, τ are parameters from (2.1), (2.2). Ordinates correspond to the average discrete time T , abscissas correspond to the α0. Channels qualities q = 1, 9 were distributed uniformly over Fmax = 100 channels, 100 experiments for each point were performed. Fig. 3.2. Average time to complete network segregation (50 agents per net, 5 nets) Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) SEGREGATION MODEL FOR DYNAMIC FREQUENCY ALLOCATION 89 The simulation stopped when the segregation process was completed or when T > 30000. The points encircled correspond a case when for all 100 experiments the segregation was completed in less than 30000 turns. For other points, the segregation process was completed in 79–99% of experiments. Fig. 3.3 represents histograms of segregation’s completion times for different values of α0 and β. We used function T (α0) = a+ b α0 − c , c > 0, b > 0 for approximations of data points. Fig. 3.3. Histograms of segregation’s times Next, we fixed α0 = 2.2, β = 30 and performed experiments with different numbers of nets and agents in each net as described in Table 3.1. Note that segregation considered Table 3.1. Unsuccessful segregation percentage Agents in net 10 20 30 40 50 60 70 80 90 100 Unsuccesses number, five nets 37 15 3 4 1 0 0 5 9 30 Unsuccesses number, eight nets 97 75 59 33 22 2 1 18 29 100 unsuccessful if it takes more than 30000 turns. Therefore, we should change α0 and β proportional to the number of agents. For example, if we have 25 agents in each of five nets, we need to reduce β approximately in four times and slightly increase α0 (see Fig. 3.4) to minimize the average segregation time. Results of the numerical experiment immediately suggest an improvement of the previously proposed algorithm. We should add the following step: 2.5. The elapsed time check. If t > Tr, then change αi, i = 0, 2 on arbitrary small values. Also, we can memorize all changes of algorithm’s parameters and gradually choose the optimal ones. The further improvement can be dividing of the set of channels into subsets so that agents from one net would tend to search channels in the channel subset associated with their net number. Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) 90 A. KUZNETSOV Fig. 3.4. Average time to complete network segregation (25 agents per net, 5 nets) The proposed cellular automaton is close to the so-called Schelling type II model. Works [1, 2], which introduce continuous-time Schelling dynamical system, characterize Schelling II model as the following. Let the population is partitioned into disjoint sets, akin to the different districts in a city. The population is divided into “types”. Let X and Y denote the two types, inhabiting a space which is partitioned into m areas, denoted Ai, i = 1, 2, ...,m. Also, let Xi and Yi denote the total X-type population and Y -type population in Ai, |X| and |Y | the total of each type in the population, and N = |X|+ |Y | the total population. Tolerances are allocated to a given type in a given area via a “tolerance schedule”. This function describes the maximum X-type population that would tolerate up to R(X)Xi members of type Y in the same area, where R(X) is necessarily monotone decreasing. It is also assumed that there is no lower bound on tolerance, i.e. no population insists on the presence of the opposing type. The simplest, single-area continuous-time Schelling dynamical system has the following form: dx dt = [xRX(x)− y]x, (3.1) dy dt = [yRY (y)− x]y, (3.2) where x, y are densities of populations X , Y , |X| = k|Y |, p > 0, and RX , RY are monotone decreasing tolerance schedules’ functions. Here, for example RX(x) = a(1− x)p, (3.3) RY (y) = b(1− ky)p, (3.4) a > 0, b > 0, p > 0, k = |X|/|Y |. We have found, that our automaton’s behaviour in some cases can be described by a model like (3.1), (3.2). Denote as x(t) = Xf (t)/|X(t)| the density of agents of the net 1 on the network channel f . Let’s also denote y(t) = Yf (t)/|Y (t)| the density of agents of all other networks on the network channel f . As we have 50 agents per net and 5 nets, k = |X|/|Y | = 1/4, x(18) = 1/50, y(18) = 1/200. At first, select p = 1.7, a = 1, b = 1/2. Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) SEGREGATION MODEL FOR DYNAMIC FREQUENCY ALLOCATION 91 We can modify (3.1), (3.2) in the way described in [1], using the exponential schedule RX(x) = e−6x − e−6 1− e−6 , (3.5) RY (y) = e−6y/k − e−6/k 2(1− e−6/k) , (3.6) to obtain better fitting. We can see the comparison of experimental points with the solutions of Schelling dynamical system on Fig. 3.5, left. Circular and diamond-shaped markers correspond to experimental values of x and y. The black dotted line corresponds to the linear schedule (3.3), (3.4), solid lines correspond to the exponential schedule (3.5), (3.6). Interestingly enough, that such initial condition exists which can provide oscillatory behaviour for Xf . This is the case of approximately equal initial numbers of agents of different nets at the channel f (see Fig 3.5, right). Unfortunately, the model (3.1), (3.2) can not explain this case at whole, and we should use more complex multi-area segregation model, but it is possible to model oscillations by multiplying (3.5), (3.6) with a periodic function. The aforesaid situation entails the potential impossibility of the network’s self-organization in a reasonable time. Fig. 3.5. Graphs of numerical experiment’s results in comparison with the solutions of Schelling dynamical system 4. CONNECTION WITH THE AGENTS’ MOTION MODEL Previously, the author had developed the model of agents’ motion and conflict and related simulator “Psychohod”. Groups of agents move through a rough terrain and can destroy other groups of agents. This simulator can export data with coordinates of communicating agents, the list of destroyed agents, and landscape obstacles to communication. The data exported used by the communication simulator which contains described above automaton as well as by other telecommunication models (Fig. 4.1). Optionally, the communication simulator can export the message exchange data to a network simulator like ns-3 or omnet++. 5. CONCLUSIONS We proposed the simulation of the automatic initial channels distribution in a wireless network. Also, we studied the dependence of the channels distribution time on various parameters like the nets’ number, the agents’ number, the channels’ scanning speed. At last, we compared the simulation results with the solution of Schelling dynamical system. We found that the proposed network self-organization is similar to social segregation Schelling type II models. Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018) 92 A. KUZNETSOV Fig. 4.1. Conjugation of the agents’ motion simulator, the communication simulator, and (optional) a network simulator In the future, we are planning to design an adaptive algorithm providing minimization of the channels distribution time, a model with relay agents based on the “Psychohod” simulator, and to obtain numerical characteristics of aforesaid models. It is also planned to provide agents with additional characteristics, such as a memory of channels visited, and link the proposed model of self-organization of the communication system with the model of the movement of agents [6], previously developed by the author. It seems promising to compare the proposed cellular automaton with more complex continuous-time segregation models to explain the occurrence of the chaotic or oscillatory behaviour of the system. This work was supported by RFBR Grant 18-07-01240 a. REFERENCES 1. Haw, D. (2016). Measuring and understanding segregation (Doctoral dissertation, Bristol Centre for Complexity Sciences). 2. Haw, D. J., & Hogan, J. (2018). A dynamical systems model of unorga- nized segregation. The Journal of Mathematical Sociology, 42(3), 1-15. doi: 10.1080/0022250X.2018.1427091 3. Horne, W. D. (2003). Adaptive spectrum access: Using the full spectrum space. In Proc. of the international symposium on advanced radio technologies. 4. Jones, M., & Dudenhoeffer, D. (2000). A formation behavior for large- scale micro-robot force deployment. In Winter simulation conference (Vol. 01, p. 972-982). Los Alamitos, CA, USA: IEEE Computer Society. doi: doi.ieeecomputersociety.org/10.1109/WSC.2000.899900 5. Kuznetsov, A. (2017). Allocation of limited resources in a system with a stable hierarchy (on the example of prospective military communications system). Large-Scale Systems Control, 66, 68–93. 6. Kuznetsov, A. V. (2017). A simplified combat model based on a cellular automaton. Journal of Computer and Systems Sciences International, 56(3), 397–409. doi: 10.1134/S106423071703011X 7. Kuznetsov, A. V. (2018). Model of the motion of agents with memory based on the cellular automaton. International Journal of Parallel, Emergent and Distributed Systems, 33(3), 290-306. doi: 10.1080/17445760.2017.1410819 8. Redi, J., & Ramanathan, R. (2011, Nov). The darpa wnan network architecture. In 2011 - milcom 2011 military communications conference (p. 2258-2263). doi: 10.1109/MILCOM.2011.6127657 9. Schelling, T. C. (1971). Dynamic models of segregation. The Journal of Mathematical Sociology, 1(2), 143-186. doi: 10.1080/0022250X.1971.9989794 10. Zhao, Q., Tong, L., & Swami, A. (2005). Decentralized cognitive mac for dynamic spectrum access. In First IEEE international symposium on new frontiers in dynamic spectrum access networks, 2005. dyspan 2005. (p. 224-232). doi:10.1109/DYSPAN.2005.1542638 Copyright c© 2018 ASSA. Adv Syst Sci Appl (2018)