Patcharee Thongtra

Arve Finn
email: finnarve@item.ntnu.no

Kornschnok Aagesen

Dittawit

OWL-based Node Capability Parameter Configuration

Keywords: Network Management, NETCONF, Capability Configuration

Node capability parameter configuration is the validation and settings of node capability parameter values according to node capability parameter configuration specification (CapSpc). A node capability is a property of a node required as basis for service implementation. This paper presents a Node Capability Parameter Configuration System (CapCon). Node Capability Ontology (CapOnt) is the basis for CapCon. This paper has focus on CapCon in network management. CapSpc specifies required types, parameters, and parameter values for the node capabilities. OWL and OWL/XDD are used to represent the ontology concepts. The NETCONF framework is applied for the network management functionality. A prototype implementation and a case study including experimental results are presented.

Introduction

Network management has been a topic of study for some decades. Some important network management frameworks are SNMP (Simple Network Management Protocol) [START_REF] Subramanian | Network Management -Principles and Practice[END_REF], WBEM (Web-Based Enterprise Management) [START_REF]Web-Based Enterprise Management[END_REF], WS-Management (Web Services Management) [3] and NETCONF (Network Configuration Protocol) [START_REF] Enns | NETCONF Configuration Protocol[END_REF]. In this paper, we apply the SNMP concept MIB as a generic concept for the system of managed objects.

A node capability is generally defined as a property of a node applied as basis for service implementation. Node capability parameter configuration is the validation and settings of node capability parameter values according to a node capability parameter configuration specification (CapSpc). CapSpc specifies required types, parameters, and parameter values for the node capabilities of all nodes in a domain. Existing network management frameworks as mentioned above do not provide functionality for automatic node capability parameter configuration.

This paper presents a Node Capability Parameter Configuration System (CapCon). CapCon identifies which nodes are capable/incapable to meet, or have already met, the requirements of CapSpc. CapCon can set the node capability parameter values on the nodes that can meet the requirements, while generating a report containing node capability types installation instruction for the nodes incapable of satisfying the requirements.

Ontology is a formal and explicit specification of shared concepts [START_REF] Studer | Knowledge Engineering: principles and methods[END_REF][START_REF] Thongtra | Capability Ontology in Adaptable Service System Framework[END_REF]. Node Capability Ontology (CapOnt) enables the definitions of non-rule-based and rulebased concepts. CapOnt is the basis for the definition of CapSpc. Some MIB concepts will be a subset of CapOnt, but represented differently. There is accordingly a need to transform between CapOnt and MIB. CapCon can be integrated with various network management frameworks. In this paper NETCONF protocol with NETCONF agents are applied. NETCONF was designed for managing configuration data. NETCONF, however, does not provide functionality to efficiently manage configuration data for a set of nodes.

The rest of the paper is organized as follows. Section 2 presents an overview of NETCONF. Functionalities and system architecture of CapCon are described in Section 3. Section 4 presents CapOnt, comprising the concepts, the representation and storage of the ontology concepts, as well as the transformation between the CapOnt concepts and YANG-based concepts. Section 5 presents a prototype implementation of CapCon. The CapOnt node capabilities and the NETCONF MIB considered are based on the SNMP IF-MIB [START_REF] Mccloghrie | The Interfaces Group MIB[END_REF]. NETCONF agent is based on the YUMA toolkit [START_REF]YUMA -YANG-based Unified Modular Automation toolkit for the NETCONF protocol[END_REF]. The functionality of YUMA agent was extended to support IF-MIB YANG module [START_REF]IF-MIB YANG module[END_REF] and also to enable registration and de-registration of nodes. Section 6 presents related work and Section 7 gives summary and conclusions.

NETCONF Management Framework

NETCONF management framework follows the manager/agent model. Managed objects, however, are divided into configuration data and state data. Configuration data is writable and is required for transforming a device from its initial default state into the desired state. State data is read-only status information and statistics. In the following short descriptions of NETCONF capability, NETCONF configuration datastore, NETCONF protocol, and YANG are given. NETCONF capability is a set of functionalities that are implemented by both manager and agent. The NETCONF capabilities are declared in <hello> messages sent by each peer during the session initialization. The base NETCONF capability is the minimum set of functionalities each peer must implement. In addition to the base NETCONF capability, there is a set of standardized NETCONF capabilities which the NETCONF agent may support, e.g., :candidate and :notification. The :candidate NETCONF capability indicates that the agent supports the candidate configuration datastore (see below). The :notification NETCONF capability indicates that the agent supports the basic notification delivery mechanisms.

NETCONF configuration datastore is a complete set of configuration data. NETCONF has running, startup, and candidate configuration datastore. Running configuration datastore represents the currently active configuration, while startup configuration datastore is the configuration that will be used during the next startup.

Candidate configuration datastore represents a configuration that may be prepared and later committed to become the new running configuration datastore. Only the running configuration datastore is present in the base NETCONF capability. The other configuration datastores can be defined by additional NETCONF capabilities.

NETCONF protocol provides a simple RPC mechanism to install, manipulate, and delete configuration data. It has four layers: content, operation, RPC, and transport. Content layer represents the managed objects. Operation layer defines operations that can be invoked as RPC methods such as get operation to retrieve the managed object instances and edit-config operation to modify a configuration datastore. RPC layer provides a transport-independent framing mechanism. Several transport protocols can be used, e.g. SOAP, SSL, and BEEP.

NETCONF MIB concepts are represented by YANG [START_REF] Bjorklund | YANG -A Data Modelling Language for the Network Configuration Protocol (NETCONF)[END_REF], but are still partly based on SNMP MIB. YANG-based MIB is structured into modules. Objects in each module are modeled as YANG nodes in a hierarchical tree. YANG nodes are of four types: container, list, leaf and leaf-list. A container node as well as a list node is an internal YANG node that has no value apart from a set of child nodes. A leaf node as well as a leaf-list node has a value but no child nodes. A container node and a leaf node have at most one instance. A list node and a leaf-list node may have multiple instances. YANG modules supported by a NETCONF agent are indicated via the <hello> messages. An MIB compiler called libsmi [START_REF]libsmi -A Library to Access SMI MIB Information[END_REF] has been implemented to translate SMIv2 MIB modules to YANG modules. As an example of a SNMP-based NETCONF MIB, a part of IF-MIB YANG module (NETCONF IF-MIB) translated from SNMP IF-MIB [START_REF] Mccloghrie | The Interfaces Group MIB[END_REF] is presented in Fig. 1. module IF-MIB {namespace "urn:ietf:params:xml:ns:yang:smiv2:IF-MIB"; prefix "if-mib"; container interfaces { leaf ifNumber {type int32; config false; .. } list ifEntry {key "ifIndex"; leaf ifIndex {type if-mib:InterfaceIndex; .. } leaf ifType {type ianaiftype-mib:IANAifType; config false; .. } leaf ifSpeed {type yang:gauge32; config false; .. } leaf ifAdminStatus { type enumeration {enum up {value 1;} enum down {value 2;} enum testing {value 3;}} config true; .. } .. }}} .. }

Functionalities and System Architecture

CapCon architecture as illustrated in Fig. 2 NCA creates INRep. First, NCA creates tables for storing the inherent node capabilities and a table for storing node existence and liveness in INRep. Then, if NCA gets a <register> message from a NETCONF agent, it will record the node's existence. If NCA gets a <hello> message from a NETCONF agent, it will parse the message and identify which YANG modules are supported. NCA will load these YANG modules into its memory and create a mapping file for the transformation between CapOnt and MIB. This mapping file will be sent to NCM and NCD. Also, NCA will send a monitoring request to NCM. If NCA gets a <deregister> message from a NETCONF agent, it will remove the node existence record and send a request to NCM to stop monitoring the node liveness and the inherent node capabilities. In addition, NCA provides the current view of inherent node capabilities in INRep to the other functionality components.

NCM gets monitoring requests from NCA and regularly sends an <rpc> message containing the NETCONF get operation to the agent. Then, if NCM gets an <rpc-reply> message with YANG node instances, it will inform NCA that the node is alive. Also, NCM will use the mapping file to transform the YANG node instances to the inherent node capabilities, and update NCA of such inherent node capabilities. If NCM does not get a <rpc-reply> message for a certain period, it will inform NCA that the node is dead.

NCD regularly identifies which registered nodes are capable/incapable of meeting, or have already met, the requirements of node capability types, parameters and parameter values. A node having the required types, parameters and parameter values have already met the requirements; a node having only the required types and parameters are capable of meeting the requirements. On the other hand, a node that lacks the required types and parameters are incapable of meeting the requirements. NCD sets the node capability parameter values for those nodes that can meet the requirements, while generating a report for further installation of the required node capability types for those previously incapable of satisfying the requirements. NCD operations are based on Equivalent Transformation (ET) [START_REF] Akama | Solving Problems by Equivalent Transformation of Declarative Programs[END_REF]. CapSpc, CapOnt and the inherent node capabilities are inputs. Outputs are one or more of nodes' IP address and the NETCONF edit-config operations with node capability parameter instances and required values. NCD will use the mapping file to transform the node capability parameter instances to YANG node instances, and send the <rpc> messages to the corresponding agents. Each of these messages contains the NETCONF edit-config operation with the YANG node instance.

Node Capability Ontology

This section defines CapOnt concept structure as well as the language representation and storage of these concepts. The projection of MIB concepts into CapOnt as well as the transformation between CapOnt and MIB concepts is also considered.

Upper Node Capability Ontology

The generic structure of CapOnt is illustrated in Fig. 3. This generic concept structure is denoted as Upper Node Capability Ontology. Inference parameters define logical relations to other node capability types. Parameters can be defined by rules. The relations between the node, node capability types and node capability parameters are referred to as: ownership relation between the node and node capability type, constitution relation between two node capability types; and description relation between the node capability-type and parameter. A service management function is an action with constraints and is defined by a rule. For a specific system, specific CapOnt concepts are defined.

MIB Concepts in CapOnt

NETCONF MIB concepts are represented by YANG, but are partly based on SNMP MIB. SNMP MIB objects will in CapOnt be represented as node capability types and non-rule-based parameters. SNMP MIBs are structured in a logical tree. SNMP tables are defined by managed objects on 3 MIB node levels. The top level node is here denoted as a table root node, the second level node as a table access node, and the lowest level nodes as columnar leaf nodes.

To create CapOnt from a SNMP MIB group, we consider three cases: 1) The inner node X is neither a table root node nor a table access node, 2) The leaf node Y is not a columnar leaf node, and 3) The inner node Z is a table root node with a table access node A and columnar leaf nodes {Ci}. For Case 1) the pair of connecting inner nodes Xi and Xj is projected to two node capability types (Xi and Xj) with a constitution relation from Xi to Xj. In Case 1) the pair of inner node X and leaf node Y is projected to a node capability type X, a non-rule-based parameter Y, and a description relation from X to Y. In Case 3) the pair of inner node X and table root node Z with a table access node A and columnar leaf nodes {Ci} is projected to two node capability types (X and A), non-rule-based parameters {Ci}, and there is a constitution relation from X to A, and description relations from A to each Ci.

Representation and Storage of CapOnt

Non-rule-based concepts are expressed by OWL [START_REF]OWL Web Ontology Language Overview[END_REF]. OWL is a standard Web ontology language, which provides a rich set of constructors to define concepts. However, OWL is limited when it comes to describe rule-based concepts. So, rulebased concepts are expressed by OWL/XDD [START_REF] Wuwonse | Towards a language for metadata schemas for interoperability[END_REF]. OWL/XDD extends ordinary XML-based elements by incorporation of variables and rule-based concepts. A rulebased concept in CapOnt is expressed by an OWL/XDD XML clause of the form:

m C C n (1)
where m, n 0, H and B i are XML expressions, and each of C i is a pre-defined XML condition on the clause. H is called the head of the clause while the set of B i and C i is the body of the clause. An XML expression is an XML-based element or document embedding zero or more variables. The upper ontology concepts as well as the CapOnt concepts for the prototype framework described in Sec.5 are given at http://tapas.item.ntnu.no/wiki/index.php/CapOnt. CapSpc is based on CapOnt concepts. CapSpc is expressed by one or more OWL/XDD XML clauses, where XML expressions of these clauses are instances of the CapOnt concepts with variables.

The ontology concepts are stored in NCRep. The inherent node capabilities are instances of the CapOnt non-rule-based concepts. They are stored in a relational database, and are inputs for dynamically setting variables in the CapOnt rule-based concepts with suitable values. NCA is responsible for creating tables in the database. These tables denoted as inherent node capabilities tables are generated from the representation of the CapOnt non-rule-based concepts, using the rules i)-iv) below.

i).

An OWL Class class_x will be mapped to a .*), primitive_datatype will be converted to an SQL primitive datatype and become the Column class_y datatype, if property_i hasValue.

The expression (2), used in the rule ii) -iv), expresses a restriction of an OWL Class class_x on property_i, in which the property's range is restricted to property_range_j.

Class(class_x .* restriction(property_i allValuesFrom(property_range_j)) .*); property_range_j unionOf(set_of_ classes) || primitive_datatype (2)

The node instances and the node capability type instances are stored in the Tables generated from the rule i). The non-rule-based parameter instances are stored in the Columns generated from the rule iii).

Transformation between CapOnt and NETCONF MIB

NCA is responsible for creating a mapping file to be used for the transformation between CapOnt and the corresponding YANG nodes in NETCONF MIB. A capability type, which is constituted by at least another node capability type, is mapped to a YANG container node. A capability type, which is not constituted by others, is mapped to a YANG container node or a YANG list node. A non-rule-based parameter is mapped to a YANG leaf node.

A YANG module defines a tree of YANG nodes. A path defines the YANG node's position relative to the root. NCA assigns a path to all YANG nodes, defined as a sequence of YANG nodes' types and names, separated by slashes, starting from the root to the YANG node assigned the path. NCA finds the corresponding YANG node for each of the node capability types and non-rule-based parameters by matching the ontology concept's name and the YANG node's name. When SNMP MIB managed objects are the basis of CapOnt concepts, there is a one-to-one mapping between these concepts and the YANG nodes. Otherwise, other logics for matching are required. A set of pairs of an OWL Class, expressing a node capability type or a non-rule-based parameter, and a YANG node's path is then generated and stored in the mapping file. With respect to the IF-MIB YANG module example in Fig. 1, an example pair for the parameter ifAdminStatus and the corresponding leaf node ifAdminStatus, locating under the list node ifEntry and the container node interfaces is {<Class rdf:ID="ifAdminStatus">, container interfaces/list ifEntry/leaf ifAdminStatus}.

A Prototype Node Capability Parameter Configuration System

General

The system consists of a load balancer and a cluster of web servers as illustrated in Fig. 4. The load balancer captures the HTTP-based user requests and forwards them to connected web servers on a round robin basis. The number of connected web servers during an interval is dynamic and depends on the total number of user requests during the previous interval. CapCon connects and disconnects web servers to/from the load balancer. Web servers will go into hibernation for energy conservation in case of an inactive time period, i.e., no incoming user requests forwarded from the load balancer or user requests have already been responded.

A prototype is implemented using JAVA programming language. NCA, NCM, and NCD are implemented based on TAPAS platform [START_REF]TAPAS Platform -A support system for deployment, execution and management of service systems defined by the TAPAS architecture concepts[END_REF], which enables NCA, NCM, and NCD to be instantiated and executed in different nodes. NCRep is a physical directory, while INRep is realized by a PostgreSQL database. The NETCONF MIB considered is NETCONF IF-MIB [START_REF]IF-MIB YANG module[END_REF]. NETCONF agent is based on YUMA toolkit [START_REF]YUMA -YANG-based Unified Modular Automation toolkit for the NETCONF protocol[END_REF]. YUMA agent functionalities have been extended to support NETCONF IF-MIB and also to provide registration and de-registration of nodes as explained in Section 3.

Node Capability Ontology Concepts

The node capability types and non-rule-based parameters in CapOnt are projected from the interfaces MIB group in SNMP IF-MIB [START_REF] Mccloghrie | The Interfaces Group MIB[END_REF]. In this MIB group, there is a managed object ifNumber and a table ifTable. ifNumber specifies the number of network interfaces. For ifTable, ifEntry is the conceptual row representing a particular network interface. There are 22 columnar objects of which 18 have Status = current. As examples ifIndex has values unique for each network interface, ifInOctets gives the total number of octets received on the network interface, and ifSpeed defines the maximum bandwidth of the interface in bit/second. The object ifAdminStatus defines the state of the interface which can either be 'up(1)', 'down(2)', or 'testing(3)'.

From the interfaces MIB group, CapOnt has two node capability types and 19 non-rule-based parameters. The node capability types are interfaces and ifEntry. The non-rule-based parameters are ifNumber and all of those 18 mentioned columnar managed objects. These concepts' instances are stored in the inherent node capabilities tables generated by using the rules in Section 4.3. CapOnt has also a rulebased parameter ifInUtilization and two service management functions. ifInUtilization is the inbound bandwidth utilization of a network interface in percentage. The service management functions' actions are setting a network interface's state. In this paper, the actions are specialized as the NETCONF edit-config operation to set the parameter ifAdminStatus value.

The CapOnt non-rule-based concepts in an OWL file as well as the rule-based ifInUtilization parameter and service management functions in OWL/XDD XML clauses are presented at http://tapas.item.ntnu.no/wiki/index.php/CapOnt.

Node Capability Configuration Specification Concepts

CapSpc for the CapCon prototype is expressed in Fig. 5. It is expresses that "A node with a 100Mbps network interface acting as the load balancer is required. Four nodes with two network interfaces acting as the web servers are required. The first network interface of the web server that ifIndex = 1 is required for the connection with CapCon. This network interface's state is always 'up'. The second network interface of the web server that ifIndex = 2 is required for the connection with the load balancer, and its state will be changed dynamically. $S:util_LB is the value of the ifInUtilization of the load balancer during the previous interval, between $S:t_start and $S:t_end second. The total number of user requests during the previous interval can be calculated from: ($S:util_LB*$S:speed)/(100*req_size), where req_size is the user request size in bit, and $S:speed is the maximum bandwidth of the load balancer (100Mbps). N is the appropriate number of web servers connecting with the load balancer during an interval. This means the number of user requests per web server must be between min_req and max_req, where min_req is the estimated minimum concurrent user requests per second that a web server should process, and max_req is the maximum concurrent user requests per second that a web server can process."

Experimental Results

Two sets of experiments (I, II) have been conducted to illustrate the result of automatic parameter values setting. In this case study, the parameter considered is ifAdminStatus. The evaluation is based on the level of energy conservation achieved from the disconnection of web servers. In both experiments, there is a node with a 100Mbps network interface being the load balancer, four nodes with two network interfaces being the web servers. A period of inactivity before hibernate mode of the web servers becomes activated is two minutes. A cost unit determines the amount of energy usage: 1 cost unit during normal mode and 0.3 cost units during hibernation mode. The time interval for the polling of NCM as well as the identification and value settings in NCD is 30 seconds. The controlled variables in the CapSpc in Section 5.3 are set as req_size = 500 bytes, min_req = 500 req/sec, and max_req = 1000 req/sec. In these experiments inbound traffic of the load balancer is controlled, and is generated only from the user requests.

In experiment I, the user requests were randomly generated at the rate between 1000-4000 req/sec. In experiment II, the user requests were generated according to the time of day: 2001-4000 req/sec during 08:00-22:00 and 1000-2000 req/sec during 22:00-08:00. During the execution, the web servers were capable to meet, or had already met, the requirement. Based on the CapSpc, the CapOnt concepts, and the inherent node capabilities from NCA, the node capability parameter configuration function in NCD calculated the ifInUtilization value of the load balancer, and validated if the number of connecting web servers was the same as required. When it was not, this function returned one or more of randomly selected web servers' IP address and the NETCONF edit-config operations to NCD. Each of the operations contains the parameter ifAdminStatus instance and required value ('up'/'down'). NCD sent the <rpc> messages to the corresponding agents, and consequently such web servers were re-connected/disconnected.

The experiments have been carried out with the same total number of user requests for both experiments. The results from both experiments show that three out of four web servers were disconnected and entered hibernating mode. Table 1 shows the number of times each web server was disconnected and hibernated. It also shows that the time percentage that a web server in experiment II enters hibernation after getting disconnected is more than its counterpart in experiment I, since the user requests rate in experiment II is more certain. We can indicate that the usage of CapCon for the "time-based" user request rate results in higher energy conservation. [START_REF] Cui | The Design of the Network Configuration Management based on NETCONF protocol[END_REF][START_REF] Liu | Implementation of the management of SNMP/NETCONF network devices for the next generation NMS[END_REF][START_REF] Nataf | End-to-end YANG-based Configuration Management[END_REF][START_REF] Elbadawi | High Level Abstraction Modeling for Network Configuration Validation[END_REF]. The work in [START_REF] Cui | The Design of the Network Configuration Management based on NETCONF protocol[END_REF][START_REF] Liu | Implementation of the management of SNMP/NETCONF network devices for the next generation NMS[END_REF] focuses on the system architecture aspect, [START_REF] Nataf | End-to-end YANG-based Configuration Management[END_REF] mainly considers the NETCONF MIB represented by YANG, and both aspects are discussed in [START_REF] Elbadawi | High Level Abstraction Modeling for Network Configuration Validation[END_REF]. Cui et al. [START_REF] Cui | The Design of the Network Configuration Management based on NETCONF protocol[END_REF] present a detailed design of NETCONF manager and agent. A proxy configuration file is used to specify the agents in the entire managed devices. In CapCon, the NETCONF agents are able to register nodes and the node capabilities without the need of configuration file. Liu et al. [START_REF] Liu | Implementation of the management of SNMP/NETCONF network devices for the next generation NMS[END_REF] improve traditional network management system by adding a simple judging function to dynamically decide whether the NETCONF protocol is supported on the managed devices. If the NETCONF protocol is supported, NETCONF operations are used. Otherwise, SNMP operations are used. Nataf and Festor [START_REF] Nataf | End-to-end YANG-based Configuration Management[END_REF] integrate the NETCONF MIB represented by YANG into the NETCONF agent from the ENSUITE open source framework, and implement a browser to retrieve and edit the configuration data. Elbadawi and Yu [START_REF] Elbadawi | High Level Abstraction Modeling for Network Configuration Validation[END_REF] present the design and implementation of a configuration validation system using Erlang programming language. Comparing with CapCon, the system provides the validation without the parameter value settings.

Conclusions

Node Capability Parameter Configuration System (CapCon) which enables automatic node capability parameter configuration is presented. Two aspects including centralized architecture and Node Capability Ontology (CapOnt) are discussed in detail. The CapOnt concept representations and the transformation between CapOnt and SNMP-based NETCONF MIB are presented. In the case study, the prototype web-based application integrated with CapCon has been implemented. The automatic parameter value setting by CapCon dynamically adapts the number of active web servers.

CapCon provides flexibility in terms of the applied frameworks. The CapOnt concepts as well as the CapSpc concepts can be added, modified and removed during the system runtime. CapCon also enables automatic discovery of nodes and their node capabilities. In this paper, CapCon is integrated with NETCONF. The flexible nature of the system enables integration with various network management frameworks. However, the future work can be focused on developing a decentralized architecture of CapCon.

Fig. 1 .

 1 Fig. 1. A part of IF-MIB YANG module.

  has three functionality components, two repositories and NETCONF agents. The functionality components are Node Capability Administrator (NCA), Node Capability Monitor (NCM) and Node Capability Parameter Modifier (NCD). NCA is concerned with the registration and deregistration of nodes and their node capabilities. NCM monitors node liveness and node capability-types, parameters, and parameter values. NCD is responsible for the validation and settings of node capability parameter values according to CapSpc. The repositories are Node Capability Type Repository (NCRep) and Inherent Node Capability Repository (INRep). NCRep stores the ontology concepts. INRep stores the existence and liveness of nodes as well as inherent node capabilities. Inherent node capabilities are observed node capability instances. The NETCONF agent registers and de-registers with NCA using <register> and <deregister> messages. Both messages contain the node IP address.

Fig. 2 .

 2 Fig. 2. CapCon Architecture.

Fig. 3 .

 3 Fig. 3. Upper Node Capability Ontology.

Fig. 4 .

 4 Fig. 4. A web-based application example.

Fig. 5 .

 5 Fig. 5. OWL/XDD XML Clause for CapSpc.

  Table class_x, if it has either one of the properties: hasNodeCapability, constitutedBy, or describedBy. The Table class_x is assigned an auto-numbered Primary key named ID and a TIMESTAMP Column named MonitoredAt for recording the row-creation/update time. The Table "Node" is also assigned a Column IPAddress. Foreign key class_x_ID will be generated in Table class_y referring to the Primary key in Table class_x, if property_i hasNodeCapability || constitutedBy. iii). For Class(class_x .* restriction(property_i allValuesFrom(unionOf( set_of_classes))) .*); class_y set_of_classes, Column class_y will be generated in Table class_x, if property_i describedBy. iv). For Class(class_y .* restriction(property_i allValuesFrom(primitive_datatype))

	ii). For Class(class_x .* restriction(property_i allValuesFrom(unionOf(
	set_of_classes))) .*); class_y	set_of_classes,

Table 1 .

 1 Experimental results. Two aspects regarding system architecture and information model are considered in this paper. Most of the recent works related to NETCONF-based configuration management systems, however, focus only on one of these aspects. Some examples are found in

	Experiment I	Experiment II


Cristina Cano
email: cristina.cano@upf.edu

Boris Bellalta
email: boris.bellalta@upf.edu

Miquel Oliver
email: miquel.oliver@upf.edu

Receiver-Initiated vs. Short-Preamble Burst MAC Approaches for Multi-channel Wireless Sensor Networks

Keywords: WSNs, Multi-Channel, MAC, SA-MAC, Receiver-Initiated

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

Introduction

Wireless Sensor Networks (WSNs) are formed by small and low-capability devices that are able to sense environmental metrics and to communicate them wirelessly to a central unit, known as a sink. The deployment of dense WSNs in large, remote and difficult-to-access areas requires keeping the size and cost of sensor nodes as low as possible. This implies that the energy, computational and memory resources of the sensor nodes are usually limited. Among the different constraints, the limitation of the energy resources is the most important one as it directly affects the network lifetime. Therefore, the design of the Medium Access Control (MAC) layer is of crucial importance because it controls the most energy consuming component of a sensor node: the transceiver. By putting the transceiver in duty cycle mode, i.e., sleeping and periodically waking up, the energy consumption can be reduced. However, a mechanism is needed to coordinate a receiver and a transmitter so as to be awake at the same instant, also known as rendezvous. Among the different techniques to ensure a rendezvous, asynchronous MAC protocols and particularly preamble sampling techniques [START_REF] Buettner | X-MAC: A Short Preamble MAC Protocol for Duty-cycled Wireless Sensor Networks[END_REF] provide extremely low energy consumption at low loads (the common situation in WSNs), have a low complexity and a lack of synchronization requirements.

Sensor nodes are normally configured to transmit at very low power [4]. This allows them to consume smaller amounts of energy while transmitting but, on the other hand, this configuration also makes them suffer from external interferences in a notable manner. It is expected that the current level of deployment of different wireless networks will make the Industrial, Scientific and Medical (ISM) band crowded in the near future [START_REF] Zhou | Crowded Spectrum in Wireless Sensor Networks[END_REF]. Therefore, it will be necessary for a sensor device to be able to select the best portion of the spectrum to communicate with its neighbours, thus increasing the probability of a correct reception, reducing the delay and maintaining a low energy consumption per successfully sent packet. When there are multiple channels available, the rendezvous problem becomes more complicated. In that case, apart from coordinating the nodes to be awake at the same time, they also need to agree on the channel to use.

In this work, the adaptations to multi-channel operation of two well-known MAC approaches for rendezvous are evaluated and the best working conditions for each approach are obtained. These first results can be useful for the further study and design of these protocols when multiple channels are available and sensor nodes select one in which to transmit or listen for data.

This article is organized as follows. In Section 2 the existing asynchronous protocols for multi-channel operation are described. Then, in Section 3 the multichannel techniques evaluated in this article are presented. After that, an analytical derivation of these mechanisms is explained in Section 4. The description of the results obtained is presented in Section 5. Finally, some conclusions and future research directions are outlined.

Related Work

In common energy-constrained WSNs, the sensor nodes are sleeping and waking up according to their duty cycle. Therefore, a mechanism is needed to coordinate a receiver and a transmitter to communicate, since both have to be awake at the same instant. Techniques to achieve this rendezvous can be divided into three different categories: TDMA-like approaches, protocols with common active periods and asynchronous approaches [START_REF] Cano | Low energy operation in wsns: A survey of preamble sampling mac protocols[END_REF]. Among these, asynchronous MAC protocols and particularly preamble sampling techniques consume extremely low energy when the network load is low, have a low complexity and no synchronization requirements.

Using preamble sampling, sensor nodes sample the channel periodically to detect activity and they remain awake if activity is detected. Thus, if a sensor node has something to transmit, it sends a long preamble before the data in order to wake up the receiver [START_REF] Polastre | Versatile Low Power Media Access for Wireless Sensor Networks[END_REF]. There are several extensions of this technique, one of the best known is the division of the long preamble into a short-preamble burst [START_REF] Buettner | X-MAC: A Short Preamble MAC Protocol for Duty-cycled Wireless Sensor Networks[END_REF]. By dividing the long preamble into short packets, some useful information can be included, like, for instance, the time at which the data transmission will start, allowing the receiver to go to sleep. Receiver-initiated approaches [START_REF] Sun | RI-MAC: A Receiver-initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks[END_REF] follow a similar idea to the one used in preamble sampling. However, in this case, when a sensor node wants to transmit something, it wakes up and listens to the channel. Sensor nodes wake up periodically and send a beacon message indicating they are awake. After receiving the beacon message, the sender can start the transmission.

When there are multiple channels to use, the rendezvous problem becomes more challenging. In that case, apart from coordinating the nodes to be awake at the same time, they also need to agree on the channel to use. In this work, the attention has been placed on asynchronous approaches since, as previously stated, they provide features that are especially beneficial to WSNs.

OMA [START_REF] Li | Oma: a multi-channel mac protocol with opportunistic media access in wireless sensor networks[END_REF] and ARM [START_REF] Li | Arm: an asynchronous receiver-initiated multi-channel mac protocol with duty cycling for wsns[END_REF] protocols are two asynchronous MAC protocols for multi-channel operation. While OMA is based on the transmission of a burst of short preambles, ARM is based on the receiver-initiated approach. In these protocols, the rendezvous is made in a common and fixed control channel, then the data transmission is done in the channel both receiver and transmitter agree to use.

In contrast, SA-MAC [START_REF] Ansari | Spectrum agile medium access control protocol for wireless sensor networks[END_REF], that is based on the transmission of a burst of short preambles, does not use a common control channel to perform the rendezvous. When a node wakes up it samples all channels trying to find a short preamble of the receiver. The short-preamble burst should take into account, apart from the sleep time of the sensor nodes, the time to sample all the available channels. Not using a common control channel makes the protocol more robust against interference problems at the cost of a higher overhead.

Similarly, the EM-MAC [START_REF] Tang | Em-mac: A dynamic multichannel energy-efficient mac protocol for wireless sensor networks[END_REF] protocol ensures the rendezvous between receiver and transmitter in an asynchronous manner and without the use of a common control channel. The difference is that this protocol is based on the receiverinitiated technique adapted to multi-channel operation and combined with a prediction of the channel and wake-up time of the receiver based on pseudorandom numbers. This mechanism allows the transmitter to wake up right before the receiver beacon in the selected channel. As a drawback, each node must store information of each neighbour and extra overhead has to be included in messages to perform the prediction.

In this work, the receiver-initiated technique presented in [START_REF] Sun | RI-MAC: A Receiver-initiated Asynchronous Duty Cycle MAC Protocol for Dynamic Traffic Loads in Wireless Sensor Networks[END_REF] is adapted to multi-channel operation by making the transmitter sample all channels to find a burst of beacons of the receiver. On the other side, the transmitter-initiated technique defined in the SA-MAC protocol is adopted. The comparison of both techniques gives insights into the best working conditions for both approaches when multiple channels are available.

Multi-Channel Receiver and Transmitter-Initiated MACs

In SA-MAC [START_REF] Ansari | Spectrum agile medium access control protocol for wireless sensor networks[END_REF], the rendezvous based on the transmission of a short-preamble burst along with the periodic channel sampling of the receiver (similar to the single-channel technique defined in [START_REF] Buettner | X-MAC: A Short Preamble MAC Protocol for Duty-cycled Wireless Sensor Networks[END_REF]) is adapted to multi-channel operation. An example of the basic functionality of this protocol with 4 channels is shown in Fig. 1. It can be observed that, when a node wants to transmit a message it starts transmitting a burst of short preambles in the selected channel and after that, it sends the data. The receiver, on the contrary, wakes up periodically and samples all channels. If the receiver detects activity in one channel, it remains awake to receive a complete short preamble, which includes the time at which the data transmission will start. This allows the receiver to go to sleep and wake up right before the transmission of the data message. Observe that the rendezvous would also be possible by making the sender switch among channels and sending a short preamble on each. The receiver could then stay listening in one channel until the short preamble is received. The transmitter can either wait in each channel for an early-ACK [START_REF] Buettner | X-MAC: A Short Preamble MAC Protocol for Duty-cycled Wireless Sensor Networks[END_REF] or announce in each preamble the channel in which the message will be sent. Both approaches require more energy waste and delay if compared to SA-MAC. The first case requires the transmitter to listen on each channel and the second one requires extra channel switches.

Based on the fact that modern radios (like the CC2420 transceiver [4]) consume less energy in transmitting than in receiving mode, the adaptation of receiver-initiated approaches to multi-channel operation seems to be a good option, especially when the network load is low (as it typically occurs in usual WSN applications). The functionality of the receiver-initiated protocol studied in this work is shown in Fig. 2 for the case in which again 4 channels are available. Each node wakes up periodically and sends a burst (equal to the number of channels) of beacons to notify potential transmitters it is awake and ready to receive data. As previously discussed, this behaviour is expected to consume less energy than waking up to sample all channels in the cases in which the energy to receive is higher than the energy required to transmit. Then, when a node wants to transmit a packet, it sequentially and periodically scans all channels to find a beacon of the intended receiver. After the reception of a complete beacon, the transmitter goes to sleep and wakes up after the beacon burst to send the data message (assuming the network load to be low, no back-off has been considered).

Observe that the transmitter should sample the channels during the sleep time plus twice the beacon burst duration to ensure the rendezvous. Observe also that the rendezvous could alternatively be done in this case by having the receiver switching among channels with the transmitter waiting for the reception of a beacon in a given channel. In this design, the receiver should either stay awake in every channel after the transmission of the beacon waiting for data or announce the channel in which it will be listening for data. Again, these alternatives consume more energy or entail more delay than the one previously described.

Analytical Derivation of Energy Consumption

To analyze and compare the performance of both techniques with multi-channel operation we conduct an analysis of the energy consumption. The energy consumed by each sensor during a time T has been calculated. Assuming that each node generates packets at an average rate of λ packets/s, the number of generated messages during T is N = λ • T . Then, the goal is to find the total energy spent (e) as the sum of the energy required to transmit these messages (e tx ), the energy spent receiving messages from other nodes (e rx ) and the energy wasted during the duty cycle (e dc ), i.e., sleeping and periodically waking up to either sample all channels or to send the burst of beacons: e = e tx + e rx + e dc .

The analytical model presented in this work considers the following assumptions:

1. It is assumed that, as occurs on common platforms like the MicaZ [4] nodes, each node is equipped with only one radio that can be tuned to work in different channels, one at a time.

2. The traffic load within the WSN is low enough to consider the collision probability negligible. This is a common assumption in WSN analytical models and is also used in [START_REF] Ansari | Spectrum agile medium access control protocol for wireless sensor networks[END_REF]. 3. A node sends and receives the same amount of messages and it is assumed that there is no overhearing, i.e., nodes only receive the packets addressed to them. 4. Ideal or random (as done in [START_REF] Li | Oma: a multi-channel mac protocol with opportunistic media access in wireless sensor networks[END_REF] and [START_REF] Li | Arm: an asynchronous receiver-initiated multi-channel mac protocol with duty cycling for wsns[END_REF]) channel selection is assumed. Since the purpose is to evaluate the behaviour of the rendezvous mechanisms, the channel selection strategy does not affect the comparison.

Short-Preamble Burst Approach

Let t speriod be the sampling period of a sensor node, i.e., the time between two channel samples, and t s the time required to sample one channel. Therefore, the sleep time (t sleep ) can be computed as shown in Eq. 1, where n ch is the number of available channels.

t sleep = t speriod -(n ch • t s ) (1)
Then, the time to transmit a message (Eq. 2) can be calculated as the sum of the time to transmit the short-preamble burst (it has to be transmitted during the t speriod to ensure a correct rendezvous), the time to transmit the data (t data ) packet and the time to receive the ACK (t ack ).

T tx = t speriod + t data + t ack (2)
The energy consumption spent to transmit a message can be obtained by multiplying the time spent in each mode by the power drawn in the specific mode (P i , where i can be transmit, receive or sleep mode) as shown in Eq. 3.

E tx = P tx • (t speriod + t data ) + P rx • t ack (3)
The total time and energy consumption to transmit all messages generated during a time T is:

t tx = N • T tx and e tx = N • E tx .
Similarly, we can compute the time (Eq. 4) and energy spent to receive a message (Eq. 5) assuming that each node will receive the same amount of messages than it generates. In this case, it has to be considered that the receiver will find the transmitter on average in (n ch • t s )/2 and that it will only receive on average 1.5 short preamble messages [START_REF] Ansari | Spectrum agile medium access control protocol for wireless sensor networks[END_REF] of duration t short-p .

T rx = (n ch • t s ) 2 + (1.5 • t short-p ) + t data + t ack (4)
E rx = P rx • (n ch • t s ) 2 + (1.5 • t short-p ) + t data + (P tx • t ack ) (5)
The total time receiving and the total energy spent to receive N messages is also:

t rx = N • T rx and e rx = N • E rx , respectively.
The rest of the time (t dc = Tt txt rx ), a node will be in duty cycle, waking up to sample all channels and sleeping. The energy spent in this operation is shown in Eq. 6.

e dc = t dc • (P rx • (n ch • t s )) + (P sleep • t sleep ) (n ch • t s ) + t sleep (6)

Receiver-Initiated Approach

In the receiver-initiated approach, the sleep time can be defined in a similar way. However, it has to be considered that each node sends a total of n ch beacons each time it wakes up:

t sleep = t speriod -(n ch • t beacon ) (7)
To compute the time and energy required to transmit a message, it has been assumed that a transmitter samples the channels during (t sleep + (2 • n ch • t beacon ))/2 s, on average, to find a receiver and that it will receive, also on average, 1.5 beacons. The expression to compute that time is described in Eq. 8 and the corresponding energy consumption is shown in Eq. 9.

T tx = t sleep + (2 • n ch • t beacon ) 2 + (1.5 • t beacon ) + t data + t ack (8)
E tx = P rx • t sleep + (2 • n ch • t beacon ) 2 + (1.5 • t beacon ) + (P tx • t data ) + (P rx • t ack ) (9)
The time and energy to receive a message is computed considering that a node sends n ch beacons, receives the data and sends the ACK as shown in Eq. 10 and Eq. 11 respectively.

T rx = (n ch • t beacon ) + t data + t ack (10)
E rx = (P tx • n ch • t beacon ) + (P rx • t data ) + (P tx • t ack ) (11)
The energy spent in duty cycle has to take into account that when a node wakes up it sends n ch beacons (Eq. 12):

e dc = t dc • (P tx • (n ch • t beacon )) + (P sleep • t sleep ) (n ch • t beacon ) + t sleep (12)

Numerical Evaluation

Using the analytical models described in Section 4, we now conduct a numerical evaluation. Results varying the packet transmission rate with n ch set to 5, 10, 15 and 20 are shown in Fig. 3. The default parameters used for the evaluation were measured on the TelosB platform by Ansari et al. in [START_REF] Ansari | Spectrum agile medium access control protocol for wireless sensor networks[END_REF] and are shown in Table 1.

In Fig. 3, it can be observed that when the traffic of the network is low, the receiver-initiated approach consumes less energy than the short-preamble burst technique, independently of the t speriod and the number of channels. In the short-preamble burst approach each node periodically wakes up to sample the channel during n ch • t s . In contrast, in the receiver-initiated approach each node periodically sends beacons during n ch • t beacon . Given that t s has been considered equal to t beacon and that it has been assumed that the energy to receive is higher than the energy required to transmit, the energy consumption for the receiver-initiated technique at low loads will always be lower than the one spent in the short-preamble burst case, independently of the number of available channels. However, as the number of channels increases, the difference is more notable.

On the other hand, note that for higher network loads the receiver-initiated approach also consumes less energy than the short-preamble burst approach in most of the cases evaluated. The difference is especially notable when the number of channels is small and t sleep is long. This difference becomes smaller when the number of channels increases and t sleep is reduced. The short-preamble burst can even show a slightly lower energy consumption than the receiver-initiated approach as depicted in Fig. 3(d). For each message to transmit, the short-preamble burst technique sends a burst of preambles during t sleep + (n ch • t short-p ), independently of when the rendezvous occurs. In contrast, in the receiver-initiated approach, the transmitter stops listening the channels when it receives a beacon. This happens on average in a period of (t sleep + (2 • n ch • t beacon ))/2. Therefore, when both the number of channels increases and t sleep is reduced, the energy consumption of the short-preamble burst mechanism can become smaller than the consumption of the receiver-initiated approach. The capability of coordinating low-capable sensor nodes working at different frequency bands is still a research challenge. In this case, multi-channel communication has been considered. However, it will provide higher benefits and also higher challenges to select variable portions of the spectrum in which to transmit based on the conditions observed. Sensor nodes will, in this scenario, have to coordinate themselves to aggree on the portion of the spectrum to use.

In this work, the receiver-initiated rendezvous approach has been adapted to work with multiple channels and compared to the multi-channel approach based on the transmission of a short-preamble burst. Results have shown that the energy consumed by the receiver-initiated approach is smaller than the energy spent by the short-preamble burst technique in scenarios with low traffic load and also in cases with high traffic load, reduced number of channels and high sleep time.

This work aims to provide the first comparison of both techniques for multichannel operation. However, a complete evaluation in multi-hop and large scenarios is required and has been left as a future work. Moreover, new approaches need to be defined in order to reduce the unnecessary energy spent to ensure the rendezvous in a multi-channel WSNs without the use of a common control channel.

Fig. 1 .

 1 Fig.1. Example of the short-preamble burst approach functionality with 4 channels

Fig. 2 .

 2 Fig. 2. Example of the receiver-initiated approach functionality with 4 channels

Fig. 3 .

 3 Fig. 3. Energy Consumption with different number of channels and traffic loads

Table 1 .

 1 Evaluation Parameters

	Parameter	Value Parameter Value
	t data	3.2 ms	t ack	0.32 ms
	t beacon = t short-p 15.8 ms	ts	15.8 ms
	Time (T )	1000 s	Ptx	46.5 mW
	Prx	58.9 mW	P sleep	3.6 mW

Acknowledgments. This work has been partially supported by the Spanish Government under projects TEC2008-06055 (Plan Nacional I+D) and CSD2008-00010 (Consolider-Ingenio Program), and by the Catalan Government (SGR2009 #00617).


Ivett Kulik
email: kulik@tmit.bme.hu

Tuan Anh Trinh
email: trinh@tmit.bme.hu

Investigation of Quality of Experience for 3D Video in Wireless Network Environment

Keywords: Quality of Experience (QoE), Quality of Service (QoS), Gigabit Passive Optical Network (GPON), WiFi network, 3D stereoscopic video, subjective test, IBM SPSS

Multimedia streams have increased dramatically over the wireless networks during the last few years. 3D video stream-based applications and movies will become significant contents of wireless network traffic in future Internet. This paper shows Quality of Experience (QoE) results based on transport network's Quality of Service (QoS) level degradation obtained from subjective tests which were carried out for 3D stereoscopic video files transporting through GPON-based transport network combined with IEEE802.11n standard based WiFi sub-networks on clients' side. Gathered information show that QoE level is influenced with more factors like: bandwidth limitation or channel interference in WiFi network and QoS parameters' values of transport network as well. In case of 3D contents quality of film shooting, size and resolution value of using display also take effect on perceived visual quality. Evaluation results were processed statistically IBM SPSS Statistics software-package.

Introduction

Widespread deploying of wireless local area networks (WLAN) brings on facilitation for customers. They can connect more easily to the Internet and the number of Internet users has increased rapidly. WLAN based on IEEE 802.11 standards with infrastructure mode is the most popular as we can recognize hot spots everywhere. Popularity of multimedia contents -especially 3D based video-games or movieshas raised the necessity of this technology progress. Today the IEEE 802.11n standard based communication support advanced multimedia applications but nature of wireless technology (like bandwidth limitation or channel interference) still brings to challenging issues for Internet Service Providers (ISPs). Customers' satisfaction needs more than only QoS support on the part of service providers, enhanced level of vision quality is also very important which is called Quality of Experience (QoE).

More research subjects had brought into focus the QoE and QoS [START_REF] Casas | End-2-End Evaluation of IP Multimedia Services, a User Perceived Quality of Service Approach" 18-th ITC Specialist Seminar of Quality of Experience[END_REF], [START_REF] Fiedler | A Generic Quantitative Relationship between Quality of Experience and Quality of Service[END_REF] or evaluation of 3D stereoscopic images and films [START_REF] Häkkinen | Measuring Stereoscopic Image Quality Experience with Interpretation Based Quality Methodology[END_REF], [START_REF] Shibata | Evaluation of stereoscopic image quality for mobile devices using Interpretation Based Quality methodology[END_REF], [START_REF] Xing | Estimating Quality of Experience on Stereoscopic Images[END_REF] but nobody had published specific results of subjective tests carried out by bigger number of participants (30 -50 testing persons) focusing to relationship between QoE and QoS in case of 3D stereoscopic videos. We made first evaluation of QoE for 3D stereoscopic video files based on QoS through the GPON-based transport network with 50 participants, which results were published in paper [START_REF] Kulik | Investigation of Quality of Experience for 3D Streams in GPON[END_REF]. Our research results showed that in the investigated scenarios GPON is suitable for efficient transport of 3D contents. QoE results of 3D stereoscopic videos' watching showed dependency on the transport network caused QoS degradations but more research was needed for observing and improving quality of user experience in case of multimedia contents delivery. Therefore we carried out further subjective tests with 40 participants through GPON-based transport network but with more features investigation and more specific results were obtained. Finally we collected information from people (36 participants) in GPON environment combined with WiFi network on the clients' side with reason to explore QoE-QoS relationship is this case. The latter scenario is discussed in this paper. Evaluation results have been analyzed by IBM Statistical Package for Social Scientists (SPSS).

The paper is structured as follows. Section 2 shortly describes methods of quality comparisons and some statistics analysis definitions. Section 3 shortly shows used topology of laboratory network. Section 4 presents description of experiment and evaluated results of measurements through the GPON transport network combined with WiFi network. Finally we conclude the paper in Section 5.

2

Methods of Quality Comparisons

When a stereoscopic film is viewed the resulting experienced is formed by many factors. Some factors related to stereoscopic materials, cognitive-emotional factors related to the viewer, the viewer's visual limitations and the viewing content. The technology that is used to watch the materials and the display's size and resolution has also significant impact on the viewer's experience. Values of transport network's QoS parameters like delay, jitter, packet loss and throughput could have also important effect to the visual quality results and multimedia attributes like coding, bit-rate, frame-rate and motion level of scenes influence results as well [START_REF] Fiedler | A Generic Quantitative Relationship between Quality of Experience and Quality of Service[END_REF]. This means that the investigation of QoE besides the importance is a complicated process and the correct evaluation of gathered information is also a challenge.

The derivation of QoE-QoS relationships builds on quality comparisons between:  The reference -which is the undistorted video stream  The outcomewhich is the potentially distorted video stream due to the QoS degradation

References play an important role when it comes to rating the quality of outcome. There are two basic measurement options: subjective tests and objective tests [START_REF] Fiedler | A Generic Quantitative Relationship between Quality of Experience and Quality of Service[END_REF].

Subjective tests are carried out by real users and this type of test is time consuming because a large number of people have to participate on it for statistically relevant results. Objective tests are carried out by an algorithm following psychophysical and engineering approaches without human presence.

QoE-QoS relationship can be investigated based on full reference metricswhich allow detailed subjective and objective comparisons of multimedia contents because both reference and outcome are available or based on no reference metricswhich is an online situation where no reference is available and quality results can be extracted only from the outcomes finally based on reduced reference metricswhich is not so detailed comparison than the case of full reference metrics but here the same set of parameters are derived and compared for the reference and outcome as well [START_REF] Fiedler | A Generic Quantitative Relationship between Quality of Experience and Quality of Service[END_REF].

Multimedia sequences (undistorted and distorted contents as well) can be scored by the Mean Opinion Score (MOS) in case of subjective evaluation, which is the core of our experiment. The MOS quality scale method used to be applied for voice and video traffic scale. Scores are: 5excellent, 4good, 3regular, 2bad, 1awful.

Statistics analysis

Collected data were analyzed by the IBM SPSS Statistics software-package for business, government, research and academic organizations. SPSS is an abbreviation for Statistical Package for Social Scientists but the other name: Statistical Product and Service Solutions are also well-known. This software offers statistical procedures to make reliable analysis, to get a quick look at our data, formulate hypotheses for additional testing, and then carry out a number of procedures to help clarify relationships between variables, create clusters, identify trends and make predictions. The goal of analysis is to make correct judgments and decisions in the presence of uncertainty and variation and to detect relations between data [START_REF] Milton | Probability and Statistics in the Engineering and Computing Sciences[END_REF]. Statistics methodology is founded on the probability study. A study is an experiment if the investigator observes how a response variable behaves when one or more explanatory variables, also called factors, are manipulated. In our experiments QoE was the response variable scored by the MOS and QoS parameters like jitter degradation and bandwidth limitation were explanatory variables.

The method of least squares where also used, which is a standard approach to the approximate solution for sets of equations in which there are more equations than unknowns. "Least squares" means that the overall solution minimizes the sum of the squares of the errors made in solving every equation.

A confidence interval is a particular kind of interval estimate of a population parameter and is used to indicate the reliability of an estimate. It is an observed interval that frequently includes the parameter of interest, if the experiment is repeated. How frequently the observed interval contains the parameter is determined by the confidence level or confidence coefficient [START_REF] Milton | Probability and Statistics in the Engineering and Computing Sciences[END_REF].

Topology of laboratory network

Experiments were carried out in laboratory environment where the same GPONbased transport network was used as core of the network topology which is described in the paper [START_REF] Kulik | Investigation of Quality of Experience for 3D Streams in GPON[END_REF]. This topology was increased with two WiFi sub-networks where WiFi Access Points (AP) were connected directly to ONTs (Optical Network Terminal) and two clients' PCs received 3D stereoscopic video files through WiFi network cards. The topology is shown in Figure 1. Video contents had to be transfer through the transport network only in unicast mode instead of multicast mode because the VLC media player v2.0 could not play 3D stereoscopic content and Nvidia Vision Player v1.6 (NVP) could play correctly 3D stereoscopic video files but only streams transported only in unicast mode and based on TCP transport protocol.

Description of experiment

The common practice to estimate user perception is to conduct large experiments in a controlled environment. Based on first and second experiences we prepared new investigation with goal to show relationship between QoE and QoS in laboratory environment extended with WiFi sub-network.

Participants had to evaluate some important points based on MOS like: 1) video continuity, 2) quality of picture, 3) 3D visual quality, 4) conformity between picture and voice and 5) QoE on the whole. The last point is more complicated than only recapitulation of first ones. We also asked people to weight their answer for statistics analysis because we could calculate the weighted average values of QoE based on gathered weighted scores.

Evaluated results

36 participants attended this experiment (34 men and 2 women) who study at the Budapest University of Technology and Economics. 18 were spectacled from them and their mean age was 22.14. 32 participants have watched 3D movies. They watched a short part of 3D version of Avatar trailer which general features are shown in Table 1.

Table 1 Features of the investigated 3D stereoscopic video

At first participants watched 3D stereoscopic video without any added disturbance. Despite of using IEEE802.11n standard in the 2.4GHz band video playing on 2 PCs in same time was not always fluent with standard quality which was caused by two major circumstances. At first many WiFi networks were accessible in the department laboratory where our experiment was carried out and other WiFi networks used same channels for carrying which is shown in Figure 2 Other subjective tests with distorted 3D video contents were carried out on these two PCs in same time and each of them was connected to different AP in the way mentioned above. We can say even based on reference tests that 3D content delivery though the WiFi network is more sensitive and less effective comparing results with first or second investigation results where we could carry out measurements on 4 PCs with mean value of QoE 4.355 (better than good) calculated based on weighted scores. Participants perceived quality of 3D presentation also by quality of stereo shooting like depth of scenes.

For this reason we did not disturb 3D video transport by jitter increase or jitter increase combined with bandwidth limitation but only with bandwidth limitation. We counted weighted averages by formula (3) based on gathered scores and weights. Formula of weighted average:

Weighted average =   5 1 _ _ * i i i

Weights of Sum

Value Weight [START_REF] Cale | Gigabit Passive Network -GPON[END_REF] Where: i -sequential number of the appropriate question point Sum_of_Weightssum of weights for 3D video Based on weighted average values we could assign one QoE value to every appropriate value of bandwidth limitation. Summary of results are shown in Table 3. Bandwidth limitation values were calculated based on the average demand bandwidth value of 3D content which was during the 95% of playing time around 4MB/s except in case of the highest motion level scenes when spine values appeared exceeded this 4MB/s bandwidth value. Therefore bandwidth was set to 5, 4.5, 4.0, 3.75 and 3.5 MB/s which means 0, 0.5, 1, 1.25, 1,5MB/s limitation values on Figure 3.

Figure 3 shows relationship between QoE degradation and bandwidth limitation's difference increasing by using interpolation lines for 2PCs together (using 3.channel and 13.channel) and for each PC separately.

    x x x ( 6
)
This means that QoE-QoS relationship for 3D stereoscopic video watching shows cubic correlation for channel 3 and channel 13. as well. The threshold value of QoS parameter was in case bandwidth 4MB/s which means 1MB/s bandwidth limitation value on Figure 3.

We can recognize from Figure 3 that 3D film delivering through 13.channel gives better quality results than communication through 3.channel which was used with more different WiFi networks in same time -shown in Table 2. The middle line shows combined results of these two channels information when started mean weighted QoE was only 3.2167 (regular). This was caused by the highest motion level scenes when the data sequences stuck shown in Figure 4 but these critical situations soon were persisted. QoE sensibility to bandwidth limitation was conspicuous and from the different value from 1MB/s rapid deterioration turned up and participants became dissatisfied. This means that bigger limitation than 5% of demand bandwidth value is not recommended for 3D stereoscopic contents if we want approach excellent or good MOS score of QoE.

Figure 5 Confidence intervals of QoE values

Based on Figure 3 and Figure 5 we can conclude that less QoS deterioration cases worse QoE in case of WiFi network using and to supply sufficient throughput is an important characteristic point to satisfy customers' demand. The buffered playing time increase also could help to raise resistivity against QoS degradation [START_REF] Rugel | A Network-based method for measuring of internet video streaming quality[END_REF] but we did not change this value.

Conclusion

In this paper we presented results of subjective test method of QoE investigation of 3D stereoscopic video files based on transport network QoS level degradations. In combined network environment GPON-based transport network + WiFi network based on IEEE 802.11n in the 2.4GHz band at the client's side the QoE is more sensitive than in case of network topology without WiFi sub-network. Video contents were transported in unicast mode based on TCP protocol and were played on two PCs in the same time. The relationship between QoE and QoS was shown based on gathered data for 3D stereoscopic multimedia content but the good quality guarantee is more complex in case of WiFi network. QoE is influenced by nature of wireless technology (like bandwidth limitation or channel interferences) and by QoS level in transport network as well.

Gathered data show that people who had watched 3D movie before this experiment (32 from 36 participants) were more critical to any quality differences. Evaluation of data was carried out by IBM SPSS Statistics software. Statistic outputs clearly show close coherence between QoE and QoS changing and robustness of 3D contents and limitation of WiFi networks together cause stronger QoE degradation on the client's side. We can emphasize that for good QoE of 3D stereoscopic contents delivery through WiFi network the demanded bandwidth should be provided.

Our results also show that quality of 3D presentation is also strongly influenced by quality of stereo shooting and 3D production. More cameras using (today for 3D movie filmmakers use 10 -20 cameras with high quality) also causes increase of 3D videostreams robustness. The stereoscopic type of displaying also could case "visual discomfort" as well. Researchers working in vision and graphics are attempting to develop new techniques and technologies to overcome the current limitations in 3D stereoscopic presentation.

Primary importance of QoE investigation in wireless transport network environment is came to the front due to the worldwide growing of video-streams presentation on smart but small mobile devices.

Therefore future work will address investigation of gathered information from experiments carried out with smart mobile devices on client sides and all research works results in the subject: investigation of QoE -QoS relationship for 3D stereoscopic videos delivery can be used in future research work. The goal is mathematical modeling of functional relationship between QoE and QoS metrics which is needed for optimal solution of 3D stereoscopic video contents delivery with appropriate display quality.

Figure 1

 1 Figure 1The GPON-based + WiFi sub-networks topology Hardware configurations of transport network's devices, multimedia server and clients are also mentioned in[START_REF] Kulik | Investigation of Quality of Experience for 3D Streams in GPON[END_REF]. Types of used Access Points were: Linksys E4200 Dual-Band N Router and Linksys WRT160NL-EE Router which were connected to 100Mb/s Ethernet port of ONTs. PCs' displays were Samsung Syncmaster 2233 with screen size 22"and resolution 1920 x 1080 and we used WiFi cards: TP Link TL-WN95IN.

Figure 2 Active

 2 Figure 2 Active WiFi networks in the laboratory environmentSecond important reason was one technical parameter of ONT: 100Mb/s Ethernet port which was directly connected to the AP. This throughput also prevented to get convenient vision quality during the watching. Therefore network topology of reference test was reduced to only one ONT, one AP and one PC on the client's side. We carried out reference test measuring with Linksys E4200 Dual Band N Router used channel 3. for IEEE 802.11n standard based connection and other reference test with Linksys WRT160NL-EE router used channel 13. for IEEE 802.11n standard based connection. In first case mean value of result scores was 4.8 (close to excellent) and in second case mean value was 4.5 (between excellent and good. Scores were always recorded by the test persons for 5 important viewpoints mentioned above. NVPv1.6 used and default buffering time during the whole experiment 440ms.

Figure 3

 3 Figure 3 QoE degradation based on bandwidth limitation Appropriate mathematical descriptions were calculated by the Wolfram Alpha application. Applying the method of least squares we got solutions: 3.channel + 13.channel: 21225 . 3 550797 . 0 02543 . 1 767565 . 0 2 3     x x x (4)

Figure 4

 4 Figure 4 Data sequences stuck in the highest motion level In case of confidence intervals (CI) we presupposed normal distribution and 90% confidence interval and we calculated based on requirements: Deviation of appropriate variable and the critical value multiplied together gives the CI. Figure in middle shows line of weighted averages of all results (3. channel + 13.channel results) and lines above and under show margins of CI.

Table 2

 2 and Table 2. WiFi networks characteristics during the experiment

	Title	Video codec	Audio codec	Container format
	Avatar	WMPv9 (VC-1 Simple/Main)	WMAv2	wmv
	Length (mm:ss)	Resolution	Avrg. Video bitrate (kb/s)	Avrg. Audio bitrate (kb/s)
	03:32	1280 * 720	9646

Table 3

 3 Summary of Calculated Weighted Values

			Bandwidth [MB/s]
	3D QoS	5.0	4.75	4.50	4.25	4.0	3.75	3.50
	3D QoE	3.2167	3.1266	3.0750	3.0521	2.9861	2.5556	2.1250
	+ conf. interval	3.5101	3.4171	3.3518	3.3066	3.2186	2.8042	2.3868
	-conf. interval	2.9233	2.8608	2.7982	2.7978	2.7536	2.3070	1.8632

The research was supported by NKTH-OTKA grant CNK77802.


László Blázovics
email: laszlo.blazovics@aut.bme.hu

Tamás Lukovszki
email: lukovszki@inf.elte.hu

Bertalan Forstner
email: bertalan.forstner@aut.bme.hu

Target surrounding solution for swarm robots ⋆

Keywords: robot swarm, distributed control, convergence

In this paper we present a distributed algorithm, which enables to follow and surround moving objects by a swarm of homogenous robots that only use local sensing. We introduce the multi orbit surrounding problem and present a solution for it. We prove that our solution always guarantees that the robots enclose the target and circulate around them. We also evaluate our solution by simulations.

Introduction

The cooperative control of biological and artificial intelligence have been being a popular research filed of many scientific researchers. The origin of the research of the swarm behavior can be dated to 1987. In this year Reynolds [START_REF] Reynolds | Flocks, herds and schools: A distributed behavioral model[END_REF] published a method about creating realistic flock motion in a virtual reality. Since this the way of controlling multiple entities has changed significantly. Instead of using a centralized coordinator for controlling the movements of the other entities, Reynolds described and implemented a decentralized control method.

Reynolds achieved a realistic flocking model by the definition of the following three simple rules, which should be individually obtained by each virtual bird :

1. Match the velocity of the other members of the swarm. 2. Avoid collision. 3. Avoid getting too far from the others.

By defining these simple rules the computation complexity was dramatically reduced.

In order to control the formation and the direction of the motion of these kind of asynchronous systems many solutions are using potential or gravitational fields to move the entities [START_REF] Cohen | Convergence properties of the gravitational algorithm in asynchronous robot systems[END_REF]. Besides the low computational complexity it is also oblivious, which is ideal for the desired artificial robots of the swarms.

Our contribution: We introduce the multi-orbit surronding problem, where autonomous robots with limited sensing range have to surround a target and circulate around it. We describe a simple algorithm to solve this problem, where each entity only needs information about the entities in its local environment and the target. We prove the correctness and the convergence of our solution and also provide simulation results.

Outline of the paper: This paper is organized as follows. Section 2 gives an overview of related work. In Section 3 we introduce our multi-orbit surrounding algorithm and mathematical notations. We prove the convergence of the algorithm in Section 4. Section 5 presents our experimental results and our simulation environment. Finally, Section 6 summarizes the work.

Related work

There are many other working implementations of swarms which rely on the work of Reynolds like the RAVEN project of the MIT [START_REF] How | Real-time indoor autonomous vehicle test environment[END_REF] the UAV system [START_REF] Bürkle | Towards autonomous micro uav swarms[END_REF], or a military solution for UGVs [START_REF] Balch | Behavior-based formation control for multirobot teams[END_REF]. The main goal of these implementations is to design a stable group of quasi autonomous robots that can keep dedicated formations.

One of the most simple solution is created by Mataric [START_REF] Mataric | Designing and understanding adaptive group behavior[END_REF]. She defined five easily adoptable rules which comforms to the rules of Reynolds. These five behaviors are the following.

Safe-Wandering:

The ability of a group of agents to move about while avoiding collisions with obstacles and each other. 2. Following: The ability of an agent to move behind another retracing its path and maintaining a line or queue.

Dispersion:

The ability of a group of agents to spread out in order to establish and maintain some minimum inter-agent distance. 4. Aggregation: The ability of a group of agents to gather in order to establish and maintain some maximum inter-agent distance. 5. Homing: The ability to find a particular region or location.

By using these five basic rules more dynamic and complex behaviors can be constructed. However the effectiveness of this solution was shown only through simulations.

From the mathematical perspective there are many approaches which are able to clearly formalize the swarm behavior. Most of that are using the already introduced artificial potential fields [START_REF] Gazi | Stability analysis of swarms[END_REF], [START_REF] Chu | Self-organized motion in anisotropic swarms[END_REF], [START_REF] Hsieh | Pattern generation with multiple robots[END_REF], [START_REF] Hsieh | Stabilization of multiple robots on stable orbits via local sensing[END_REF], [START_REF] Leonard | Virtual leaders, artificial potentials and coordinated control of groups[END_REF], in order to define interaction control forces between neighboring entities and the environment itself. The benefit of this formalism was the easy provability of the stability of the overall system.

Gazi et al. [START_REF] Gazi | Stability analysis of swarms[END_REF] have presented a virtual potential field based solution which are able to stabilize swarm of homogenous entities in an n-dimension Euclidean space. Based on this approach Chu [START_REF] Chu | Self-organized motion in anisotropic swarms[END_REF] has extended this to be able to handle heterogenous entities. However, by using interactive matrix, the final shape of the swarm will be rough in contrast with the sphere form of Gazi's solution. Neither of these solutions are taking care of those situations where the average velocity of the swarm is not zero.

Leonard and Fiorelli [START_REF] Leonard | Virtual leaders, artificial potentials and coordinated control of groups[END_REF] proposed a concept for the above mentioned problem. They introduced virtual leaders, which are moving "independently", while they are followed by the rest of the entities.

Hsieh et al. [START_REF] Hsieh | Stabilization of multiple robots on stable orbits via local sensing[END_REF] also used virtual potential fields in their solution in order to keep entities in a dedicated smooth shape "orbit". Once the entities have reached the given trajectory, they are using the tangential speed to avoid interagent collisions.

Barnes et al. [START_REF] Barnes | Swarm formation control utilizing elliptical surfaces and limiting functions[END_REF] has presented a similar methodology to the work of Hsieh. However they have been using multiple weight functions depending on the distance from the center of the potential filed. We have modified and extended their weight functions in order to decrease the time while the entities are reaching the desired trajectory.

Cohen and Peleg [START_REF] Cohen | Convergence properties of the gravitational algorithm in asynchronous robot systems[END_REF] presented an asynchronous algorithm to gather entities at the center of gravity. Their algorithm uses the LCM (Look-Compute-Move) discrete cycle based model to move their robots. They mathematically proved upper and lower bounds on the convergence speed of their solution. Cord-Landwehr et al. [START_REF] Cord-Landwehr | A new approach for analyzing convergence algorithms for mobile robots[END_REF] described an easy-to-check property of target functions that guarantee convergence and gives upper time bounds. This property holds for the target function in [START_REF] Cohen | Convergence properties of the gravitational algorithm in asynchronous robot systems[END_REF] and improves the upper bound on the speed of the convergence.

Multi-orbit surrounding

In this section we will present our solution for target surrounding. We have been using a similar potential field based approach as it was introduced and used by Hsieh et al. [START_REF] Hsieh | Stabilization of multiple robots on stable orbits via local sensing[END_REF] and Barnes et al. [START_REF] Barnes | Swarm formation control utilizing elliptical surfaces and limiting functions[END_REF]. However in order to achieve a faster and more uniform surrounding process we have been using a more complex potential field.

The concept

If multiple entities are trying to capture a moving target one of the most relevant tactic is the surrounding. Most animal groups who are hunting in group -like wolf packs -are following this strategy. Therefore, the main idea of our method is to define a trajectory around the target on which the entities should take place. However, in order to assure that the target cannot escape from the circle of the entities -i.e. the circle is not uniformly filled and there a holes on it -, they should move around him. In order to minimize the possibility of inter agent collision we have defined a heading direction on the trajectory. Nevertheless by the introduction of this strict direction rule on the desired trajectory prohibits the use of a usual pincer movement.

In order to solve this issue, we have introduced the multi-orbit surrounding mechanism. We have defined multiple orbital trajectories around the target which are moving with it. A simple example can be seen on Fig. 1. Each trajectory has a different heading direction like their neighbors. This serves two purposes. First it enables the possibility of the pincer movement while keeping the probability of inter-agent collision low. Each neighboring trajectory pair has different heading direction, which implies that there should be some distance between them in order to minimize the collision probability. Second it accelerates the surrounding process, i.e. if an inner trajectory contains a hole, an additional robot from the next trajectory can fill it in shortest time.

The basic behavior of the entities between two trajectories is a radial movement around the target.

As it can be seen there are two types of trajectories. The first type is the primary trajectory (T primary ). This is the nearest trajectory around the target. The main goal of the entities is to put themselves into orbit on this trajectory. Whenever an entity has reached this trajectory, it stops radial movement and start to move around the target in the given heading direction.

The second type of trajectories is the secondary trajectory (T secondary ). These trajectories are more distant than the primary. If an entity is passing through one of this trajectories during the surrounding process and it is sensing another entity in front of it, it should put itself onto orbit on the current trajectory. By doing this not only the collision will be avoided but the surrounding process will be accelerated: a robot in the secondary trajectory and a hole in the primary trajectory move towards each other.

However if the entities are not staying on any of the above introduced trajectories, it is not allowed to make tangential movements around the target.

Our solution uses the gradient vectors of the potential field to move the entities to the desired direction. The potential of the entities are decreasing while they are approaching the desired trajectory. We are calculating with constant velocity.

Potential field based approach

In this section we present the mathematical notations for our potential field based multi-orbit surrounding solution.

Let the two dimensional potential function -which generates the potential field -of the target be the following:

f (x,y) = e -α((x-xc) 2 +(y-yc) 2 )
(1)

The x c , y c are the coordinates of the target, α is a positive parameter. The gradient of this function can be seen on the Figure 2(a) and it is look like as follows:

d x = -2αf (x, y)(x -x c ) d y = -2αf (x, y)(y -y c ) (2)
This gradient can be used for a pure attractive function. In order to keep the entities away from the close proximity of the target, a repulsion function should be used. This can be achieved by inverting the direction of the gradients.

d x = 2αf (x, y)(x -x c ) d y = 2αf (x, y)(y -y c ) (3)
The next part of our function gradient set is the perpendicular gradients. This will be used for the circulation on the trajectories. These gradients can be generated by a simple rotation. See Figure 2(b).

d x = 2αf (x, y)(y -y c ) d y = -2αf (x, y)(x -x c ) (4)
In order to limit the attraction and repulsion and perpendicular forces to the desired areas, weight functions should be used. For the attraction and repulsion functions the following weight function is sufficient:

W rad = 1 1 + e -αout(r-(R+Rout)) - 1 1 + e αin(r-(R-Rin)) (5)
Where R is the radius of the primary trajectory, r is distance function which is rotation invariant, α in , α out , R in and R out are positive parameters. More detailed description can be found in [START_REF] Barnes | Swarm formation control utilizing elliptical surfaces and limiting functions[END_REF].

In order to localize the perpendicular forces to the primary trajectory another weight function should be introduced:

W tan = e -α ⊥ (r-R) 2 0 1 -1 0 (6)
Where α ⊥ is a positive parameter. By combining these two weight function in the following equation of V = v x v y T , the entities will move until they reach the primary trajectory where they start their orbital motion, as it can be seen on Figure 2(c).

V = (W rad + W tan ) ∂x (7)
Where ∂x = d x d y .

In order to extend this system with our multi-trajectory solution we have generated a new weight function which can be seen on Figure 2(d) and looks like as follows:

S tr = (2 - 1 2 + e r )sin(α tr r) (8)
S out = 1 1 + e αout(r-(R+Rout)) (9)
W * tr = S out S tr [START_REF] Hsieh | Stabilization of multiple robots on stable orbits via local sensing[END_REF] The S tr component generates the distinct trajectory curves with a slightly increasing tangential speed while the S out limits its gain to the outside of the primary trajectory.

However it is not efficient when every entity start to move along on the secondary trajectories before reaching the desired trajectory. This is only required when they are not able to move directly towards the desired position. This can only happen, when there is another entity in the way, which means that this newly introduced weight is required only in collision avoidance situations.

Therefore we have extended this by adding proximity parameters to it:

W tr = i∈X W * tr λ - λ 1 + e -α avoid (r avoid -R avoid ) ( 11
)
The λ is a parameter like the κ, nevertheless it should be minor: λ < κ/2. The final velocity vector of a given entity looks like as follows:

V = (W rad + W tan + W tr ) ∂x (12)
4 Analysis of the convergence

In this section we prove that by using of the above introduced surrounding method a swarm of robots will always enclose a given target. For this we use following assumptions.

Assumptions:

1. The entities are modeled as points.

2. There is only one static target at the same time.

All entities know the position of the target.

4. All movements of the entities are divided into discrete steps.

5.

In each step a robot can move a unit distance in the direction determined by the potential field or stay in place if this movement is prohibited by another robot. 6. The distance d(u, v) between each pair of entities u, v must be at least some constant d min < 1. 7. The distance between neighboring trajectories are 1 unit, i.e. r i+1 -r i = 1, i = 0, 1, ..., where r i is the radius of the i th trajectory T i .

8. The sensing range of the entities is at least d min +2. Thus, each entity which could get closer than d min after one time step is within the sensing range. 9. The entities are able switch between neighboring trajectories within one time step.

Remark: For simplicity, we assume a static target. This assumption can be changed for a slowly moving target. In that case the unit velocity of the robots must be relativ to the velocity of the target.

Convergence

Each entity tries to move straight into the direction of the target. If it is not possible, because it would get too close to another entity, it moves on the trajectory containing their current position. Note that by Assumption 5,6, 7, and 8, all entities that could be closer to an entity v than d min in the next time step and could cause a collision with v, are within the sensing range of v.

We assume that at the beginning the distance between each pair of eintities u and v is at least d min . We prove that the entities always can move, never stuck in deadlock situation and we give a convergence guarantee of the surrounding process.

We say that two entities u and v prohibit each others movement if the above rule would cause collision. In that case the entity with lover potential is allowed to move. In order to break ties, we assume that each entity v ∈ V has a unique ID denoted by v.ID and each entity knows the IDs of the entities within its sensing range 1 .

We say that an entity v has a higher priority than another entity u, iff ϕ(v) < ϕ(u) ∨ (ϕ(v) = ϕ(u) ∧ v.ID < u.ID). Thus, we have a straight total order on the entities. If two entities prohibit each others movement, the entity with higher priority is allowed to move.

First we show that each entity can move eithter staight into the direction of the target or on the trajectory around the target. Therefore, the potential of an entity never increases. Lemma 1. Each entity v, which is not on the innermost trajetory, can move straight towards the target if v is not prohibited by another entity u with higher priority. Otherwise, v can move on the trajectory around the target in the corresponding heading direction. The potential of v never increases during the surrounding process.

Proof. First we consider an entity v which is already on the innermost trajectory T 0 . We show that v can move on that trajectory and its potential never increases. Since all entities on T 0 (if any) move in the same direction around the target, their distance to each other remains the same, and thus, they do not cause a collision. Another entity u with a higher potential ϕ(u) > ϕ(v) is only allowed to move to T 0 , if it does not cause a collision. Now we consider an entity v which not in T 0 . If v is not prohibited to move straight towards the target by any another entity u with higher priority then it moves towards the target and its potential strictly decreases. Otherwise, by similar argument than above, v can move on the trajectory corresponding to its current position and its potential does not change.

⊓ ⊔

Now we are able to prove a guarantee of the convergence of the surrounding process.

Theorem 1. Until the inner trajectories have not been filled with robots (i.e. an inner trajectory T in contains a hole of length at least 2d min ), the overall potential energy of the swarm is strictly monotonically decreasing within r om • π + 1 steps, where r om is the radius of the outermost trajectory T om .

Proof. Our rules guarantee that no robot increases its potential. If a robot is not prohibited by other robots, it is moving on a straight line towards the target, until it reaches the innermost trajectory. If a robot do not decreases its potential in a time step, then it is either on the innermost trajectory or it is prohibited to decrease the potential by another robot with higher priority.

Assume that in a time step no robot can decrease its potential. Let T i be the innermost trajectory which contains a hole of length at least 2d min . Let r i be the radius of T i . Consider the robot v with the highest priority among the robots having strictly higher potential than the robots on T i . If no such robot exists, then we are done, all inner trajectories are filled. Otherwise, v can only be prohibited to move straight to the direction of the target by robots on T i . Then v circulates on trajectory T i+1 . The robot v and the hole on T i circulate in opposite direction. Within r i π + 1 steps either v can move into the hole on T i or another robot filled the hole before v. Thus, within r i π + 1 steps at least one robot strictly decrease its potential.

⊓ ⊔

Simulation Environment and Validation

In this section we will present our experimental results, which were made by the V-REP Virtual Robot Experimentation Platform, which is a 3D robot simulator with an integrated development environment.

We have created a compact 2D model that is easily extendable into a 3D model. Our virtual entities use infrared distance sensors, however a vision based solution is also usable for simultaneously scan the foreground and track the target. Although our entities are using local sensing only, it is possible to extend it with a communication layer for an extended model.

Besides the scanning of the neighborhood the entities should also track the target itself. Although we have made an assumption that all entities know the position of the target, we have tried to be more realistic in order to ease the integration of our simulation environment into a real implementation.

In Section 5, for simplicity, we have assumed a static target and we remarked that it can be changed for a slowly moving target. Then the unit velocity is relative to the velocity of the target. In our simulations we have a slowly moving target.

We compared our multi-orbit surronding algorithm (Algorithm 1) with another simple algorithm, which we call baseline algorithm (Algorithm 2), where the entities move to the left on the trajectory corresponding to its current position, if they are prohibited to move towards the target. In the first simulation scenario the entities are forming a row behind the target which is moving to the opposite direction. Fig. 3 shows the trajectory of the entities during the surrounding process until the the stationary state, where the swarm is circulating around the target. If the entities use an unidirectional surrounding behavior like Algorithm 2, which can be seen in the left image of Fig. 3, instead of our multi-orbit surrounding concept (middle and right image of Fig. 3), the surrounding takes longer.

In our second simulation scenario the start positions of the robots formed a block, i.e. they were distributed in a square area in a grid with d min distance from the neighbors. At the beginning of the simulation many robots was prohibited to move towards the target. Our multi-orbit algorithm handeled this situation easily. In our third scenario the start positions of the robots were chosen randomly from the simulation area. In this scenario almost all robots were able to move straight towards the target until they reached the available innermost trajectory. The results of the simulations are summarized in Table 1. Table 1. Simulation results where 15 entities are surrounding a moving object.

Summary

We have defined the multi-orbit surronding problem, where autonomous robots with limited sensing range have to surround a target and circulate around it. We have described a simple local algorithm to solve this problem. We have proved the correctness and the convergence of our solution and provided simulation results.

Fig. 1 .

 1 Fig. 1. Three circular trajectory curves and their headings around a given target.

Fig. 2 .

 2 Fig. 2. Different vector fields generated with the gradients

Fig. 3 .

 3 Fig. 3. Simulated trajectories for the first test scenario, where 15 entities are surrounding a moving object.

5 •

 5 vtarget 5• vtarget 5• vtarget 5• vtarget 5• vtarget 5• vtarget enclosing time (min) 3

For example, the entities within the sensing range of each other exchange their IDs through their communication interface.

⋆ This work is connected to the scientific program of the "Development of qualityoriented and cooperative R+D+I strategy and functional model at BUTE" project. This project is supported by the New Hungary Development Plan (Project IDs: T ÁMOP-4.2.1/B-09/1/KMR-2010-0002, T ÁMOP-4.2.1/B-09/1/KMR-2010-0003).