Kieran Flanagan
email: k.flanagan@research.ait.ie

Enda Fallon
email: efallon@ait.ie

Paul Connolly
email: paul.connolly@npd.com

Abir Awad
email: abir.awad@southwales.ac.uk

NetFlow Anomaly Detection Though Parallel Cluster Density Analysis in Continuous Time-Series

Keywords: Anomaly Detection, NetFlow, Clustering, Density Analysis

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In recent years, research into new methods of anomaly detection within a network has increased in prominence. The need for a fast, reliable method to identify possible malicious activity has grown in response to emerging threats. Protecting confidential and proprietary data is of paramount importance to any organization to ensure that both legal and contractual obligations are kept. In addition, the data stored may not necessarily be the property of the company storing and handling the data. Malicious activity such as Botnets and Port Scans are increasing in frequency. These attacks, while simple, have the potential to allow for unauthorized access onto the network.

Within any organization, it is common place to use network monitoring and analysis tools to help with the detection of any anomalous behaviour on the network. Tools, such as McAfee ePO and Tipping point for example, are signature based models, which require a known example of a threat to be catalogued and a signature generated. The signature based model, while highly exact, fails if a novel attack occurs (e.g. zero-day vulnerabilities), since no previous signature exists. This limitation gave rise to anomaly based detection mechanisms. These methods require no signature database, but instead models the "normal" traffic on a network and alerts to any activity that happens outside of these normality bounds.

While much research has been conducted on various methods for anomaly based systems using a variety of approaches [START_REF] Chen | Combining MIC feature selection and feature-based MSPCA for network traffic anomaly detection[END_REF][START_REF] Lin | CANN: An intrusion detection system based on combining cluster centers and nearest neighbors[END_REF][START_REF] Fernandes | Network anomaly detection using IP flows with Principal Component Analysis and Ant Colony Optimization[END_REF][START_REF] Ciplinskas | Outlier Detection Method Use for the Network Flow Anomaly Detection[END_REF][START_REF] Wankhede | Intrusion Detection System using Classification Technique[END_REF], key limitations apply when attempting to adapt these approaches to a real-time system. These include, most notably, computational cost. Within commonly used distance based outlier detection mechanisms, the need for distance based calculations for each new sample can be overwhelming for high volume data. This gave rise to optimized algorithms designed to mitigate this limitation. Algorithms such as Fast Local Outlier Factor (FastLOF) [START_REF] Goldstein | FastLOF: An Expectation-Maximization based Local Outlier detection algorithm[END_REF] and Micro-Cluster based Outlier Detection (MCOD) [START_REF] Kontaki | Continuous monitoring of distancebased outliers over data streams[END_REF], reduce the overall cost of the range queries with varying degrees of success.

It has been shown that the application of time series can be beneficial in the detection of network anomalies. Applying time series over time-windows of increasing size has been shown to be capable of normalizing normal behaviours over time. However, at smaller time-intervals, it is possible for abnormal behaviour to traverse time windows, allowing for the possibility of becoming a false positive. This is particularly prevalent among anomalies that generate low numbers of NetFlow. It is possible for it to become hidden within other network traffic as time progresses, making detection increasingly unlikely.

Moreover, while it is possible that a large increase may occur, small deviations in established traffic behaviour may also be an indication of unauthorized activity. For example, an increase in failed login attempts may produce little difference with respect to NetFlow, it may be indicative of someone trying to guess a password. Detecting such an instance would be of paramount importance, particularly if followed by a successful login attempt [START_REF] Purwanto | Time based anomaly detection using residual polynomial fitting on aggregate traffic statistic[END_REF]. This paper proposes a solution to this problem. By implementing parallel clustering algorithms, it is possible to gain a higher level of granularity while maintaining the normalization techniques gained from an incrementally increasing timewindow. Concurrent algorithms can detect minor deviations from established behaviour that can occur, regardless if they occur while traversing between time-windows.

In Section 2, an overview of related work is given. In Section3, a brief overview of the technology used is presented. In Section 4, we propose a framework for the identification of anomalies within NetFlow data. The architecture is presented as well as an overview given on algorithms created and used. In Section 5, testing methodology is presented. In Section 6, results obtained from live data are presented and analysed. In Section 7, conclusions and future work are presented.

Related Works

Recent research into anomaly detection has largely focused on applying anomaly detection mechanisms on network data to successfully identify anomalous behaviour. Many problems still exist however. Performance is a key factor when trying to utilize anomaly detection techniques and there are many examples where this is apparent. Methods such as Principal component analysis [START_REF] Fernandes | Network anomaly detection using IP flows with Principal Component Analysis and Ant Colony Optimization[END_REF], K nearest neighbour [START_REF] Putra | Modified K-means algorithm using timestamp initialization in sliding window to detect anomaly traffic[END_REF] and ensemble techniques [START_REF] Goeschel | Reducing false positives in intrusion detection systems using datamining techniques utilizing support vector machines, decision trees, and naive Bayes for off-line analysis[END_REF], [START_REF] Uddin | Signature-based Multi-Layer Distributed Intrusion Detection System using Mobile Agents[END_REF] have been used to various degrees of success in this task.

However, there comparatively expensive operations have led to a rise in clustering techniques to mitigate the calculations need when associating anomaly detection with big data [START_REF] Vijayakumar | Big Data, Cloud and Computing ChallengesFuzzy Based Intrusion Detection Systems in MANET[END_REF], [START_REF] Singh | Big Data Analytics framework for Peerto-Peer Botnet detection using Random Forests[END_REF]. Using aggregated data, such as NetFlow can be used to reduce the calculations further [START_REF] Carela-Español | Analysis of the impact of sampling on NetFlow traffic classification[END_REF]. Limitations are present with these techniques however. Kumari et al [START_REF] Kumari | Anomaly detection in network traffic using K-mean clustering[END_REF] looks at a clustering technique for the use of anomaly detection over a network, setting a distance based threshold as the 100th farthest data point from the obtained cluster centroids. This threshold is a common theme across multiple anomaly detection solutions [START_REF] Alsayat | Social media analysis using optimized K-Means clustering[END_REF][START_REF] Velmurugan | Efficiency of k-Means and K-Medoids Algorithms for Clustering Arbitrary Data Points[END_REF][START_REF] Asmuss | Network traffic classification for anomaly detection fuzzy clustering based approach[END_REF]. However, it can be argued that using a common threshold over all clusters within real data is non-representative of the various forms of traffic created. E.g. Traffic from different applications do not act in a similar manner.

This brings forward an interesting problem. While distance based outliers have been shown to be of significance in a plethora of works [START_REF] Abid | Anomaly detection through outlier and neighborhood data in Wireless Sensor Networks[END_REF][START_REF] Fu | Biased-sampling of density-based local outlier detection algorithm[END_REF][START_REF] Tsiatsikas | Battling against DDoS in SIP: Is Machine Learning-based detection an effective weapon?[END_REF], we propose another indicator of possible anomalous behaviour. By monitoring cluster density over a time series, changes in underlying behaviour can be detected. Rather than only focusing on samples that are anomalous via distance based calculations, changes in the density of activity over time are also monitored.

Asmuss et al [START_REF] Asmuss | Network traffic classification for anomaly detection fuzzy clustering based approach[END_REF] demonstrates the use and effectiveness of utilizing a time series based approach over live data. The aggregation of traffic is highly beneficial in this case, as it reduces the computational sources needed. Furthermore, it also provides a tangible benefit when comparing results across clusters. This idea of time-aware analysis has been used elsewhere also [START_REF] Gajic | An improved anomaly detection in mobile networks by using incremental time-aware clustering[END_REF], and has shown to be a valuable tool in mapping continuous behaviour.

This ability to generate a normalized view of traffic over time, practically speaking, has some limitations however. The potential for an anomaly to traverse though sequential time windows can lead to the anomaly threshold not being broken, thus leading to a false positive reading. Presented in Section 4 is an architecture that utilizes concurrent time windows in order to mitigate the risk of this happening. Anomalies can be gathered from individual instances of the clustering algorithm, while the correlation of clustering behaviours through instances can also indicate anomalous activity.

Technology Overview

Cisco NetFlow

Cisco NetFlow is a system that amalgamates network traffic information into a format that successfully describes communications occurring on a network. Through a NetFlow enabled device (Fig. 1), packet traces are identified and stored as a single flow representation of a specific set of communications between two devices. These are used for multiple tasks such as network performance monitoring and used as a means of security evaluation when an incident has been detected. Visualization of the NetFlow has also proven to be of tangible benefit [START_REF] Wong | A visual analytics paradigm enabling trillionedge graph exploration[END_REF]. Using this aggregated data for anomaly detection has numerous benefits, such as data size being reduced for processing purposes and storage. For the analysis in this paper, NetFlow was used as it was found that using NetFlow for network monitoring purposes was highly common in the area [START_REF] Li | A survey of network flow applications[END_REF], as well, in this case, the current infrastructure of NPD allowed for the collection of NetFlow with relative ease.

MCOD

MCOD is a distance based outlier detection mechanism that utilizes clustering to reduce the amount of distance based calculations needed to identify possible anomalies. This reduced performance cost of the algorithm makes it an ideal candidate for real-time anomaly detection over data streams when compared to other distance based algorithms such as Local Outlier Factor (LOF). As described in [START_REF] Kontaki | Continuous monitoring of distancebased outliers over data streams[END_REF], MCOD uses a sliding window approach to identify outliers over a data stream. By using an expiring data set, the algorithm can be optimized to only use a data set that is large enough for satisfactory anomalies to be detected, while maintaining the low amount of calculations needed. Distance is calculated between cluster centroids and the NetFlow sample being queried. If the point is within this range of a cluster centroid and the cluster has the specified density, k, then the point is determined to be a non-anomaly, or inlier.

Proposed Framework

The architecture is a two-step approach that involves monitoring traffic at different levels of abstraction. Firstly, an adaptation of the MCOD algorithm is applied on the NetFlow data in sequential time windows (Fig. 2). This stage can outline distance based outliers contained within the NetFlow information. Following this, the clusters generated within each time-window are correlated to identify those representing similar traffic. The density values (how many input samples are contained within the cluster) are then gathered at the end of each window 5 minute period.

Fig. 2. Architecture Overview

Anomaly Detection

When using algorithms such as k-Nearest Neighbour and MCOD, a common variable that must be tuned to the dataset is k. While it's exact use may change, the principal remains consistent. k is used to describe the limit of normality within anomaly detection frameworks. It is a single variable used to tune the classification or detection rate within an algorithm. Within MCOD, it is the value at which a micro cluster is generated and an outlier is classified as an inlier. Within the context of NetFlow anomaly detection, this is a severe limitation, as it assumes that all network traffic activity has an equal distribution across the network, which is an extremely unlikely assumption (Discussed further in Section 5).

In order to successfully mitigate this limitation, all cluster densities are monitored irrespective of k's value. This allows for the successful detection of abnormal increases and decreases in cluster densities with respect to the time window being analysed.

Density Normality Measurement Generation

Within the proposed architecture, MCODT is initialized with a time window of size t. MCODT clusters data within this window, identifying anomalies using distance based calculations. The clusters generated within this time window contain samples that correspond to a type of network behaviour (Table 5). In parallel, windows are initialized in time steps of St using the same configuration as the initial algorithm.

Fig. 4. MCODT Definition

The positions of the clusters generated are then correlated with each subsequent MCODT instance to successfully capture the clusters activity through the other MCODT instances. This correlative step is needed as, due to the cluster generation step of MCODT, a cluster might not be in the exact same position throughout the sequential time windows, even though they represent the same class of network traffic.

Fig. 3 . Commonly Used Notation

Fig. 5. Cluster Correlation

Once the clusters have been correlated and shown to be representative of the same class of network traffic, the cluster is persisted and given an ID. At the end of each instance of MCODT, the clusters density is measured and compared to its own historical activity and its activity in the other instances.

Fig. 6. Residual Calculation

This allows for the identification of anomalies, using the 3-standard deviation rule, within the persisted cluster. Furthermore, when a cluster is not generated in all the instances of MCOD, it is indicative of non-homogenous network activity. This specific type of traffic (as shown in Section 6) is highly irregular, and corresponds to network traffic that is extremely uncommon within the testing environment.

Methodology

Collected Data

To successfully test the proposed method, NetFlow was collected in a 24-hour period from within NPD. This was live data, and no previous insight about this 24hour period was held. It was unknown if it held anomalies or not, simulating realworld conditions. The NetFlow contained all communications, both internally and externally, during this period. A total of 151,995,634 NetFlow samples. From these samples, 8 attributes were extracted (Table 1). And from these, 6 attributes were selected to be used in the anomaly detection calculations.

• Source/Destination IP • Destination Port • Source Port • Destination Bytes • Source Bytes • Protocol ID
These attributes were normalized using theoretical maximums as well as observed maximums over a 3-month period (Table 2).

Table 1. Selected NetFlow Attributes

Destination Bytes

Volume of traffic sent from the Destination IP in bytes Destination I.P.

The destination I.P address of the NetFlow

Destination Port

The Destination port used for the NetFlow

Source Port

The Source port of the NetFlow

Start Time

The time at which the represented communiqué was initiated. The remaining collected attributes were excluded from the anomaly calculations due to various reasons. The IP addresses were excluded due to the IP address leases allocated by DHCP servers were inconsistent in both maintaining the allocated IP's, and time-out periods for leased IP's. This would lead to inconsistent results within networks, as IP addresses could be re-allocated in as little as 30 minutes, drastically changing their perceived normal traffic pattern. Instead, IP addresses were categorized as either internal or external, in order to develop separate clusters in feature space to represent internal-tointernal and external-to-external traffic types. These attributes, along with the Start Time attribute, were collected for the investigation of identified anomalies and clusters within the proposed architecture. For testing, a 24-hour example was chosen with no specific preference. No previous assumptions existed about this data before testing. The architecture was configured with an initial time window size of 5 minutes, and parallel instances were configured to run at one minute intervals after this, leading to a total of 5 MCOD instances processing the data in parallel. Configured variables are outlined in Table 3.

Program Configurations

Results

In this section, we discuss the results of the proposed method of anomaly detection. Anomalous samples that were identified at both stages of the proposed architecture are outlined and analysed. Examples of normal activity of various types will also be presented.

Point Anomalies

Due to the two-stage architecture of the proposed method, anomalies may be detected in two different manners. Firstly, anomalies that are anomalous by the distanced based calculations are outlined at the end of every time window. An anomaly outlined in this window contains a point that never meets the required density irrespective of time. These are regarded as Point Anomalies. Due to the relatively small time window of the MCODT instances, the number of point anomalies detected within the first hour of processing was vast. The number of additional anomalies fell rapidly over the course of the analysis.

Because of this, focus was placed on point anomalies that were detected after the initial 12 hours of analysis. Table 4 outlines two such samples that were correctly identified as an anomaly. Sample A represents a simple DNS request, which at first seemed like a false positive. However, upon investigation, it was shown that this DNS request was from an internal asset to an external DNS server. This incident was of interest to security technicians within the NPD Group. Sample B was an unauthorized UPnP (Universal Plug and Play) device connected to the network. It has been well documented how network security can be effected by having a UPnP device hosted on a network [START_REF] Zheng | Petri Nets Based Modeling and Analysis of UPnP Security Ceremonies[END_REF]. Upon Detection, the device was disconnected from the network. Cluster densities were measured at regular intervals. Five instances of MCODT were run in parallel, each with the same configuration settings (Table 3) The initial instance, MCODTN0, was initialized at 00:00am on the day in question. One minute after this, MCODTN1, was initialized, followed by MCODTN2 and so on. This low level of analysis allows for the detection of possible malicious activity in as little as one minute after an incident Table 5 outlines sample clusters, selected based on being classified as an anomaly, and their activity over the course of one hour within the scope of all the independent instances. This totals 1440 total densities measured for 1532 clusters generated and persisted over the course of testing.

Cluster Density Analysis

Anomalies were detected in all instances of MCODT. However, anomalies were shown in both the independent analysis and correlative analysis. Of interest is an anomaly detected (Table 5. Sample 9). This anomaly appears in all instances of the algorithm, and is shown to have significant divergence from observed normal behaviours. The rapid increase, once investigated, was attributed to a single asset. It was shown to be connected to an external IP. It proceeded to attempt to open a connection to the external asset, but never received any connection. This was of interest to the security team within NPD, and was swiftly resolved. Sample 4 was also anomalous within the test. The Cluster only appeared in one window, showing the extremely temporal nature of the event. The other instances did not detect sufficient activity to generate a cluster. It represents an extremely short burst of activity to an external device.

Conclusions and Future Work

This paper proposed an architecture designed to detect anomalies within NetFlow data.

To achieve this at a micro level, a clustering algorithm was run in parallel to determine anomalies in cluster activity in time-series. It was shown to be able to detect anomalies in live data without any previous knowledge on the data. These anomalies were investigated and shown to be of security interest. The result was interesting given that the testing was conducted on real world, live data. However, to compile a complete effectiveness rating for the algorithm would require a considerable amount of resources if used on real world representative data.

Future work would include refining the extensibility of the algorithm. Due to the abstraction of the density monitoring, it is possible to add attributes to MCODT's feature space in order to monitor changes in not only network traffic, but other metrics that could attribute to the risk of a malicious attack, such as the vulnerability of an asset determined by an external program.

Fig. 1 .

 1 Fig. 1. NetFlow Example

  Protocol I.D. The ID of the Protocol used. (6 = TCP, 17 = UDP) Source Bytes Volume of traffic sent from the Source IP in bytes Source I.P. The Source IP of the NetFlow

Table 2 . Maximum Values used for Normalization

 2

	Variable	Maximum
		Value
	Source/Destination Port	65535
	Source/Destination Bytes	4294967270 (Bytes)
	Protocol ID

Table 3 . Program Configurations

 3

	Name	Symbol	Value
	Minimum Density Required	K	50
	Maximum range for Sample	R	.0025
	Number of Algorithm Instances	N	5
	Size of Window	T	360 seconds

Table 4 . Sample Point Anomalies

 4

	Sample	Source	Destination	Source	Destination	Protocol
	ID	Port	Port	Bytes	Bytes	ID
	A	57838	53	116	262	17(UDP)
	B	49886	1900	8428	0	17

Table 5 . Detected Anomalies

 5

	ID Source	Destination	Source	Dest.	Protocol	N0	N1	N2	N3	N4
		Port	Port	Bytes	Bytes	ID
	1	34701	6001	272	296	6	2	4	2	6	3
	2	2598	6773	3486	3486	6	3	5	7	3	5
	3	6188	41781	212	74	6	48	30	32	24	27
	4	54787	5355	376	0	17	5	NA	NA	NA	NA
	5	58544	2181	2840	1640	6	10	10	10	10	10
	6	7858	443	1026	782	6	308	256	337	201	339
	7	1720	61444	320	0	6	1418	1418 1418 1418 1418
	8	45549	8879	22472 7580	6	755	755	755	755	755
	9	5925	5040	442	0	17	28	21	116	182	167
	10	1521	46172	3532	5624	6	10	15	9	13	14


Abdelhamied A Ateya

Anastasia Vybornova
email: a.vybornova@gmail.com

Konstantin Samouylov

Andrey Koucheryavy

System Model for Multi-level Cloud Based Tactile Internet System

Keywords: Tactile Internet, Cloud, System model, Mobile Edge Computing, Ultra-low Latency, 5G. 1

With the realization of 5G system which will become a fact by 2020, there is a great demand to achieve the Tactile Internet system. Tactile Internet system should handle a 1ms communication latency, which is the main problem of the system realization. One of the proposed system structures to achieve such latency is to build the system based on the multilevel cloud architecture and the 5G network structure. In this work, we build a system model for a multi-level cloud based Tactile Internet system. The model is used to find the system latency and evaluate the system performance. The proposed system is simulated and the results show that the system will achieve a lower latency than other known architectures. The proposed model also reduces the overall network congestion. It can be used to optimize the number of clouds in the system to achieve the best system performance.

Introduction:

Unlike the existing cellular networks, the future 5G cellular system will support new machine type communication services. By achieving the waited cellular system in 2020, Tactile Internet may become a reality. Tactile Internet will enable human -tomachine (H2M) communication and interaction, which consequently will enable a new era for the communication networks [START_REF] Aijaz | Shaping 5G for the Tactile Internet[END_REF]. Tactile systems will have massive applications in many fields such as smart cities, education, health care, augmented reality and smart grid [START_REF]The Tactile Internet[END_REF]. The main challenge with the design and development of the Tactile Internet is the 1ms round trip delay.

Mobile edge computing (MEC) is one of the key features that will enable the development and realization of the 5G system. MEC merge the three technologies of the mobile Internet, mobile computing and cloud computing [START_REF] Gai | Dynamic energy-aware cloudletbased mobile cloud computing model for green computing[END_REF]. The first technology is the mobile Internet which represents the wireless communication network or the cel-lular network. The second technology is the mobile computing that is represented by the techniques used for executing wireless communications. Mobile computing includes both hardware and software involved in the communication process such as protocols, user equipment and the network infrastructure. The last part is the cloud computing that provides a way for resources sharing or in other word deliver everything for the user as a service at the time and place the user need it.

Moving clouds closer to the user (approximately one hope away from the user) will allow to achieve lower latency and thus enable the realization of real time haptic communication that is known as Tactile Internet, which becomes a very promising area of research. MEC replaces the large and expensive data centers with small distributed cloud units connected to the cellular network [START_REF] Aijaz | Realizing the tactile internet: haptic communications over next generation 5G cellular networks[END_REF]. These small cloud units have limited capabilities in terms of processing and storage. There are a lot of studies that suggest places for the edge computing unit in order to achieve better latency.

In [START_REF] Ateya | Multilevel cloud based Tactile Internet system[END_REF] we suggest a multi-level cloud based Tactile Internet system. The system consists of three cloud levels: Micro-cloud, Mini-cloud and Core network cloud level as shown in Fig. 1. Micro-clouds are employed in each cellular cell and connected to the radio access network (RAN), and thus they are one hop away from users. Each group of Micro-clouds is connected to a Mini-cloud unit which has higher capabilities and can process much complex tasks. The second level of clouds (Mini-clouds) act as the controller for the first level (Micro-clouds) connected to it. They also can perform tasks that exceed the workload of the Micro-clouds connected to it and tasks that need processing capabilities greater than that of the Micro-cloud. Mini-clouds are connected to the core network cloud that represents the third level of clouds [START_REF] Ateya | Multilevel cloud based Tactile Internet system[END_REF].

Presenting a new level of higher capability clouds in the way between core network and RAN's clouds reduces the communication latency and the throughput. Thus, multi-level cloud based Tactile Internet system reduces the round trip delay by applying multilevel hierarchical of cloud units. In this paper, we build a mathematical model for the multi-level cloud based Tactile Internet system. The model is used to find the latency of the system and evaluate the system performance. In Sec. 2 the mathematical model of the system is discussed and the total latency is calculated. In Sec. 3 the system model is simulated over Java environment. Sections 4 concludes the paper and describes the future work.

Mathematical model

In this section, we introduce a mathematical model for the multi-level cloud based Tactile Internet system introduced in [START_REF] Ateya | Multilevel cloud based Tactile Internet system[END_REF]. The model is used to find the latency and evaluate the system performance. In order to design a low latency Tactile Internet system with the desired performance, a mathematical model for this case is introduced and all the important parameters are defined. Figure 2 illustrates the system model for the Tactile Internet based on the multi-levels of cloud units.

In our system, each cellular cell eNB is connected to a small cloud unit (Microcloud) Cmicro(i) with acceptable processing elements, where, i  {1, 2… M} and M is total number of Micro-clouds in the network. Each group of Micro-clouds are connected to larger cloud unit known as Mini-cloud Cmini(j), where, j  {1, 2… N} and N is the total number of Mini-clouds in the network. The Mini-cloud has higher processing and storage capabilities, and used to handle higher performance tasks that cannot be handled by Micro-clouds. Each Mini-cloud also acts as a controller for Micro-clouds connected to it. Mini-clouds represent the gateway between Micro-clouds and the core network. In our model, we assume that each Mini-cloud unit is connected to a fixed number S of Micro-cloud units.

The rate of tasks offloaded to the Micro-cloud unit changes based on the cell users demands. Thus, we assume the tasks randomly arrived based on the Poisson process with a Poisson rate of λi. Each cell produces a workload Wi to the connected edge computing unit Cmicro(i) with a Poisson rate λi. Every Micro-cloud can handle tasks offloaded by the corresponding eNB, but in case the processing demands of the current tasks is equal or higher than the maximum workload Wcmax(i), new tasks are moved to the Mini-cloud unit, until the resources of the Micro-cloud are released. Therefore, each Micro-cloud unit holds Wmicro(i) workloads and other non-handled tasks are shifted to the Mini-cloud unit. The computing time of Micro-cloud unit depends on the delivered work load Wdmicro(i).

Each Mini-cloud unit can handle up to Wmmax(j) of the work load, where, Wmmax(j) is the maximum workload of the Mini-cloud unit Cmini(j). Tasks that require higher processing capabilities than current free processing resources of the Mini-cloud unit are shifted to the core network cloud.

We consider the multi-server queuing model M/M/s [START_REF] Nair | The multi server M/M/(s, S) queueing inventory system[END_REF] to model the Micro-and Mini-clouds. For Micro-clouds the model is M/M/Smic and for Mini-clouds M/M/Smin, where Smic and Smin are the numbers of servers in the Micro and Mini-cloud unit respectively.

The total latency consists of the task's response time and the communication delay. The average response time for the tasks at the Micro and Mini-clouds is the sum of the queuing time and the processing time of the tasks. The average processing time of the tasks in the Micro and Mini-cloud units can be calculated as a function of the arrival rate λ, based on the M/M/S queuing model and the Erlang's C formula as deduced in [START_REF] Harchol-Balter | Performance modeling and design of computer systems: queueing theory in action[END_REF] [START_REF] Jia | Cloudlet load balancing in wireless metropolitan area networks[END_REF].

Where Tmicro-i is the average processing time of tasks in Micro-cloud unit i, Tmini-j is the average processing time of tasks in Mini-cloud unit j, Si is the total number of servers in the Micro-cloud unit i, Sj is the total number of servers in the Mini-cloud unit j, λi and λj are the arrival rates of the Micro-cloud unit i and Mini-cloud unit j and µi and µj are the corresponding service rates.

To simplify the calculation of the total latency we can assume that the latency function is a linear function and as indicated in [START_REF] Intharawijitr | Analysis of fog model considering computing and communication latency in 5G cellular networks[END_REF] this assumption is acceptable and verified. The total latency can be calculated simply as following: a-If the task is handled by Micro-cloud unit:

𝑇 𝑇-𝑚𝑖𝑐𝑟𝑜-𝑖 (𝑤 𝑖 ) = 𝑓 𝑐 (𝑤) + 𝑑 𝑐𝑒𝑙𝑙 = [𝛼(𝑤 𝑑𝑚𝑖𝑐𝑟𝑜-𝑖 ) + 𝛽] + 𝑑 𝑐𝑒𝑙𝑙 (4)
Where TT-micro-i is the total latency for the offloaded tasks of the Micro-cloud unit i, fc is the linear function that is used to determine the processing delay for the current work load and dcell is the communication latency inside the cellular cell. b-If the task is moved and handled by the Mini-cloud unit:

𝑇 𝑇-𝑚𝑖𝑛𝑖-𝑗 (𝑤 𝑗 ) = 𝑓 𝑐 (𝑤) + 𝑑 𝑐𝑒𝑙𝑙 = [𝛼(𝑤 𝑑𝑚𝑖𝑛𝑖-𝑗 ) + 𝛽] + 𝑑 𝑐𝑒𝑙𝑙 + 𝑑 𝐶 𝑀𝑖𝑐𝑟𝑜-𝑖 ,𝐶 𝑀𝑖𝑛𝑖-𝑗 [START_REF] Ateya | Multilevel cloud based Tactile Internet system[END_REF] Where TT-mini-j is the total latency for the offloaded tasks of the Mini-cloud unit j and 𝑑 𝐶 𝑀𝑖𝑐𝑟𝑜-𝑖 ,𝐶 𝑀𝑖𝑛𝑖-𝑗 is the communication delay between micro-cloud unit i and Mini-cloud unit j.

Simulation and results

In this section, we analyze the suggested system model for the Tactile Internet system in a simulation environment, after the mathematical model is defined in the previous section.

a-Simulation environment and simulation parameters There are many simulation environments that are used to simulate and deploy Micro-cloud and Clouds with different facilities and capabilities [START_REF] Wang | Mobile micro-cloud: application classification, mapping, and deployment[END_REF], [START_REF] Bahwaireth | Experimental comparison of simulation tools for efficient cloud and mobile cloud computing applications[END_REF]. These environments are able to create virtual machines (VM), remote procedure execution and web services with different capabilities. We developed a tool kit based on the CloudSim framework to analyze the system. The simulator is based on Java language and on the IDE NetBeans. The simulation is run on Window 7 basic (64-bit) and i7 Processor with 3.07 GHz of speed and memory of 8GB. We build a system consists of 300 Micro-cloud units distributed randomly and connected to 20 Mini-cloud units. Each Micro-cloud unit represents the offload to a cellular cell. Each Mini-cloud unit is connected and controls 15 Micro-cloud units. This number is a design parameter and should be optimized in terms of achieving the lowest latency and best performance of the system. We assume that all Micro-clouds have equal capabilities and also all Mini-clouds are the same. The application tasks are sent and distributed to the Micro-clouds randomly. All important simulation parameters are illustrated in table1.

b-Simulation results and analysis

We consider three simulation cases with three different values for Wcmax. In each case the latency for each Micro and Mini-cloud unit is calculated two times. The first is for the simulated system and the second is the theoretical one. The theoretical latency of Micro and Mini-cloud units is calculated using equations ( 4) and ( 5) based on the amount of workload delivered to the cloud unit.

In the first case, we assume a workload of 20 events per second and tasks higher than this workload will be directed to Mini-cloud unit. This will put a load on the Mini-cloud units. Figure 3 shows the total latency for each Micro-cloud unit for both theoretical and simulation models. The average latencies for the theoretical and simulation cases are 0.698 and 0.70 milliseconds respectively, and it seems to be very near for all Micro-clouds because they are of the same parameters. Theoretical latency varies from one cloud unit to another based on the amount of delivered workload since the tasks are distributed randomly. Figure 4 indicates the total latency for each Mini-cloud unit and the average total latencies for theoretical and simulation cases are 1.127 and 1.13 milliseconds. It is clear that the latency for Mini-cloud units is much higher as there is an additional communication hop between the Mini and Microcloud units. Without Mini-clouds, the latency is supposed to be much higher as the tasks would be delivered to the core network and the core network would be loaded with more workload.

In the second case, we increase the maximum work load of the Micro-cloud units to 30 and thus it should reduce the total load on the Mini-cloud units. This is because Micro-cloud units in this case handle many tasks and therefore reduce the number of tasks moved to Mini-cloud units. Figure 5 shows the total latency for each Microcloud unit compared to the delay according to the theoretical model. The average latencies for the theoretical and simulation cases are 0.838 and 0.84 milliseconds respectively and it increased because of the increased workload. Figure 6 indicates the total latency for each Mini-cloud unit. The average latencies are 0.978 and 0.98 milliseconds and this is less than the first case as the tasks moved from Micro-cloud units are less than that in the first case.

In the third case, the maximum work load of all Micro-cloud units is set to 40 and the delay for Micro and Mini-clouds is recorded and compared to the delay according to the theoretical model as indicated in Fig. 7 and8.

The time delay for each of Micro and Mini-clouds in the previous cases can be found to be relatively near to the theoretical results. The average delays for all Microcloud units and Mini-cloud units in the three cases are compared with that of the theoretical model in Table 2. Finally, the average workload for all Micro and Mini-clouds for each of the previous cases is illustrated in Figure 9.

Conclusion and future work

One of the efficient ways to reduce the round trip latency of data is to introduce a cloud level in the way between the eNB's cloud and the core network cloud. Multilevel cloud based Tactile Internet system introduces the Micro and Mini-cloud levels before the core network cloud. These two levels, as it was illustrated before, provides a useful and efficient way to reduce the round trip latency of data and produce away for offloading to reduce the workload delivered to the core network. The paper introduces a mathematical model for the Multi-level cloud based Tactile Internet system that is used to calculate the system latency. Simulation results verify the model and thus it can be used as a valid structure for the Tactile Internet system. The proposed system model can be used to solve the optimization problems of the Tactile Internet in terms of latency and energy efficiency.

Our future vision is to use the mathematical model to optimize the number of first level clouds connected to each Mini-cloud unit to reduce the round trip delay.

Fig. 1 .

 1 Fig. 1. Tactile Internet system [5].

Fig. 2 .

 2 Fig. 2. System model for the Tactile Internet system.

Table 1 .Fig. 3 .

 13 Fig. 3. Latency of Micro-cloud units in case (1).

Fig. 4 .

 4 Fig. 4. Latency of Mini-cloud units in case (1).

Fig. 5 .

 5 Fig. 5. Latency of Micro-cloud units in case (2).

Fig. 6 .

 6 Fig. 6. Latency of Mini-cloud units in case (2).

Fig. 7 .

 7 Fig. 7. Latency of Micro-cloud units in case (3).

Fig. 8 .

 8 Fig. 8. Latency of Mini-cloud units in case (3).

Fig. 9 .

 9 Fig.9. Average workload for each cloud level.

Table 2 .

 2 Average delay for Micro-and Mini-clouds.

	Case (1)	Case (2)	Case (3)

Acknowledgement

The publication was financially supported by the Ministry of Education and Science of the Russian Federation (the Agreement number 02.a03.21.0008).


Mehdi Guessous
email: mehdiguessous@research.emi.ac.mazenkouar@emi.ac.ma

Lahbib Zenkouar

A NURBS Based Technique for an Optimized Transmit Opportunity Map Processing in WLAN Networks

Keywords: Interferences, NURBS Surfaces, Radio Resource Management, WIFI, Wireless Local Area Networks

Dynamic Radio Resource Management helps overcome interferences in dense WLAN deployments. By processing data from upperlayers services, it could optimize and enrich end-to-end wireless client experience. This experience may be tight to a transmit opportunity function that hints on the radio interface condition, and effectiveness of the transmission itself from different points of view: application, service and underlying network infrastructure. Transmit opportunity calculations that are done at WLAN central intelligence level are resource consuming due to processing of huge amount of raw data from lower and upper system layers. One major part of this processing is the establishment of a coverage map that indicates in real-time and at any point the quality of a radio transmission. This work helps optimize transmit opportunity map calculations by exploring a novel approach based on NURBS Bézier surface technique. It demonstrates that map processings time and changes to radio environment could be enhanced.

Introduction

Among all issues that a wireless network may face interferences and their impact on the overall network performance are a major one as they occur at a very low system layer and are unpredictable. To tackle these issues three strategies are adopted in general: centralized decision-making intelligence, coordinated intelligence processing, and dynamic radio resource management.

A centralized decision-making intelligence processor, appliance or distributed, software or hardware, is necessary to ensure that network-wide applied radio strategy is coherent among all participating nodes in one hand, and that raw data used for decision-making itself is reliable on the other hand. The need for dynamic radio resource management arises from the fact that network configuration should react quickly to unpredictable changes in radio environment and trigger necessary actions to overcome any issues. These techniques may also help optimize overall network performance by processing transmission opportunities, as an example.

Dynamic Radio Resource Management (RRM) is the focus of this work and considers mainly these two inputs: lower layer physical inputs (RSSI, SNR, EIRP, noise, etc.) and upper layer service inputs (MAC layer, TCP/IP services and applications, etc.). Other complementary inputs may be provided by passive and active on-field site surveys. In addition to survey inputs, techniques such as Transmit Power Control, Dynamic Channel Assignment, Direction of Arrival estimation and Transmit Opportunity processing provide RRM with necessary data and tools to overcome interferences and adapt efficiently to changes.

Processing of this huge amount of raw data and estimatation of transmit opportunity at every point under coverage area in a timely manner is very resource consuming. It depends on: the number of points of interest under coverage area and external or internal events that may require a recalculation of all the topology. In this work we discuss a Bézier surface technique for optimizing coverage area transmit opportunity map calculations in frequently changing dense environment.

In the upcoming section, we present a foundation on unified WIFI architectures, opportunity map calculations and NURBS surfaces. In section III, we discuss more formally the problem and in section IV, we present our solution. Section V, is dedicated to our solution results evaluation and interpretation. In the end, we conclude and further our work.

Theoretical Background

This section gives an overview of methods used to process transmit opportunity maps as they relate to unified WIFI architectures. Additionally they introduce NURBS, a generalization of Bézier surface technique, for the same purpose of establishing a transmit opportunity map.

Unified WIFI Architecture

Autonomous or standalone access points architectures do not scale well with high number of access points and mobile devices networks that require high-class quality of service and security. Controller-based ones gradually replace these architectures. "Unified" architectures are managed centrally by a decision-making entity and integrate well with other end-to-end network parts: LAN, WAN, etc. from a QoS and Security point of view. Industry implements such central decision making processors mainly in three ways: physical controller-based, virtual controller-based, or access point distributed-based. In the latter implementation access points take over the controller role. The first two implementations require a controller, a virtual or physical appliance that is reachable by all network access points.

A good example of unified WIFI architectures is Cisco vendor physical WLC 5500 series controller-based one. It defines a communication protocol, CAPWAP, used by access points to build protocol associations to the main controller. It defines another over-the-air communication protocol, OTA, for access points to exchange some proprietary and standard patterns for management or control purposes. In addition, it integrates, at access point level, a set of on-chip proprietary RRM new features: Clientlink or Cleanair that are meant to monitor and measure radio environment characteristics and report them back to the controller via the already established CAPWAP tunnels. Based on this gathered information, the controller decides on channel assignment and corresponding power level tunings network-wide. Its decision conform to a pre-configured set of policies that define many configurable variables such as acceptable signal strength levels, tolerable noise levels, range of usable power levels, range of usable channel frequencies, etc. Then raw data, gathered by controllers, is forwarded to both Cisco Prime Infrastructure (PI) and Mobility Service Engine (MSE) platforms for different purposes mainly interferences spotting and analytics. Generated heat maps represent interferences occurence estimation and analytics on customers presence at a covered location.

Transmit Opportunity Map

In this work we focus mainly on transmit opportunity map calculations that represent co-channel interferences and upper-layer SLA inputs. Co-channel interferences are considered to have more impact on network performance than cross-channel ones, and are inversely proportional to transmit opportunity. SLA inputs, corresponding to upper-layer services QoS measurements, help minimizing processing hysteresis and errors.

Methods, to calculate radio coverage characteristics (interferences, signal strength, etc.), could be categorized as:

1. predictive: distance [START_REF] Ruslan | Cognitive radio-based power adjustment for Wi-Fi[END_REF] [2] [START_REF] Qiao | Adaptive transmit power control in IEEE 802.11a wireless LANs[END_REF], barycenter [START_REF] Kapadia | Interference-constrained Wireless Coverage in a Protocol Model[END_REF], direction based [START_REF] Guessous | Cognitive Directional Cost-Based Transmit Power Control in IEEE 802.11 WLAN[END_REF] or variants, 2. experimental that are based on on-field site surveys, 3. or hybrid that are a mix of both approaches.

In distance-based models distance estimation of two interfering nodes is necessary to evaluation the amount of interferences. Barycenter-based methods tend to reflect weighted impact of each transmitting point on the others. It results in partitioning of the overall coverage area into zones that are under unique control of each node and that are dependent on the weight each transmitting point may have over time which is not the case of distance based ones. Direction-based methods add more granularity and scalability to previous methods by reconsidering transmission in some areas that were considered as no-talk by other models. In addition, they hint more precisely on hidden interferers and maximize transmission opportunities by qualifying and multiplying transmit directions.

Experimentally based methods have the advantage of reflecting the real measurements. These methods are based on specialized equipments and products such as AirMagnet or Ekahau. However, they lack the ability to adapt to dynamically changing radio environments over time and require important human, financial and system resources.

To evaluate a method over another one, three criterions may be used: accuracy of transmit opportunity calculations at any point, calculation time, and recalculation time in case of network change.

Heuristic methods seem to offer the highest accuracy level. Barycenter-based models seem to have advantage over distance-based ones in terms of measurement accuracy. However, neither of them can scale with frequently changing network processing. In the upcoming sections, we explore a new method that is NURBS surface based, and evaluate how it can scale with frequently changing dense network deployments.

NURBS Surface

This subsection is an introduction to a widely used technique in computer aided graphical design fields that are NURBS surfaces which are a generalization of the much known Bézier-Bernstein and B-Spline curves. A NURBS surface of degree p and q is defined as:

S(u, v) = m i=0 n j=0 N i,p (u)N j,q (v)w i,j P i,j m i=0 n j=0 N i,p (u)N j,q (v)w i,j (1)
Where, u, v -are variables in [0, 1] P i,j , w i,j -are control points and corresponding weights m, n -correspond to number of control polygons and points {t 0 , t 1 , ..., t m+p+1 }, {t 0 , t 1 , ..., t n+q+1 }-are knots that correspond to control polygons and points respectively p, q -function degree that corresponds to number of polygon, point knots minus number of control polygons, points minus 1 N i,p and N j,q are the B-Spline basis functions that describe surface control polygons, that are matched by u variable, and curves control points that are matched by v variable. They are given by these formulas:

N i,0 (t) = 1 if t i ≤ t < t i+1 0 otherwise (2) N i,j (t) = t -t i t i+j -t i N i,j-1 (t) + t i+j+1 -t t i+j+1 -t i+1 N i+1,j-1 (t) (3)
Where, t is a variable in [0, 1] and j an integer different from 0.

Our solution takes advantage of introduction of these new core concepts:

1. control points that are a special set of coverage area points that do influence radio characteristics, 2. weighting of control points that allows impact classification of these control points for a specific measurement or at upper-layer, control over the transmit opportunity, 3. knots that can be tight to the accuracy of our calculations: the more knots we work with and their distribution, the more accurate is our processing of environment attributes.

To ease our preliminary work we consider these simplifications: control polygons and control points numbers are the same, corresponding knots numbers are the same, and knot vector is uniform.

Problem Statement

In this section, we formally state the problem. For the rest of this paper let us define, A s , A d , A c -sets of network mobility devices: mobile stations and access points, measurement points referred as distribution points in this paper and points under the whole coverage area, AP i , ST A j -i th access point and j th mobile station respectively, P c,i , P d,i , P s,i -are i th points corresponding to A sets respectively on a 2-D plan grid, O() -function, is the transmit opportunity at every coverage area point.

Each AP i has a communication path to a WLAN controller for radio measurement and reporting purposes. In addition, we consider that each ST A i has a virtual communication path to the controller via corresponding AP i of attachment and for the same purpose. P d,i are defined as virtual points on grid such as to confine each ST A i or AP i to the smallest possible square obtained by dividing uniformly the grid horizontally and vertically. It is to note that the number of P d,i depend on the distribution of AP i and ST A i on the grid and not on their number. A s is a subset of A d that is itself a subset of A c . To ease this preliminary work we consider that A d set is sufficient for accurate O() calculations.

Let us define, T m , T ch , T m,intf , T m,cpu -coverage map processing time, map change processing time, time to report a measure, and time to process a transmit opportunity, T, T n -whole cycle and n-cycle processing times, N, M -number of control points and mobility devices respectively.

T m and T ch are required for complete map calculation and recalculation in case of changes in environment. A requirement for map calculations is that all control points report data in a timely manner. In addition, changes to radio environment should be paced enough to allow stable transition from an old map condition to a new stable one. T m could be further divided into two times: T m,intf and T m,cpu . T m,intf corresponds to the situation where a control point is an AP or STA and it includes necessary time for radio measurement at point level and reporting it back to the controller. On the other side T m,cpu corresponds to the estimated time for transmit opportunity calculation by algorithms at controller level. T ch may correspond to a periodic interval at which a new map calculation is triggered and necessary time for it. T m,intf is a real-time measure and is dependent on vendors hardware and control plane network condition. Then this work focuses on T m,cpu and T ch times. T m,cpu depends on the used algorithm at controller level.

If distance-based or beam direction-based, transmit opportunity at any given control point except from AP or STA could be approached by a weighted function of intersections with all other transmitting sources radio patterns. In case of barycenter-based algorithms, the transmit opportunity is more related to point localization within a discovered coverage zone.

Then,

T m,cpu (DIST AN CE) = (N -M ) * M * T intersection (4)
T m,cpu (BARY CEN T ER) = (M -2) * T iteration + N * T zone (5)
Where T intersection is the required time for processing an intersection between two transmit patterns in the coverage area. T iteration is the required time for an algorithm iteration. In case of Delaunay triangulation based calculations, iteration may correspond to a circumcircle center calculation. T zone is the time required to locate a point in a defined zone and to deduce its corresponding transmit opportunity value.

The total time for a whole calculation cycle that include k -1 change is equal to:

T (DIST AN CE) = T m,intf + k * (N -M ) * M * T intersection (6) T (BARY CEN T ER) = T m,intf + k * ((M -2) * T iteration + N * T zone ) (7)
Barycenter algorithms calculations time is negligible to distance-based one when N and M are low. For high N and M values, distance-based algorithms are more scalable. We notice also that barycenter algorithms performs better when the M is roughly a half of N . The upcoming section describe our solution aimed at scaling barycenter-based algorithms like processing times using generalized Bézier NURBS surfaces calculations. It aims also at reducing processing time for higher equivalent N and M numbers that is more relevant to distance-based algorithms like processing.

Our NURBS-Based Solution

Our transmit opportunity calculations are based on Bézier NURBS surfaces notions. Two algorithms run for this purpose. The first one, NTO-CP, processes transmit opportunity at every coverage area point. The second one, NTO-CH, processes changes to the current transmit opportunity map.

NTO-CP Algorithm

The aim of this algorithm is to calculate the transmit opportunity at every coverage area point and:

1. to reduce the number of control points and still obtain the same results, 2. optimize knots number corresponding to variables u and v.

Lets A be the set of P i,j control points. First, this set initializes to correspond to mobility devices: AP and STA as they have the ability to report raw radio data measurements and are, at the same time, the main source of interferences. To ease this work, lets correspond P i,j values to nodes transmission power levels. Then we reorder A set by increasing power levels, weight at maximum the first node, calculate S() at all the other A set nodes and, compare them to reported measures. If reported measures after and before weight change are the same and if S() at these points is the same, then we move this node from A set to a new set A inef f of ineffective control points. A inef f defines a monitoring points set that are coverage area points that do not have effective control over the transmission opportunity map but still monitor radio interface and report radio raw data. If S() is not the same as reported measures, we define a new hysteresis value, ERR or variance that can be seen as a calibration of the actual transmit opportunity function calculations. A i correspond to the set of P j node that are affected by P i maximum weighting.

For this preliminary work we consider that knot vector is the same for u and v variables. We divide the coverage area into a maximum of three zones: one central and two suburbans. In each region, we elect a zone control point that matches these two criteria:

1. covers the all-corresponding zone, 2. and is the farthest point from the central zone or central zone control point.

Then we set these three zone control points transmit power level at maximum and we turn other control points to monitoring state that corresponds to the lowest transmit power level. We initialize next, knots number to match control points number. If the reported measures at these points are the same as the calculated ones we keep the current number, otherwise we double it until the acceptable hysteresis is satisfied. Further work may consider knots distributions that are different per zone and per direction u or v. The following algorithm details this procedure:

This procedure is done only at system initialization and subsequently for any newly added control point or at sufficiently large periodic time interval to guarantee that A set is refreshed with accurate information. The second part of calculations focuses on processing of control points zones that are meant at optimizing knots numbers for calculations accuracy. For the rest of this algorithm let us define: w avg,reported -the average of reported measure of P i as seen by all other nodes, P 0,pseudo -the nearst point of A -A inef f from the processed pseudo-node, Algorithm 1 NTO-CP algorithm: Part1

1: procedure Effective-A(A, wmax) 2:
for i ← 0, |A|, i + + do 3:

wi ← wmax 4:

A inef f ← ∅ 5:

Ai ← ∅ 6:

for j = i ← 0, |A|, j + + do 7:

if w j,af ter = w j,bef ore then 8:

A inef f = A inef f {Pi} 9:
if S j,af ter = S j,bef ore then 10: end for 20: end procedure Z 0,pseudo -the central zone control points set covered by pseudo control point at maximum weight, Processing of effective control points requires one by one node weighting at maximum and measurement of its effect over other control points. This weighting may be: an increase of transmit power level, a high QoS classification, etc. a mix of them or other variables that are under system management control and that can maximize the opportunity function. Zones processing and determination of pseudo control points helps optimizing S(u, v) knots number for calculation accuracy purposes.

ERR = max(ERRnew,
We double the initial number of knots until S() calculation hysteresis is satisfied in each zone. We then update the current optimized knots number to match the maximum among all defined zones.

NTO-CH Algorithm

A change may affect a zone, multiple zones or the entire network. This algorithm task is to scope the change impact so that only pertaining sets control points are processed to reflect the new change. It is to note that zones used in NTO-CH are different from ones used in NTO-CP algorithm, as the purpose is different. The idea here is to find an optimized number of zones that hints on the impact of a given change.

Not all changes are relevant and maybe classified to match one of this set of categories: minor, medium, or high. To ease this preliminary work only high

Algorithm Time

Calculation time corresponds to one initialization and k -1 changes. This time is compound of effective control processing time, optimum knots number processing time, and change processing time. Effective control point processing is unique to this method and it requires running S(), M * (M -1) times. Optimum knots number processing time corresponds to S() calculations at every zone control points and iterations until required accuracy is achieved. Then if α, µ, and β, are number of iterations, number of zones and number of ineffective controls points respectively, the time is given by: α µ * (M -β). It is to note that the first purpose of zoning is to allow parallel processing in every zone.

T ( N U RBS) = M 2 -(1 + k -α µ )M + kηN + (k µ + β µ -α β µ ) ( 8
)
Where η is a value that represents the scope of the change.

We apply these numerical simplifications: α = 1, µ = 3, η = 0.25. α = 1 as one iteration is sufficient for an acceptable accuracy with regards to other algorithms, and because at initialization, the number of knots could be set to a higher level. It influences only S() calculation time in case of higher knots number which is considered insignificant in this paper but may be considered in further work if necessary. µ = 3 is more to allow parallel processing when end for 48: end procedure computing zones and may correspond to non-overlapping channels. η = 0.25 supposes that most changes affect only specific zones and do not span multiple zones. It is sufficient for this preliminary work that shows our solution design advantages.

Results Evaluation and Conclusion

At this level, our evaluation is based on Matlab simulations of our solution, distance and barycenter based ones. Next step would consider implementing this solution on Linux based AP and STA in environments including vendorworking solutions. At the same time, we consider that at coding level we could get concluding results with regard to competitors and other related work.

First, in Fig. 1, we vary N and M numbers and observe the variation of processing times of the three methods. For higher N numbers our solution starts performing better than both other solutions when M is almost greater than 10% of N . At higher M values, barycenter-based solution is no more scalable. For lower M and N numbers barycenter-based solution is better than our solution and distance-based ones. Then it is more suitable for lower density and sparse deployments. For high-density deployments which correspond to higher N numbers and with lower M number our solution starts performing better than barycenter-based ones when N number is roughly four times the M number.

Next, we evaluate the impact of number of changes over our solution and the two other solutions. Fig. 2 shows results for the three algorithms. Changes impact over barycenter-based algorithms is very noticeable for higher numbers of distribution points and increasing number of mobility devices. Distance-based algorithm seems to depend solely on the number of affecting changes. Our solution algorithm seems to depend slightly on both the number of changes and mobility devices. We see clearly that for lower number of mobility devices, mainly access points, and significant number of distribution points our solution performs better in case of frequent changes. if wi ≥ wC1 then 5:

P j,change ← Pi 6:

Z j,change ← {Pi} 7: j = j + 1 8:

else if wC1 > wi ≥ wC2 then 9:

Z j,change ← {Pi} {Pi+1} Pi+1 ∈ Ai, wC1 > wi+1 ≥ wC2

Otherwise break 10: i = i + 1, j = j + 1 11:

else if wC2 > wi ≥ wC3 then 12:

Z j,change ← {Pi} {Pi+1} {Pi+2} Pi+1, Pi+2 ∈ Ai, wC2 > wi+1, wi+2 ≥ wC3

Otherwise break 13: i = i + 2, j = j + 1 14:

end if 15:

end for 16: end procedure

Algorithm 4

 4 NTO-CH algorithm1: procedure Ch-Zones 2:j ← 1 3:for i ← |A -A inef f | do 4:

Fig. 1 .Fig. 2 .

 12 Fig. 1. Opportunity processing time comparison between our solution, distance and barycenter based algorithms

  Pi s. t. Pi ∈ A -A inef f -Z 0,pseudo -Z 1,pseudo 35: end procedure effect changes are considered and all other changes are considered insignificant. A change may correspond to a newly reported RSSI or any other relevant variable.

	Algorithm 2 NTO-CP algorithm: Part2
	21: procedure CP-Zones(A, wmax)
	22:	∀Pi ∈ A -A inef f , wi ← wmax
	23:	for i ← 0, |A|, i + + do
	24:	wi ←	w i w i +w avg,reported
	25:	end for
	26: 27:	P 0,pseudo ← w i * P i w i ∀Pi ∈ A -A inef f -P 0,pseudo , wi ← wmin
	28:	P 0,pseudo ← wmax
	29:	if Z 0,pseudo = A -A inef f then
	30:	P 1,pseudo ← Pi ∈ Z 0,pseudo
		s. t. ∀j, j = i, wi = min(wi, wj)
	31:	else
	32:	P 1,pseudo ← Pi
		s. t. Pi ∈ A -A inef f -Z 0,pseudo
	33:	end if
	34:	P 2,pseudo ←

Acknowledgment

We would thank colleagues : researchers, engineers, and anonymous reviewers for sharing their precious comments and on-field experience that improved the quality of this paper.


Christos Bouras
email: bouras@cti.gr

Georgios Diles
email: diles@ceid.upatras.gr

Distributed Sleep Mode Power Control in 5G Ultra Dense Networks

Keywords: Femtocells, Sleep mode, Power control

The upcoming 5G networks are characterized by ultra dense deployments of small cells. These structures are capable of providing the much desired increase in capacity and data rates. The limited resources though present challenges on how they will be shared among the high number of base stations. Distributed coordination will play a big part in resource allocation. In this paper, we present a power control mechanism for dense femtocell deployments which utilizes sleep mode strategies and spectrum sharing among users. The mechanism exhibits increased throughput for the femtocell subscribers, preserving non-subscribers performance and increasing the network's energy efficiency.

Introduction

There is a consensus that in order to reach the massive targets of next generation mobile networks, a tremendous amount of base stations will be required. Some have even estimated that at some point the access points will surpass the number of users [START_REF] Okino | Pico cell range expansion with interference mitigation toward lte-advanced heterogeneous networks[END_REF]. However, this massive deployment can be problematic in terms of interference and power consumption especially for the macrocells and small cells which usually compete for the available resources, they often adopt restrictive access policies and in contrast with the M2M communications, they have a high power consumption. Thankfully, this is recognized by the community which therefore has made crucial the issue of interference mitigation for better performance and the reduction of energy consumption of new mobile networks both for cutting costs for the operators and ecological sustainability [2].

A combination of the above goals can be seen in base stations' sleep mode. Sleep mode is a major part of energy reduction in the macrocell tier. This is when the macrocell base stations decide to turn into a low power node when traffic demand does not justify their operation (i.e. at night) and can be met by the adjacent macro base stations. Due to the massive penetration of small cells, it is evident that these techniques will have to address the small cell tier too. While micro or pico cells are easy to handle, since for the majority they are deployed and controlled by the operator who can determine their operation in a centralized way, femtocells are not.

Due to their ad-hoc deployment and the exclusive access permissions, the macro cell strategies are not that easily transferable in the femto tier. For example, one cannot centrally determine that a private owned femtocell must be deactivated, both because such action is considered invasive and because traffic cannot be easily passed to adjacent femtocells due to the Closed Subscriber Access policy of most femtocells. However, this can be facilitated if we find a way to combine the sleep mode of one femtocell with the interference mitigation for the users of another one.

Sleep mode of femtocells is an active research field. In [START_REF] Ashraf | Sleep mode techniques for small cell deployments[END_REF] the authors propose energy-efficient algorithms that lead small cell base stations to sleep mode in a bid to reduce cellular networks power consumption. Three different strategies for algorithm control are discussed, relying on small cell driven, core network driven, and user equipment driven approaches each leading to different energy savings. The authors in [START_REF] Mugume | Sleep mode mechanisms in dense small cell networks[END_REF] also compare different sleep mode mechanisms in dense small cell networks to conclude that sleep mode can lead to significant energy efficiency especially with the careful selection of the base stations.

A cluster-based approach is incorporated in [START_REF] Samarakoon | Dynamic clustering and sleep mode strategies for small cell networks[END_REF] to improve the energy efficiency of small cell networks. Specifically, the clusters use an opportunistic base station sleep-wake switching mechanism to strike a balance between delay and energy consumption with gains that reach 40% in energy consumption and 23% in load. The work in [START_REF] Ali | Femtocell sleep mode activation based interference mitigation in twotier networks[END_REF] on the other hand, utilizes sleep mode strategy but focuses on mitigating interference for macrocell users. The evaluation showed that the strategy achieved better performance along with significant power savings.

In this paper, we extend the mechanism that we introduced in [START_REF] Bouras | Sleep mode performance gains in 5g femtocell clusters[END_REF] that aims to reduce the number of active femtocells in the area without compromising their subscribers performance. The novelty of the mechanism is that it strives for deactivating a base station even when its subscribers are active by combining sleep mode and hybrid access operation in femtocell clusters and enforcing a restriction policy that guarantees performance gains. In our initial approach we were based only in spectrum sharing waiting for the restrictions to be met. This led to a very small number of cases that met the requirements which resulted in a small number of deactivated femtocells.

Instead in this paper, we introduce power control in order to increase that number by investigating what the power level of the femtocells should be in order to meet the performance restrictions. If such level exists and it is feasible, subscribers of the femtocell that turns to sleep mode are handed over to the neighbour femtocells. On the other hand, subscribers of the femtocell accepts willingly the non-subscriber users since the increased power level of their base station and the reduced interference due to inactivation of the nearby femtocell should cause a boost to their performance. We also expand the mechanism requirement set in order to protect femtocell users that belong to the same cluster but do not participate in the user exchange. Ultimately, the addition of power control leads to fewer concurrently active base stations leading to increased capacity gains for the subscribers and increased energy efficiency.

The structure of the rest of the paper is as follows: The next section presents the model of interference between the base stations in the femto and macro tier and we describe how sleep mode works in femtocells. The third section provides a detailed analysis of our proposed mechanism. In the fourth section, the evaluation of our proposal is taking place, providing extensive results obtained through simulations. Finally, the last section summarizes our conclusions and draws future research steps.

System Model

For the evaluation of our method we focus on users' performance gains regarding the impact in data rate for femtocell subscribers and macrocell users. Below we describe the model we used as basis for the formation and evaluation of our proposed scheme presented in the following section and the details of the sleep mode operations.

Pilot Power

In order to evaluate the performance repercussions of our setup to users data rate, we utilize Long Term Evolution Advanced (LTE-A) architecture, and its Orthogonal frequency-division multiple access (OFDMA) technology. OFDMA is characterized by flexible allocation of available spectrum resources to users, allowing complex spectrum allocation strategies. Since dense small cell deployments will mostly back up the demands of dense populated area, we follow the LTE-A directives for urban environments for the calculation of necessary parameters, such as path loss and gain [8].

For the power levels of each femtocell, we take into account the position of the femtocell inside the macrocell. Since we examine most co-channel transmission between the macro and femto tier, the effective range of the femtocells would be totally different between a femtocell near the edge and near the center of the macrocell due to interference. Thus, we adjust femtocells' power levels towards a constant radius of coverage [START_REF] Claussen | Performance of macro-and co-channel femtocells in a hierarchical cell structure, in Personal, Indoor and Mobile Radio Communications[END_REF], by taking into account the power received from the closest macrocell at a target femtocell radius r. A maximum power level P max is also set:

P f = min (P m + G -P L m (d) + P L f (r), P max) . (1)
with P L f (r) denoting the line of sight path loss at the target cell radius r, P m the transmit power of the closest macrocell and G the antenna gain. P L m (d) is the average macrocell path loss at the femtocell distance d (excluding any additional wall losses).

Sleep Mode

The sleep mode model considered in this paper is based in [START_REF] Claussen | Dynamic idle mode procedures for femtocells[END_REF] and [START_REF] Ashraf | Sleep mode techniques for small cell deployments[END_REF]. During this mode, most components of the femtocell switch off, thus contributing to the power savings, apart from the ones needed for connection with the backhaul network and the ones required for sensing when a nearby subscribed user is transmitting in order to set the femtocell to full operational mode when needed.

Sensing is done with an additional component-"sniffer" that is able to sense rises in received power on the uplink frequency band. Such rise would indicate a connection established between a user and the macrocell. Setting a threshold on the sensed rise accordingly to reflect the desired coverage radius of the femtocell, the sniffer wakes up the femtocell if the threshold is surpassed and the user is allowed to access it through a handover procedure. This approach allows multiple components of the femtocell to be switched off such as the radio frequency (RF) transmitter and receiver leading to a reduction in power consumption close to 40%. Drawbacks of this approach include the requirement of a handover from macrocell to femtocell and that it is limited by the fact that underlying macrocell infrastructure must be present. However, this limitation falls within the scope of our paper since we explore dense urban scenarios. Also, the additional signaling due to sleep mode integration and handover requirement is more than compensated by the reduction of femtocell functionalities in sleep mode, resulting in the reduction of overall signalling compared to the same scenarios if femtocells would always operate in full mode [START_REF] Claussen | Dynamic idle mode procedures for femtocells[END_REF].

Throughput Calculation

When the power of the femtocells has been deternimed (either the pilot or the proposed) we derive the Signal-to-interference-plus-noise ratio (SINR) of each user. The SINR of a user u on each sub-carrier k, served by either macrocell or a femtocell, is given by:

SIN R u,k = P B,k G u,B,k N 0 ∆f + B P B ,k G u,B ,k . (2)
where P B,k is the transmit power of user's serving base station B on subcarrier k, and G u,B,k is the channel gain between user u and its serving cell B on sub-carrier k. Similarly, P B ,k and G u,B ,k denote respectively the power of every other interfering base station (either femtocell or macrocell) and the gain between them and the user u. N 0 is the white noise power spectral density, and ∆f the sub-carrier spacing.

From the SINR we then calculate the capacity of the user u on that subcarrier k by [START_REF] Lei | A novel multi-cell OFDMA system structure using fractional frequency reuse[END_REF]:

C u,k = ∆f • log 2 (1 + αSIN R u,k ) . ( 3
)
where α is defined by α = -1.5/ln(5BER). Based on the spectrum allocation and the subcarriers utilized by the user, we evaluate the overall throughput of serving base station by [12]:

T B = u k β u,k C u,k . (4)
where, β u,k notifies the sub-carrier assignment for the users. When β u,k = 1, the sub-carrier k is assigned to user u. Otherwise, β u,k = 0.

Proposed Scheme

The ad hoc nature of femtocells deployments is a critical factor that depending on the circumstances may lead to a success or a failure. On the one hand, the flexibility they provide and the targeting of very specific local needs is very helpful. On the other hand, the lack of central coordination for their placement may lead to severe problems. The deployment of macrocell layer base stations is carefully planned regarding the location and the spectral usage, in order to gain the maximum of their utilization and avoid large interference issues. If no such planning took place, and base stations happened to be in very close distance and using same frequencies, the interference would be catastrophic and handovers would quite frequently occur.

Unfortunately, in femtocell layer this could be a usual scenario for the upcoming ultra dense networks. The situation gets worse, if we also consider that private owned femtocells operate mostly in closed access mode, making the handover option to other femtocells impossible. The accumulative interference of multiple nearby femtocells for an apartment residents in a building would easily lead to the acquirement of a femtocell by that household, too. It is easy to conclude that with every deployment of a femtocell in a building, the need of the neighbors for their own femtocell increases, thus eventually, every apartment in that building will have a femtocell.

This however represents a disparity, because the number of femtocell base stations will not reflect the actual needs in data rates, capacity or connections but solely the exclusivity of usage between separate apartments. This situation causes mainly three problems. Firstly, the subscribers of a femtocell will suffer by the accumulative interference of all the other nearby femtocells. Secondly, any individual not belonging to any of the femtocells access list, would also suffer tremendously. Thirdly, the energy consumption of the practically redundant base stations should be avoided.

We address the above by proposing a scheme that combines two operating modes of the femtocell: The hybrid access mode and the sleep mode. Sleep mode as explained in Sect. II, is a mode used in base stations where most but not all of their functionalities have been turned off. On one hand this provides energy efficiency when full operation is not required, and on the other hand the transition to full operating state is rapid. A waking signal is usually used in order for the femtocell to return to full operation, either from the user, from the network or from the femtocell itself [START_REF] Ashraf | Sleep mode techniques for small cell deployments[END_REF][START_REF] Mugume | Sleep mode mechanisms in dense small cell networks[END_REF] with every approach resulting in different advantages and disadvantages in energy efficiency and in functional requirements.

In sleep mode we consider zero interference towards non-subscribed users and no serving of subscribed ones.

Hybrid access mode is an operation state for a femtocell where it adapts an intermediate policy regarding which users it will admit. While closed access restricts access to users enlisted to its Closed Subscriber Group (CSG) of the femtocell, and open access allows everyone in its range, hybrid access presents a golden mean. While it preserves its main portion of resources for its CSG users, it may allow external users in their range as well, usually under custom policy restrictions. The main problem for the adoption of hybrid or open access is that owners of private femtocells are justifiably reluctant to offer their resources to external users. Hybrid access admission policies usually tackle this problem through pricing schemes where the owners are compensated for their resources' provision. The same is true for the owners of the femtocell that goes to sleep mode. In most papers, sleep mode is activated only when the traffic demands of their users is zero because otherwise they will experience performance disruptions. Instead, in our case, we follow a different approach that uses a combination of hybrid access and sleep mode to provide incentives of energy savings and data rate gains. Femtocells with active users may turn to sleep, while their users' reallocation is possible through the hybrid access of their neighboring femtocells. This exchange allows the users to willfully adopt these modes, since policy restrictions require performance improvement. As a result fewer base station will be active, while user experience stays the same or improves.

Thus, the mechanism first investigates if a femtocell is eligible to turn to sleep mode, by examining clusters of femtocells and test if a reallocation to a neighboring femtocell is possible. Incentives for the femtocell to turn to sleep mode or to hybrid access are provided through requirements. First, each user belonging to the candidate for sleep mode femtocell has to at least regain its performance when reallocated to another femtocell. This is expressed by: T HR N ew ≥ T HR Old .

(

) 5
The user will of course try to connect to an active femtocell, which will be serving his own subscribers at the time. That means it will probably get a portion of spectrum resources of what it enjoyed by its own femtocell. A part of this reduction is compensated by the reduced interference in the area since a close by femtocell will turn to sleep. The rest might require an increment in the power levels of the new base station in order to reach the user's prior performance. Searching for the required power increment, according to Sect. II, based on the previous equation we have:

P Inc ≥ R * ∆f + B P B G u,B -P Old * G u,N G u,N . (6)
where ∆f + B P B G u,B denotes the interference in the user when connected to the new femtocell, G u,N his/her gain relative to the base station he might migrate, P Old the power of that station and R is:

R = (1 + aSIN R Old ) (N2+1)/N1 -1 a . (7)
where SIN R Old is the SINR that the user would experience if served by the original femtocell. N 2 is the number of users served by the neighbour and N 1 is the number of users served by the origin femtocell. Power increment is also subject to a maximum allowed power transmission of the femtocell. A similar incentive is required for the users of a femtocell candidate to adopt hybrid access. Thus hybrid access is adopted only for users that come from a neighboring sleeping femtocell. In addition, the gains of it turned to sleep mode due to less interference must compensate the reduced spectrum utilization due to hybrid access. Again, added to the reduction of interference due to the sleeping neighbour, a power increment may be required to compensate for the reduction of further spectrum resources:

P Inc ≥ R * ∆f + B P B G u,B -P Old * G u,N G u,N . (8)
where ∆f + B P B G u,B denotes the interference of the subscriber, G u,N his/her gain as before, P Old the power of the femtocell and R this time:

R = (1 + aSIN R Old ) (N2+1)/N2 -1 a . (9)
Estimating the required power level that will meet both of the demands, a final check is taking place for the rest of the femtocells of the same cluster that do not participate in that particular user exchange. The check makes sure that no subscriber of these femtocells experiences decrease in his/her throughput. This is possible when these users benefit by the deactivation of the slept femtocell at least as strongly as they are affected by the increase on their neighbour's power transmission. If this check returns successful the deactivation and the user exchange is finalized.

Performance Evaluation

Simulation Parameters

In our simulations, we considered a network of 9 macrocells with the base station located at the center of each cell and transmitting at 46 dBm. The cells' radius was 250 m. In this area we randomly deployed multiple femtocells and their subscribers. Each femtocell could have up to three transmitting subscribers at the same time. Macrocell users were also randomly deployed. Parameters values have been based on 3GPP directives from LTE-A and the LTE simulator in [START_REF] Simsek | An LTE-femtocell dynamic system level simulator[END_REF]. Results depicting cumulative distribution function (CDF) show the average obtained by 20 repeated simulations. An instance of the simulation topology is shown in Fig. 1.

Simulation Results

Fig. 2 shows the number of slept femtocells for different densities when the simple form is adopted and when it is enhanced with power control. Simple form represents our initial approach where no power increase was allowed in order to meet the performance requirements. The results are somewhat expected, since initially the restriction for better performance for every user with one less base station is quite strict making the possibility for a slept femtocell thin (i.e. 5 femtocells turned to sleep mode when 50 clusters were formed). Power control causes a dramatic increase in slept femtocells quadrupling the number to 20. Even if we neglect the capacity gains that we present later, and consider the worst case where users' data rate did not experience either an increase or a decrease, the energy gains of the mechanism as a result of the deactivated femtocells are substantial. However, the worst case regarding the users' throughput does not happen. Since the mechanism requires every user involved in the slept or hybrid femtocell experience the same performance, if the exchange is feasible, it adopts to the user who is in more danger to experience deterioration. That provides a margin of improvement for the users who were not in the danger zone, i.e. users who would not face decrease in their data rate even with the initial power transmission levels. This improvement can be clearly seen in Fig. 3 which displays the CDF of the throughput exhibited by subscribers of femtocells that are part of a cluster (independently of having eventually a slept femtocell in its members or not). The mechanism in its simple form showcases an improvement compared to the initial state where every femtocell is activated and operates in CSG , whereas the power control version increases the performance substantially.

Total clusters formed

Data rate of femto users in clusters (Mbps) Since these scenarios are characterized heavily by their tendency in tradeoffs, there are also users who are going to be influenced negatively. Fig. 4 depicts the CDF of the macrocell users that were found in the range of one (or more) femtocell that belong in a cluster. The simple strategy mainly resulted in the deactivation of femtocells within a cluster. Remaining operating stations did not increase their power levels, at least not due to the mechanism requirements. This had a beneficial effect on this type of users who saw the overall interference in the area to mitigate. Unfortunately, in the power control version, any mitigation due to femtocell deactivation is balanced by an equal increase due to power transmission increase. Therefore, the macro users' throughput is significantly behind the simple sleep strategy version. It is worth to note however, that compared to the initial state macro users mostly retain their performance without experiencing any downfall.

Conclusions and Future Work

In this paper we investigated performance gains for our proposed sleep mode and hybrid access mechanism extending its benefits by introducing a power control strategy. The mechanism tries to overcome the base station density caused by Data rate of macro users within clusters range (Mbps) We managed to increase substantially the number of femtocells turned to sleep mode by simply allowing the increase in power transmission in the hybrid access femtocells that admit neighbour femtocell's users. Balance is enforced by seeking the maximum increase in power control that retains the performance of the subscribers involved in the user exchange and at the same time avoiding negative influence to the close-by subscribers of the same cluster's femtocells. As a result the overall capacity provided by the femtocells to their subscribers is increased substantially without compromising any individual subscribed user. The increased energy efficiency of the enhanced approach is also noted. On the downside, macrocell users lose the benefit they enjoyed by the deactivation of some nearby femtocells due to the increase in power transmission of the remaining operating stations. However, compared to their initial state, no substantial decrease is observed. Future extensions of this work could include the estimation of energy efficiency and performance gains of the algorithm, adding user mobility, and examining different traffic models.

Fig. 1 .

 1 Fig. 1. Instance of the network

Fig. 2 .

 2 Fig. 2. Number of femtocells turned to sleep mode depending on the femtocell deployment density

Fig. 3 .

 3 Fig.3. CDF of the data rate of femto users that are subscribers to femtocells that are members of clusters.

Fig. 4 .

 4 Fig. 4. CDF of the data rate of macro users that are are affected by femtocells that are members of clusters

Table 1 .

 1 Simulation Parameters

	Parameter	Value
	Macrocells	9
	Macrocell radius	250 m
	Femtocells	250-550
	Subscribers per femtocell 1-3
	Macrocell users	140
	Bandwidth	20 MHz
	Carrier frequency	2 GHz
	BS transmit power	46 dBm
	FBS max transmit power 18 dBm