Thorsten Schlachter
email: thorsten.schlachter@kit.edu|clemens.duepmeier@kit.edu

Eric Braun
email: eric.braun2@kit.edu

Clemens Düpmeier

Christian Schmitt
email: christian.schmitt@kit.edu

Wolfgang Schillinger
email: wolfgang.schillinger@lubw.bwl.de

ISESS 2017 -A Generic Web Cache Infrastructure for the Provision of Multifarious Environmental Data A Generic Web Cache Infrastructure for the Provision of Multifarious Environmental Data

Keywords: Environmental information systems, Generic data model, Master data, Time series, Spatial data, Semantics, Schema, Microservices, REST, Web portals, Mobile apps, Container-based virtualization, Cloud computing, Open government data, Linked data, Semantic Web

As a basis for the efficient data supply for web portals, web-based and mobile applications of several German environmental authorities, a microservice-based infrastructure is being used. It consists of a generic data model and a series of corresponding generic services, e.g. for the provision of master data, metrics, spatial data, digital assets, metadata, and links between them. The main objectives are the efficient provision of data as well as the use of the same data by a wide range of applications. In addition, the used technologies and services should enable data supply as open (government) data or as linked data in the sense of the Semantic Web. In a first version, these services are used exclusively for read access to the data. For this purpose, the data are usually extracted from their original systems, possibly processed and then stored redundantly in powerful backend systems ("Web Cache"). Generic microservices provide uniform REST interfaces to access the data. Each service can use different backend systems connected via adapters. In this way, consuming components such as frontend modules in a Web portal can transparently access various backend systems via stable interfaces, which can therefore be selected optimally for each application. A number of tools and workflows ensure the updating and consistency of the data in the Web Cache. Microservices and backend systems are operated on the basis of container virtualization using flexible cloud infrastructures.

Introduction

A direct consequence of the Aarhus Convention was the adoption of the EU directive 2003/4/EG [START_REF]Directive 2003/4/EG[END_REF]. This directive, respectively its implementation into national law, e.g. the Environmental Information Act in Germany [START_REF]Umweltinformationsgesetz[END_REF], regulates access to environmental information for the public. Authorities are obliged to the active dissemination of environmental information [2, §7]. The Internet provides a perfect platform for this purpose. Therefore, a lot of environmental information, as well as (raw) data in the sense of open (government) data [START_REF] Ubaldi | Open Government Data -Towards Empirical Analysis of Open Government Data Initiatives[END_REF], are already made available using Internet based applications, e.g. websites, portals, mobile applications [START_REF] Schlachter | My Environment -A Dashboard for Environmental Information on Mobile Devices[END_REF]. Nevertheless, even today, 15 years after the Aarhus Convention entered into force, much environmental information are not yet or only partially available online. The reasons are manifold and correspond with the challenges of providing open government data [4, pp. 30-39]: political, technical, legal, organizational, cultural, and economic reasons are hindering the free dissemination of environmental information. The majority of these barriers cannot be broken down technically, but modern technologies can help in reducing them.

In some cases, however, long-term processes must lead to a rethinking and rerouting of people and institutions in politics and administration. With the concept of a Web Cache presented in this paper, we want to give an impulse how more environmental information can be made accessible to a wider public by addressing at least some of the inhibitory causes.

Idea and Basic Concepts

Starting point of our considerations is that environmental information is made available through central entry points such as Web portals and mobile applications. Most of these applications ultimately use data that have been arisen in the daily work of environmental agencies. Mostly the primary purpose of this (original) data is not information for the public, which leads to the problems and challenges listed above. For example, environmental information include personal data, are subject to licenses, consist of large amounts of information, require appropriate user rights, are stored in special data formats, are not accessible via the Internet, are incomprehensible to lay people, aren't available around the clock, etc. Our basic idea is to provide "Internet-enabled" copies1 of the original data on a "Web Cache" (Figure 1). The information is being extracted automatically from the original systems (data sources), e.g. professional databases and specialist applications, then being processed (data ingestion) and provided in redundant systems (data management). The avoidance of direct access to original data sources allows for better availability and usage-based scaling of services (data services and data management), and offers security benefits by strict separation of internal and external/public requests. Data flow is designed unidirectional from data sources to the Web Cache. So the Web Cache represents a read-only copy of the data. Consistency or coherence conditions are set for each data type and any data source influencing the nature and frequency of synchronization between data source and Web Cache. Limited to mainly unidirectional data flows, the Web Cache application is ideally suited to be implemented as a horizontally scalable microservice-based framework. In general, however, the framework provides the full range of functionality for data management, i.e. functions for adding, updating and deleting data are also available (known as CRUD for create, read, update, delete), also including mechanisms for authentication and authorization, which do not apply for the Web Cache, which exclusively contains public data and does not have any access restrictions for reading.

Architecture and Components

In order to keep efforts of setting up the Web Cache on an acceptable level, it is an essential objective of the project to provide the entire information by means of a limited number of generic services which have to be able to handle a large variety of data semantics. For this purpose, a small set of generic data services and their functionality have been defined allowing the storage of multifarious kinds of data as well as additional semantic metadata in order to provide applications with strongly typed data where necessary. Depending on the application, in addition to newly developed services the use of cloud services off the shelf is eligible2 .

For the implementation of environmental portals, e.g. the LUPO environmental portal family [START_REF] Schlachter | LUPO Umsetzung einer (micro-)serviceorientierten Architektur (SOA) für Landesumweltportale[END_REF], a total of 8 generic services has been identified:

• Master Data Service • Schema Service • Time Series Service • (Media and) Digital Asset Service • (Full Text) Search Service • Geo Data Service • Metadata Service • Link Service
These 8 core services are supplemented by two additional services supporting configuration management of (and therefore rather belonging to) consuming applications:

• Application Configuration Service • Data Discovery Service

These services are described in more detail in section 5.

In a microservice-oriented architecture all services should be independently deployable and usable, and only being coupled loosely. This requirement corresponds to the term "functional decomposition" being used for microservices [START_REF] Fowler | Microservices -definition of this new architectural term[END_REF]. Therefore, each data service provides functionality for managing one single generic type of data.

Packed in runtime containers such as Docker3 , the services can be operated without any additional effort on a variety of possible infrastructures, like dedicated servers, clusters, or in the cloud [START_REF] Cohen | Containers, microservices, and orchestrating the whole symphony[END_REF]. Using runtime infrastructures like Kubernetes4 , operational aspects such as (rolling) updates, monitoring, horizontal scalability and load balancing are just a matter of configuration -assumed an appropriate computing infrastructure and software design.

All services use suitable backend systems, which in particular ensure the persistence of the data. Here, again, the architecture is abstracted from concrete systems, so that backend systems can easily be replaced by others, or different backend systems can be used simultaneously. The selection of suitable backend systems, e.g. various NoSQL technologies, also ensures dynamic properties such as load balancing, scalability, etc. at this level. All services provide their functionality through versioned RESTful interfaces via content negotiation [START_REF] Seemann | REST implies Content Negotiation[END_REF]. This facilitates the development, maintenance, and replacement of individual services.

The postulated independence of services must not lead to a loss of possible functionality, for example by a lack of inter-service interaction. For this purpose, a microservice-based architecture provides a messaging infrastructure (channels) for loose asynchronous coupling of services. However, unlike Gartner's microservice architecture [START_REF] Olliffe | Microservices : Building Services with the Guts on the Outside[END_REF], in applications similar to the Web Cache the functionality of the messaging layer "below" the microservices may be delegated to the data ingestion phase and/or to consuming applications using an event bus [START_REF] Schlachter | LUPO Umsetzung einer (micro-)serviceorientierten Architektur (SOA) für Landesumweltportale[END_REF], a simplification, which is sufficient for a wide range of given use cases with unidirectional data flow.

Generic Data Model

The services mentioned in section 3 are the basic elements of a well-considered generic data model resulting from a use case analysis in different application domains beyond the environmental field. However, we do not claim it to be completely universal. Although the model implements generic data types, it compensates the loss of a strong (relational) schema by using additional semantic services which add missing semantics back into the service-oriented data management infrastructure (like it is done for the Semantic Web). One main advantage of the external provision of semantic information by means of dedicated services is that schema information is not hardcoded anymore, so it can easily be shared between applications.

The core data type of the generic data model is the master data object. A master data object may be a digital model of any entity (of the application-relevant part) of the real world, e.g. a nature protection area, a measuring station, a wind turbine, or a legal document. Each master data object is described by a set of structured properties identifiable by a certain key attribute. This structure can be formalized in a data schema. Objects of the same type use the same schema and belong to the same class of objects (master data). This classification step is of great importance as it directly assigns particular semantics to classes and the respective objects. Relationships between master data objects (or between master data types) can be expressed in various ways, e.g. a composition within a schema (an object consisting of sub-objects), or by the explicit provision of a certain relation between two objects. In general, relations can be typed, directed or undirected, and may have properties as well.

A number of master data types need special consideration. Environmental monitoring often consists of measured values, e.g. time series describing the concentration of ozone on a certain location or the performance of a wind turbine over time. In addition, most environmental objects do have a spatial reference, i.e. (at a certain time) they are located at a specific place in the world and may have specific geometry. The generic data model takes this into account and therefore provides generic data types (and respective services) for time series and spatial data. Digital assets can also be viewed as a special case. Just like other "real world objects", they are usually assigned properties (metadata). In addition, however, the concrete digital object may be provided as well, e.g. as image file, HTML snippet, PDF document or audio/video stream. The generic data types mentioned thus form the basis for specialized services, which offer specific access (service interfaces) to the respective data type.

Data Services

The services are divided into data services, which form the core of the framework, and supplementary services, which focus on the support of consuming applications.

For the Web Cache, the following sections only describe the core data services. Further services, e.g. Link Service and Data Discovery Service, are described in the conference paper by Eric Braun et al. [START_REF] Braun | A Generic Microservice Architecture for Environmental Data Management[END_REF].

Master Data Service and Schema Service

Almost all real-world objects have properties which can be expressed in a corresponding data model. In general, this is not only static or structured data, but there are also dynamic or unstructured parts, e.g. objects can contain components which can be regarded as independent objects, too (subobjects or compositions).

The Master Data Service considered here represents a simplification in comparison to such a general master data model since it essentially stores static and structured data. Other properties, in particular dynamic parts, compositions and relationships, are stored by means of references which can refer to both master data and various data types from other services. For example, the master data of an air measurement station (id, name, location, references to multiple measurement series, etc.) are stored in the Master Data Service (Fig. 2). A measurement series is also stored in the Master Data Service (id, substance, unit, accuracy, references to the measured values, etc.), while the actual meas-ured values are stored in the Time Series Service. The reference type "timeSeries" defines a custom data type not shown here (timeSeries ~ array of measurement).

The Master Data Service primarily provides a service facade, which guarantees a uniform and stable interface to applications. The actual persistent storage of the data takes place in different backend systems, which are each connected to the Master Data Service via adapters. This allows the connection and exchange of various backend systems (e.g. relational or NoSQL databases, search engines) depending on the specific requirements or applications.

In order to store and provide different data types using a generic service, a structural as well as a semantic description of the data is required. The descriptions of all data types are provided via a Schema Service. Since data types can change over time, schemas have to be versioned. Schemas do not only refer to the data types used in the Master Data Service, but also to the contents of all data services within the framework. Services and consuming applications may use these schemas, e.g. to validate incoming data or to use the structure when visualizing the data. The Schema Service and its implementation based on JSON schema5 are described in more detail in [START_REF] Braun | A Generic Microservice Architecture for Environmental Data Management[END_REF].

Using schemas, the Master Data Service and other services may resolve references, i.e. replace references by the corresponding data, or provide references as URLs/HTTP URIs6 . Using server-side communication via message channels, the former can lead to a considerable performance gain and possibly reduce complexity in the client or the consuming application.

On the code base of the Master Data Service, specialized content-specific variants can be set up, e.g. a service for storing and providing metadata. Another possible use is described as "Application Configuration Service" below.

Time Series Service

Since the corresponding master data is already stored in the Master Data Service, the Time Series Service simply stores the actual measured values (time stamp and value per measurement). This again corresponds to the paradigm of the single responsibility per microservice 7 . In the sense of this single responsibility, the Time Series Service, with the aid of the underlying specialized time series databases, is capable of performing specific, time series-related tasks, e.g. filtering of data, data aggregation or unit transformations.

Geo Data Service

The Geo Data Service is used to store and provide spatial data. In many cases, these data correspond to master data, whereby one or more attributes describe the position and/or the geometry of the objects. Therefore, depending on the application, e.g. if no complex spatial operations are required, it is possible to provide spatial data exclusively via the Master Data Service, e.g. using the GeoJSON format. However, if specific spatial operations or special data formats are required, the provision of the data on the spatial data service is useful and necessary.

Since the requirements for the Geo Data Service are still fully supported by a (Cloud-based) solution off the shelf (CARTO 8 ), the implementation of this service is currently postponed. For some applications, data is stored redundantly in both the Geo Data Service and the Master Data Service and synchronized automatically.

Digital Asset Service

Digital assets have the special characteristic that in addition to the descriptive properties (depending on the context called master data or metadata), the object itself can be accessed as binary data stream. Depending on the application, sometimes a link (HTTP URI) on the original asset may be sufficient, in other cases the provision of a copy may be useful or necessary.

Although the range of types of digital assets, their formats, and use cases is significant, the service just considers them as binary data with a certain format (MIME type) and different properties. In other words, the Digital Assets Service generally does not look into the digital assets. If necessary e.g. the Search Service can be used for that.

A digital asset may exist in several variants and/or formats, e.g. images may be available in different resolutions, or a text document either in MS Word or PDF format. According to the mechanisms of content negotiation the client application usually determines required format.

The Digital Asset Service can be connected to different backend systems via adapters, e.g. document management systems providing a CMIS9 interface. Using suitable backend systems, streaming services (e.g. for videos) can be applied as digital assets, too.

Search Service

The last actual data service presented here is the Search Service. It provides index information related to unstructured data, often in the form of text documents. To be more specific, it provides access to full-text indexes, which usually provide relevant excerpts (snippets) from as well as references on the entire document. The Search Service serves as a uniform interface for connecting various full-text search engines, again connected using adapters. The Search Service can also be used in conjunction with the Digital Asset Service, e.g. if an application needs to search the actual content of a document in addition to its metadata.

However, the Search Service can also provide structured data, e.g. when structured and unstructured search results have to be presented in a single view, or when the search engine provides structured information for a facetted search.

The use of the Search Service also simplifies the replacement of a search engine product, usually by creation of an additional adapter. Many search engines can be connected via the existing OpenSearch10 adapter, and web catalogues using the CSW11 interface.

Application Configuration Service

The Application Configuration Service allows applications to store structured information. The service focusses on the reuse of information beyond application boundaries, e.g. complex visualization configurations, map configurations (a map as a compilation of several specific layers), or cross-system settings for individual users.

Technically the Application Configuration Service shares most of its code with the Master Data Service, but there exist some specific extensions, e.g. relaxations with regard to the use of schemas, extended multi-tenant capabilities, vastly limited access, and the use of special service-accounts for authentication and authorization.

Technologies

The diversity of services directly implies the use of different technologies for data management, e.g. geographic information systems, different types of NoSQL databases, time series databases, document management systems, full-text search engines, structured search engines, etc. to match the specific requirements of each case. Services can implement facades accessing underlying (Cloud) services, such as Google Cloud SQL, Bigtable, DataStore, storage, etc.

In addition, tools for data ingestion are required, for example Apache Flume12 , Logstash13 or FME 14 . These tools are essential to ensure the necessary degree of automation for the management of large and diverse data sets, and to be able to control workflows easily and transparently. In addition, they already offer many prefabricated interfaces for the processing of standard data formats, or for adding further interfaces by configuration or by programming of small additional modules.

All services are implemented as microservices based on Java using the "Spring Boot" framework15 , are packaged in Docker containers, and operated on a Kubernetes infrastructure in the Cloud (Google Container Engine). Development instances run on dedicated servers and on a (local) computer cluster, also based on Kubernetes.

Table 1 gives a brief overview of the data services, used frameworks for implementation and runtime environment, and a selection of connectable backend systems.

Service

Experiences

The Web Cache has gradually grown and the presented architecture is in operation since the beginning of 2016. Some precursors of individual services were based on other technologies (Servlets, Google App Engine). With the general idea of the microservice-based architecture in mind during their development, those services could be refactored to "real" microservices. Experiences in development and operation are very positive. Because of the independence and loose coupling of services a gradual start-up was possible. The devel-opment of individual services is straightforward and requires relatively short periods of time.

Nowadays, significantly more data are available for more applications than ever before. Data that previously haven't been available, or have been hidden in business applications, now can be used in many ways, for example, by other special applications, websites, portals and mobile apps. Rising requirements in operation, for example a growing number of accesses, can easily be scaled out on the fly using the horizontal scaling capabilities of the container virtualization infrastructure. The use of container technologies allows a greater independence in the selection of infrastructure operators. Also, the relocation of single or several services is easily possible.

Within consuming applications the use of a generic family of services enables the implementation and reuse of generic, highly configurable frontend components. This additionally simplifies the work of online editors and increases the recognition value for users.

Existing generic services are suitable for many new applications and use cases, usually implemented just by configuration.

By abstracting the (versioned) interfaces (REST APIs) from the underlying internal modules, components or even whole services can be exchanged transparently for consuming applications, depending on the infrastructure even without interrupting operations.

For the synchronization of data sources and services, a high level of automation is possible.

The Web Cache has some positive side effects: With the help of its generic services, it is possible to combine data from different sources, or to create comprehensive views on (disjoint) databases, e.g. from different federal states.

Drawbacks can be seen as opportunities, depending on the approach. The fundamental problem of redundancy (dual operation and redundant data storage with the corresponding additional expenses) generates operational flexibility, and facilitates the provision of "Internet-enabled" data. The necessity of concepts for legal issues, operations, consistency, data schemas and formats, provides opportunities to clarify issues, responsibilities and the (re-)definition of (operational) processes.

Although the provision of data for a wide range of users creates transparency, it also reveals poor data quality in some cases.

Conclusion and Outlook

The Web Cache concept presented in this paper defines a complete architecture for the dissemination of environmental information. The keystone of this architecture is the provision of multifarious types of data by a limited number of generic microservices. Consistent implementation of these services with (versioned) RESTful APIs, and use of container virtualization offer the greatest possible degree of flexibility in the (further) development and operation. In contrast to the development of monolithic applications, individual services or data containers can be provided very quickly. This leads to a gradual improvement of the consuming applications, allowing the "release early, release often" philosophy in the development of modern (mobile) applications. The development of individual services is not yet completed. Existing APIs have to be partly replaced by new, unified, and more powerful versions. This entails a better automatic processing of data, with the aim of being able to provide information according to the ideas of the Semantic Web [START_REF] Braun | A Generic Microservice Architecture for Environmental Data Management[END_REF], e.g. using relevant standard formats such as RDF. This also includes, for example, information on provenance of data as well as usage and exploitation rights.

Currently, only freely accessible data is stored in the Web Cache. In order to provide data with limited access via the Web Cache the existing mechanisms for authentication and authorization have to be instrumented.

Fig. 1 .

 1 Fig. 1. Web Cache architecture at a glance

Fig. 2 .

 2 Fig. 2. Example of master data using a composition (measurement series as sub-objects of air measurement station) and references to actual measurement values in the time series service shown as UML-like diagram and JSON schema

Table 1 .

 1 Services, their underlying frameworks, and backend systems

		Implementation and	Persistence Layer
		Runtime Environment
	Master Data Service	Spring Boot,	Elasticsearch 16
		Docker, Kubernetes	MongoDB 17
			Google Cloud SQL 18
	Master Data Service	Google App Engine	Google Cloud SQL
	(Interim version)
	Schema Service	Spring Boot,	Elasticsearch,
		Docker, Kubernetes	MongoDB
	Time Series Service	Spring Boot,	OpenTSDB 19
		Docker, Kubernetes	InfluxDB 20
			Elasticsearch
	Geo Data Service	CARTO (Cloud)	CARTO
	Digital Asset Service	Spring Boot	Alfresco 21 (CMIS-
	experimental	Docker, Kubernetes	Interface)
	Search Service	Spring Boot,	Google Search Appli-
		Docker, Kubernetes	ance 22
			Elasticsearch
			OpenSearch (Atom)
	Application Configuration	Spring Boot,	Elasticsearch
	Service experimental	Docker, Kubernetes	MongoDB
	Link Service	Spring Boot,	neo4j 23
	experimental	Docker, Kubernetes

An excerpt of the original data meeting all the conditions for publication on the Internet.

Since they may not meet all future requirements, such standard cloud services are rather regarded as interim solutions.

https://www.docker.com

http://kubernetes.io

http://json-schema.org

The use of HTTP URIs as references between objects applies to the core ideas of Linked Data.

As known from Unix as "Do one thing and do it well."

https://carto.com

https://www.oasis-open.org/committees/tc_home.php?wg_abbrev=cmis

http://www.opensearch.org/Home

http://www.opengeospatial.org/standards/cat

https://flume.apache.org

https://www.elastic.co/products/logstash

http://www.safe.com

http://projects.spring.io/spring-boot/

https://www.elastic.co/de/products/elasticsearch

https://www.mongodb.com

https://cloud.google.com/sql/

http://opentsdb.net

https://www.influxdata.com

https://www.alfresco.com

https://enterprise.google.com/search/products/gsa.html


Simon Burkard

Frank Fuchs-Kittowski

Anna O'faolain De Bhroithe
email: anna.ofaolaindebhroithe@htw-berlin.de@htw-berlin.de

Mobile crowd sensing of water level to improve flood forecasting in small drainage areas

Keywords: Flood forecasting, Crowd sourcing, Mobile sensing, VGI, Water level

Flood forecasting is particularly difficult and uncertain for small drainage basins. One reason for this is due to inadequate temporal and spatial hydrological input variables for model-based flood predictions. Incorporating additional information collected by volunteers with the help of their smartphones can improve flood forecasting systems. Data collected in this way is often referred to VGI data (Volunteered Geographic Information data). This paper discusses how this information can be incorporated into a flood forecasting system to support flood management in small drainage basins on the basis of mobile VGI data. It therefore outlines the main functional components involved in such a VGI-based flood forecasting platform while presenting the component for mobile data acquisition (mobile sensing) in more detail. In this context, relevant measurement variables are first introduced and then suitable methods for recording these data with mobile devices are described. The focus of the paper lies on discussing various methods for measuring the water level using inbuilt smartphone sensors. For this purpose, three different image-based methods for measuring the water level at the banks of small rivers using a mobile device and the inbuilt orientation and camera sensors are explained in detail. It is shown that performing the measurements with the user's help via appropriate user interaction and utilising known structures at the measuring points results in a rather robust image-based measurement of the water level. A preliminary evaluation of the methods under ideal conditions found that the developed measurement techniques can achieve both an accuracy and precision of less than 1cm.

Improvement of flood forecasting in small drainage basins through citizen participation in data collection

Floods are one of the natural hazards that directly threaten the civilian population, regularly causing extensive material damage and costing many lives. Damage as a result of flooding has increased considerably in recent decades [START_REF] Müller | Hochwasserrisikomanagement -Theorie und Praxis[END_REF]. There is a very high probability that this trend will continue and the intensity of floods will continue to increase [START_REF] Neumayer | Normalizing economic loss from natural disasters -A global analysis[END_REF]. This is due in particular to the increase in short-term, local flood events. In order to reduce the harmful impact of floods and to be able to take targeted protective measures, disaster relief forces and the affected population must be informed early and reliably of imminent threats through forecasting and early warning systems [START_REF] Kundzewicz | Late lessons from early warnings -science, precaution, innovation[END_REF]. Hydrological and hydraulic forecasting models are used as the basis for decisionmaking for disaster relief measures. Model-based flood predictions are, however, often uncertain and error-prone. The reasons for this include uncertainties on the model and precipitation forecasts, as well as inadequate temporal and spatial hydrological input variables. Predictions are especially difficult for small bodies of water since very fast responses of the basin often occur, leaving very little warning time. There is often insufficient official data for these exceptional situations. However, extra information, such as additional water level measurements along a river, can be used to extend these important data sets and update the forecast models in order to reduce the uncertainties on the forecast [START_REF] Blöschl | Flood warning -on the value of local information[END_REF].

Such additional hydrological data can also be voluntarily recorded and provided by citizens using the inbuilt sensors in their own devices (e.g., smartphones, tablets, etc.) via mobile crowdsourcing and sensing [START_REF] Fuchs-Kittowski | Mobiles Crowdsourcing und Sensing[END_REF]. Location-specific data collected in this way is often referred to VGI data (Volunteered Geographic Information data) [START_REF] Goodchild | Citizens as Voluntary Sensors -Spatial Data Infrastructure in the World of Web 2.0[END_REF][START_REF] Alcarria | Volunteered Geographic Information System Design -Project and Participation Guidelines[END_REF][START_REF] See | Crowdsourcing, Citizen Science or Volunteered Geographic Information -The Current State of Crowdsourced Geographic Information[END_REF]. By incorporating VGI data, the amount of spatial and temporal input information for the prediction models can be increased, reducing uncertainties and therefore improving the predictions of flood forecasting systems. In addition, involving the population in the process raises awareness of flood hazards and citizens can actively contribute to improving flood forecasts and reducing flood damage [START_REF] Fuchs-Kittowski | Mobile crowdsourcing of water level data[END_REF].

In this article, methods for measuring the water level using smartphone sensors (mobile sensing) are presented. It is also discussed how this information can be incorporated into a flood forecasting system to support flood management in small drainage basins on the basis of mobile VGI data. The article is structured as follows: after an overview of the current status of the science and technology (Section 2), the conceptual architecture of such a VGI-based flood management platform is outlined and the functional components involved are described (Section 3). The component for mobile data acquisition (mobile sensing) is then presented in more detail. For this purpose, relevant measurement variables are first introduced and then suitable methods for recording these data with mobile devices are described (Section 4). Various methods for measuring the water level using inbuilt smartphone sensors are explained in detail and evaluated (Section 5). A final summary provides on outlook on future developments within the framework of the presented platform (Section 6).

2

Current status of research and technology

Mobile crowdsourcing and VGI in disaster management

Mobile crowdsourcing refers to the use of mobile devices to collect data as well as to coordinate volunteers involved in the data collection. The core concept is that ordinary citizens collect and share information about themselves or the surrounding environment using their own mobile devices. The participants contribute the data voluntarily, for their own benefit or for the benefit of a community. No task-specific special hardware is used, only normal mobile devices available on the mass market such as smartphones and tablets [START_REF] Fuchs-Kittowski | Mobiles Crowdsourcing und Sensing[END_REF]. The required data is recorded using the built-in sensors in the mobile devices (mobile sensing). Volunteers can be proactively prompted to collect data, and their tasks can be coordinated (mobile tasking [START_REF] Neubauer | Crowdtasking -A New Concept for Volunteer Management in Disaster Relief[END_REF][START_REF] Middelhoff | Crowdsourcing and Crowdtasking in Crisis Management -Lessons Learned From a Field Experiment Simulating a Flooding in City of the Hague[END_REF]). The recorded data are known as VGI data [START_REF] Goodchild | Citizens as Voluntary Sensors -Spatial Data Infrastructure in the World of Web 2.0[END_REF] -usually geospatial measurements that are also often time-referenced.

Closely related to the notion of mobile crowdsourcing are concepts such as VGI [START_REF] Goodchild | Citizens as Voluntary Sensors -Spatial Data Infrastructure in the World of Web 2.0[END_REF][START_REF] Alcarria | Volunteered Geographic Information System Design -Project and Participation Guidelines[END_REF][START_REF] See | Crowdsourcing, Citizen Science or Volunteered Geographic Information -The Current State of Crowdsourced Geographic Information[END_REF], Public Participatory Geographic Information Systems (PPGIS [START_REF] Sieber | Public Participation Geographic Information Systems: A Literature Review and Framework[END_REF]), and Participatory Sensing (PS [START_REF] Burke | Participatory sensing[END_REF]). Common to all concepts is the voluntary and collaborative nature of the data collection and data sharing process.

There are already many different crowdsourcing applications, especially in nature conservation, environmental protection, and disaster management [START_REF] Fuchs-Kittowski | Mobiles Crowdsourcing und Sensing[END_REF]. In disaster management, mobile crowdsourcing can be used to great effect both during and after a catastrophe [START_REF] Middelhoff | Crowdsourcing and Crowdtasking in Crisis Management -Lessons Learned From a Field Experiment Simulating a Flooding in City of the Hague[END_REF][START_REF] Schimak | Crowdsourcing in Crisis and Disaster Management -Challenges and Considerations[END_REF]. For example, in a catastrophe, residents and rescue and emergency personnel can gather information about the current situation in the affected area so that aid and rescue workers can target the most critical zones. After a natural disaster (such as a flood, storm, or heavy rain), finding, documenting, and evaluating damage (such as fallen trees, flooded roads and paths, fallen power masts) is an important task that allows the limited resources to be deployed more quickly and accurately to begin cleanup and repairs. It also allows assessments of the total damage to be up-to-date and comprehensive [START_REF] Abecker | Participatory Sensing for Nature Conservation and Environment Protection[END_REF].

Mobile crowdsourcing applications have already been successfully used in disaster situations, but the accuracy and quality of the information has been of minor importance. VGI data have been used, for example, during floods [START_REF] Kaewkitipong | Lessons Learned from the Use of Social Media in Combating a Crisis -A case Study of 2011 Thailand Fodding Disaster[END_REF][START_REF] De Longueville | Digital Earth's Nervous System for crisis events -real-time Sensor Web Enablement of Volunteered Geographic Information[END_REF][START_REF] Poser | Volunteered geographic information for disaster management with application to rapid flood damage estimation[END_REF], wildfires [START_REF] Goodchild | Crowdsourcing geographic information for disaster response -a research frontier[END_REF], earthquakes [START_REF] Yates | Emergency knowledge management and social media technologies -A case study of the 2010 Haitian earthquake[END_REF], and even severe storms [START_REF] Huang | Web 2.0 and Internet Social Networking: A New tool for Disaster Management? -Lessons from Taiwan[END_REF]. In the system presented in Section 3, VGI data is utilised, among other things, to update and validate forecast models. Therefore, there is a stronger focus on the accuracy and quality of the data recorded using mobile data collection methods.

Flow measurement and mobile sensing for flood forecasting

Hydrological data which can be used to measure the water flow are of particular importance for flood prediction. Flow measurements in hydrometry are mostly indirect and rely on known flow cross sections and measurements of the flow speed and the water level [START_REF] Herschy | Streamflow Measurement[END_REF]. Approaches to automatic flow measurement from images already exist. These are based on remote sensing methods which can be used to estimate the level of a body of water using aerial photographs [START_REF] Smith | Estimation of river discharge, propagation speed, and hydraulic geometry from space: Lena River, Siberia[END_REF], for example. Another example is the use of permanently installed cameras for the image-based measurement of the water level using markers or staff gauges [START_REF] Iwahashi | Water level detection for river surveillance utilizing JP2K wavelet transform[END_REF][START_REF] Kim | Development of a Cloud-based Image Water Level Gauge Development of River Eye system[END_REF][START_REF] Lo | Visual sensing for urban flood monitoring[END_REF][START_REF] Royem | Technical Note: Proposing a low-tech, affordable, accurate stream stage monitoring system[END_REF]. The idea to have passers-by read off the water level at staff gauges was also successfully tested. The reading was sent via SMS [START_REF] Lowry | CrowdHydrology: Crowdsourcing hydrologic data and engaging citizen scientists[END_REF] or an app [START_REF] Fuchs-Kittowski | Mobile crowdsourcing of water level data[END_REF] to a data server for evaluation. The collection of data by mobile users does not necessarily involve manual data input, e.g., in a form, but can be automated by using the sensors already present in mobile devices. The term "mobile sensing" has been established to describe the acquisition and generation of data using the sensors installed in or connected to peoples' own mobile devices [START_REF] Fuchs-Kittowski | Mobiles Crowdsourcing und Sensing[END_REF]. A mobile sensing application specifically for automatic image-based gauge monitoring has been developed by [START_REF] Kisters | Einfach smart -App für Pegelmessung auf Knopfdruck[END_REF]. However, special staff gauges are required for robust measurements, as well as certain other factors such as sufficient brightness and a small distance between the camera and the indicator.

The sensor-based determination of water level lines by mobile devices can be facilitated by the knowledge of the device's exact position in 3D space. Therefore, research in the areas of mobile augmented reality and mobile 3D tracking for position determination is also of interest. These areas of research are still relatively new, but there are already several approaches and technologies for the image-based estimation of a device's own position in 3D space that are more accurate than the localisation provided by GPS signals [START_REF] Amin | Comparative Study of Augmented Reality SDK[END_REF]. There are currently no known existing applications that use such technologies for VGI-based determination of hydrological data.

While there are many mobile applications for information about water levels (e.g., Pegel1 , Pegelstand2 , Pegel-Online3 , Pegelstände4 , Meine Pegel5 ), very few mobile apps exist that allow users to measure the water level. For example, the MAGUN research project has developed mobile applications for the acquisition of current water levels and also historical high water marks [START_REF] Fuchs-Kittowski | A content platform for smartphone-based mobile augmented reality[END_REF], but these are not in widespread use. The goal of the WeSenseIt project is to design and test a complete platform for citizen-based documentation and monitoring of water levels and floods [START_REF] Lanfranchi | Citizens' Observatories for Situation Awareness in Flooding[END_REF][START_REF]WeSenseIt: Sensor Data -Sensors, Citizens, Information and Models[END_REF]. Smartphones as well as various other cost-effective sensors are used for the measurement of hydrological data such as water levels and flow speeds in the project. Information on the robustness and quality of the measured data is, however, not documented. The measured data is also not intended to be directly embedded in a prediction model, i.e., the integration of the data (or the entire process) into a concrete operational scenario -such as flood management -is missing.

Conceptual architecture of a VGI-based prediction system

In this section, the conceptual architecture of VGI-based flood forecasting system is proposed and described. This architecture is based on concepts of generic architectures for crowdsourcing [START_REF] Fuchs-Kittowski | Architecture of Mobile Crowdsourcing Systems[END_REF] and crowdtasking applications [START_REF] Neubauer | Crowdtasking -A New Concept for Volunteer Management in Disaster Relief[END_REF], and has been specifically adapted for VGI-based flood forecasting systems. The functional components are illustrated in Figure 1. In addition to an adapted classical flood forecasting system and central flood management software, the platform includes components for mobile tasking and mobile sensing.

Mobile tasking and mobile smartphone application

Volunteers should have the possibility to independently decide if, and in what form, they wish to record and provide measurements. With the help of smartphone notifications, volunteers can be additionally instructed to record and send data at certain times (mobile tasking). These notifications can be created and sent manually, but can also be sent automatically when coupled with an early warning system. For example, volunteers can be automatically notified and instructed to collect data when heavy rain and potential floods are forecast. Hydrological data are collected via a smartphone application (mobile sensing) in the drainage basin(s) indicated in the flood forecast. The measured data can then be sent over the mobile network or a WLAN connection to a central server for further processing.

Fig. 1. Conceptual architecture of a VGI-based flood forecasting platform

Ideally, the measurements should be made using the integrated sensors in mobile devices. These sensors include GPS sensors for rough positioning (accuracy up to 5 -10 meters) and tilt sensors (compass, accelerometers, magnetometers) for determining the viewing direction of the device as well as the integrated camera used to record images. The use of these sensors, in particular for the measurement of water levels, is explained in more detail in Sections 4 and 5.

In addition to the ability to record and send user-generated data, the mobile application is also intended to provide users with relevant information about floods. With the help of flood risk maps and the representation of current water levels in the area, the user is kept informed about flood risks and the current flood situation.

Model-assisted flood forecasting system

A problem of user-generated data is that the quality and accuracy of the data can vary considerably. Before the measured hydrological data are finally made available to the forecast system as input variables, an automatic quality and plausibility check of the incoming data is necessary. By means of a spatial and temporal comparison of the VGI data sets, erroneous input data (outliers) can be identified and eliminated. Based on a classical model-assisted prediction system, the system can subsequently supplement or validate the underlying model using the available VGI data in order to provide an improved flood forecast.

3.3

Situation monitoring

A web-based user interface (dashboard) is used for situation monitoring. Incoming VGI data and flood forecasts are processed and appropriately visualised to enable an effective assessment of the flood situation. Besides the map-based representations and listings of current and historical VGI measurements and photographs, the hydrographs for the floods as well as official meteorological data such as radar images for precipitation forecasting are also displayed.

Mobile sensing -relevant variables and methods

With the help of the mobile smartphone application, certain parameters can be measured and made available by the volunteers. Relevant parameters are shown in Figure 2.

The selection of parameters that should ultimately be measured results from a consideration of the additional gain provided for the hydrological prediction model versus the technical feasibility of robust mobile measurement methods for these parameters.

The water level and the flow speed of the water at defined measuring points are decisive inputs for the hydrological forecasting system as both parameters are relevant for the direct measurement of the flow rate. However, a meaningful measurement of the flow rate from smartphone measurements alone is very difficult. A rough estimate from the mobile user of the flow rate of the body of water is possible (e.g., "flow is very fast" or "flow is very slow") but an indication of the speed without a physical unit (e.g., meters per second) is not a useful input variable for the prediction system. An image-based estimate of the flow using a smartphone camera would be conceivable [START_REF] Kwonkyu | Surface Image Velocity Measurement System for Wide Rivers Using Smartphones[END_REF]. However, such an approach is quite complex and requires a fixed position from which to record as well as ideal external recording conditions (e.g., ideal lighting conditions). Additionally, it is only possible to roughly estimate the flow speed at the water's surface, but not the speed of currents below the surface. For the mobile measurement of the water level, however, there are several approaches. These techniques are presented in detail in Section 5.

Fig. 2. Relevant parameters and possible measurement methods

Other relevant input parameters for the model are the current precipitation intensity and the depth of snow. However, robust automatic measurement methods using smartphones are difficult to implement for these parameters. Although an image-based estimate of the current rain intensity is possible [START_REF] Garg | Vision and rain[END_REF], the result is often erroneous. Instead, a manual estimate of the intensity of precipitation can be provided directly by the volunteer. This rough estimate of the intensity ("no rain", "light rain", "heavy rain"), combined with the location of the user as determined by the GPS signal, is helpful for improving the localisation of strong precipitation cells.

The depth of snow can also be estimated by the volunteer. A rough knowledge of the snow conditions with high spatial resolution facilitates an estimate of the volume of water contained within the snow cover in the drainage basin. This estimate can be of great benefit as an input parameter for the prediction model.

In addition to these quantitatively measurable values, photographs and short video clips taken with the smartphone camera can be included. These recordings can be displayed on the dashboard map and aid the relief forces in assessing and documenting the flood situation in the field. Measured water levels can be augmented with additional images. This function can also be used to locate floods and flood damage. Volunteers can, for example, monitor critical locations in case of a flood threat to see if a flood has actually occurred and if so, take pictures to document and share its extent.

Methods for water level measurement

The main focus of the development of the mobile sensing component is the implementation of suitable methods for measuring the water level with a smartphone. Measurements of the water level are not taken at arbitrary locations, but at fixed measuring points (e.g., bridges). There are several possible methods available to measure the water level with a smartphone, see Figure 3. The functionality and suitability of these methods will be described in more detail in the following section. The focus of the current discussion is the presentation and evaluation of the methods for semi-automatic imagebased measurements.

Fig. 3. Options for mobile water level measurement

Manual reading of staff gauges

In the simplest case, the water level can be measured by simply reading it from an existing calibrated staff gauge and entering the value into the smartphone application via a classic interface (e.g., slider or text input field). This method is quite robust. It is independent of the smartphone sensor and is also possible under unfavourable lighting and weather conditions. However, visible and accessible staff gauges that have been calibrated and installed at the measuring points are a prerequisite for this method.

Fully automatic image-based water level measurement

Another option is a fully automatic image-based measurement of the water level. The general idea is that, after taking a photograph from a more variable position, an image analysis algorithm automatically determines the water level from the picture without further input from the user. A prerequisite for this method is the presence of an appropriate marker. This can be an easily-visible staff gauge or other artificial marker. The area of the marker still visible above the water line can be determined by means of classical image or text recognition algorithms in order to determine the water line and thus the water level. As the appearance of the markers is known in advance, the recognition algorithms can be specially trained and adapted for this particular application using test images. Under ideal conditions, such a fully automatic procedure facilitates high-accuracy measurements, but the method is not always sufficiently robust and is often error-prone. The marker is often not sufficiently visible or the water line not sufficiently pronounced due to general light conditions (e.g., shadows or darkness) or close-by structures (e.g., walls with uneven surfaces). Other structures are often more prominent in the photograph and interfere with the algorithms' recognition of the marker or water line.

Semi-automatic image-based measurement

Performing the measurements with the user's help via appropriate user interaction (e.g., drawing reference points on the image) and utilising known structures at the measuring points (e.g., a building on the river bank) results in a rather robust image-based measurement of the water level. As the measurements are made at predefined points and the flow cross section at these points must be known in advance of the flow calculation, it can be assumed that the dimensions of surrounding structures at these location are also known, e.g., the height and width of a bridge railing or the height of a wall beside the river relative to the riverbed (the zero-point of the gauge). This knowledge can be used in the development of the measurement method. In the following subsections, three different methods to measure the water level using the camera and orientation sensors of a smartphone, assuming the parameters mentioned above are known, are presented. The three variants are roughly sketched in Figure 4.

Fig. 4. Methods for semi-automatic image-based water level measurement

Variant A -Inclination. The general idea of this variant is that the inclination of the device with respect to a predefined reference line on the opposite bank of the river and the current water level is measured with the aid of the smartphone's rotational sensors (accelerometer and gyroscope). If the measurement is always preformed at a fixed measuring point, the current water level can be determined. A requirement for the procedure is that the reference line must be parallel to the horizontal water line and in a plane orthogonal to the water surface. Quay walls or boundary walls or railings are usually suitable for this purpose. The measuring point should be parallel to the reference line on the opposite side of the river. A horizontal line is overlaid in real time on the camera image. The user first aligns this displayed line with actual reference line by rotating the phone and confirming once both lines coincide. In the second step, the user performs an analogous process, this time aligning the displayed line with the water line.

If the height of the reference line relative to the river bed (the zero level point) is known along with the orthogonal distance between the measuring point and the reference line, the water level can be calculated using trigonometry. Variant B -Reference points. This variant also assumes that the measurement is made from a fixed point. Additionally -analogous to variant A -a reference object or at least two reference points with a known position relative to the measuring point must be present on the opposite side of the river.

The position (3D coordinates) of the reference points are defined with respect to a predefined position of the smartphone camera (camera coordinate system) at the measuring point. The camera projection matrix (an intrinsic parameter of the camera) is used to calculate a projection of the points onto the camera image. This projection is displayed over the camera image. In calculating the projection, no rotation is taken into account, i.e., the identity matrix is defined as a fixed orientation. The orientation sensors are not used in this variant.

The user rotates the smartphone in the first step until the projected reference points are directly aligned with the actual reference points in the image. In this way, the rotation matrix of the device is forced fixed to be the identity matrix (i.e., zero rotation). From this camera position, the user then takes a high-resolution photograph. In the second step, the user indicates the water line in the photograph. This can be done, for example, by moving two points around on the picture, which when taken together, define the water line. The water level can then be derived in a simple manner given a knowledge of the position of the measuring point with respect to the reference points and the river bed (zero level point) and with the requirement that the water line and the reference points lie in the same plane.

Variant C -Correspondence points. This last variant is based on the general idea that the measuring position can be determined if the user draws at least four points on the image that correspond to known reference points. In contrast to the former two variants, no fixed measuring position is required for this method. The user can take a photograph from any position provided that the defined reference points are located within the field of view of the camera. The chosen reference points must lie in the same plane as the water line on the opposite side of the river bank, as in the previous variants. Furthermore, it is assumed that the distances between the each of the reference points and the zero level point (river bed) are known. Following a manual selection by the user of the reference points in the photograph, a homographic relationship can be determined between the camera image plane P1 and the plane P2 on the opposite side of the river in which the reference points lie. In the second step, the water line is additionally drawn on the image by the user, that is to say in the plane P1, and this line can be projected onto P2 using the known homography. In this way, the water level can be directly determined in the coordinate system of P2.

Evaluation

The three variants for measuring the water level were implemented in a demo application for the Android platform. With this prototype, it was possible to test the accuracy and precision achieved by each method when measurements were taken under ideal conditions.

To perform the measurements, reference lines or a reference object (dimensions: 150cm x 55cm) as well as a fictitious water level were defined on a vertical wall in order to simulate an ideal measuring site on a small river. The imaginary water level was drawn at 95cm above the ground (defined as the zero point). The water level was measured with each of the three methods using a Galaxy S4 (GT-I9515) as a test mobile device. For each method, the measurement was repeated 20 times. For variants A and B, which both require a fixed measuring point, the measurements were performed at a distance of 300cm from the reference object. For variant B, a camera height of 150cm was also defined. For variant C, the distance between the measuring point and the reference object varied from about 200cm to 400cm, and the viewing angle varied up to ±45 degrees. The results of the test measurements are shown in Figure 5. It can be seen that Variant A consistently overestimates the water level. This is the most inaccurate method, and with the largest errors, also the most imprecise. Variants B and C determine the water level relatively accurately and the mean values of the data sets agree with the true water level within the calculated errors. Variant C achieves the highest precision of all the tested methods with a standard deviation of less than 1cm. This variant also allows the greatest flexibility as the measuring point is not fixed. However, the measurements take longer to perform than with variant A or B as all four correspondence points must be input manually by the user. Variants A and B may therefore be preferred if a quick measurement is important. It should be noted that the above results were achieved in an ideal environment. Under real conditions, appropriate reference objects may only be available with certain limitations (e.g., the plane in which a reference object lies may not be completely identical to the plane in the water line is measured), introducing larger inaccuracies.

Conclusion and outlook

In this article, methods for measuring the water level using the sensors integrated in smartphones (mobile sensing) have been presented. It has been described how mobile VGI data can be incorporated into a flood forecasting system to support flood management in small drainage basins. The use of such mobile techniques for measuring the water level or recording snow depth and precipitation intensity increases the density of available hydrological and meteorological data and can thus improve the accuracy of flood forecasts. It has been shown that image-based measurement methods can be developed to determine the actual water level to within a few centimetres by using the built-in orientation and camera sensors in common mobile devices. The presented evaluation reveals that such high accuracies can be realised under ideal conditions. The challenging task will be to achieve equally satisfying results when transferring the presented measurement techniques into real-world environments. In real-world situations, further conditions and parameters have to be taken into account when performing measurements using the discussed techniques. An essential premise will be finding and surveying suitable measurement locations meeting the aforementioned requirements of the measurement methods (e.g., suitable reference objects, accessible fixed measurement positions, definable flow cross sections etc.). In addition, the identification and marking of such reference points and measurement positions as well as the usability and user friendliness of the mobile app will be an important role for the success of the mobile sensing methods. Only if the instructions and exact measurement procedures are clearly and unambiguously comprehensible to all user groups can the complex measurement methods be executed successfully.

In the next steps, the feasibility of the methods will therefore be tested more intensively under real-life conditions at selected locations along small rivers. Following this, a pilot phase involving a larger number of potential users will allow the evaluation of the proposed flood forecasting platform along with the general feasibility and efficiency of the VGI approach within the scope of flood management. Only after such field tests are complete, can the accuracy and efficiency of the presented water level measurement methods be evaluated conclusively.

Fig. 5 .

 5 Fig. 5. Results of the different measurement methods

Table 1 .

 1

	Variant	A	B1	B2	C
	Mean [cm]	102.95 ± 3.44	94.47 ± 1.51	94.88 ± 2.69	95.35 ± 0.67

Table 1 .

 1 Results of the different measurement methods

https://play.google.com/store/apps/details?id=de.posts.Pegel

https://play.google.com/store/apps/details?id=info.pegelstand.pegelstandnoebasic

https://play.google.com/store/apps/details?id=org.cirrus.mobi.pegel

https://play.google.com/store/apps/details?id=com.lifestream_creations.pegelmelder

https://play.google.com/store/apps/details?id=de.hochwasserzentralen.app&hl=de


Petr Fiala
email: pfiala@vse.cz

Petr Šauer
email: sauer@vse.cz

Environmental Modelling with Reverse Combinatorial Auctions: CRAB Software Modification for Sensitivity Analysis

Keywords: environmental management, decision-making, sensitivity analysis, reverse combinatorial auctions

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

Introduction

The paper builds on work published in ISESS 2013 [START_REF] Šauer | Modelling of Environmental Risk Management under Information Asymmetry[END_REF] and in ISESS 2015 [START_REF] Šauer | Water Pollution Reduction: Reverse Combinatorial Auctions Modelling Supporting Decision-Making Processes[END_REF], where the general model of the theory of reverse combinatorial auctions and its selected environmental applications were presented. At the same time, we presented the results of laboratory experiments showing whether and to what extent the negotiating parties at auctions are able to approach the optimal result. The main practical goal of the paper was to contribute to increased cost-effectiveness of waste water cleaning projects [START_REF] Berbel | A Cost-Effectiveness Analysis of Water-Saving Measures for the Water Framework Directive: the Case of the Guadalquivir River Basin in Southern Spain[END_REF], [4] in conditions where coalition solutions are possible. The previous research results [START_REF] Šauer | Modelling of Environmental Risk Management under Information Asymmetry[END_REF], [START_REF] Šauer | Water Pollution Reduction: Reverse Combinatorial Auctions Modelling Supporting Decision-Making Processes[END_REF], [START_REF] Šauer | Coalition Projects to Cut Back Costs of Cleaning Recreational Water Bodies: The Case of the Bohemian Lake Rozkoš[END_REF] have shown the need to deepen our research into sensitivity analysis of the resulting optimal solutions. Specifically, in terms of understanding how to study coalition structures in the space between the optimal solution and solutions in the form of individual projects, and how the change of feasible coalition structures changes achieved cost. This paper provides an approach for calculating the sensitivity and proposals for necessary adjustments of CRAB software, which makes its use for the relevant decision-making tasks more user friendly.

Models of reverse combinatorial auctions in environmental applications

Before explaining the nature of the proposed approach of sensitivity analysis, we provide the basic model of reverse combinatorial auctions. Supposed that m potential sellers S1, S2, ..., Sm offer a set R of r items, j = 1, 2, …, r, to one buyer B; a bid made by the seller Sh, h = 1, 2, …, m, would be defined as

bh = {C, ch(C)}, (1)
where C ⊆R, is a combination of items, ch(C) is the price offered by the seller Sh for the combination of items C.

The constraints ensure that the procurement provides at least one set of all items. The objective is to minimise the buyer's cost, given the bids made by the sellers.

Binary variables are introduced for the model formulation: yh(C) is a binary variable specifying whether the combination C is bought from the seller Sh(yh(C) = 1).

The basic reverse combinatorial auctions model can be formulated as follows [START_REF]Combinatorial Auctions[END_REF]:

( ) ( ) 1 h h m h c y C min C = → ∑ (2) subject to ( ) 1 1, , C R h m h y C j R = ⊆ ≥ ∀ ∈ ∑ ∑ (3) yh(C) ∊ {0,1}, ∀ C ⊆ R, ∀ h, h = 1, 2, …, m. (4)
This basic model only considers the minimisation of costs, which is complemented by restrictions on environmental standards. In terms of mathematical formulations, inequalities are added that compare the pollution reduction achieved with the required limit values for five specific environmental parameters [START_REF] Šauer | Coalition Projects to Cut Back Costs of Cleaning Recreational Water Bodies: The Case of the Bohemian Lake Rozkoš[END_REF].

( ) ( )

1 . hi h i m h C R e C y C E = ⊆ ≥ ∑ ∑ (5)
where ehi are pollution parameters of the projects and Ei are the prescribed environmental standards for the parameters.

Sensitivity analysis

For further decision-making about the investment program that is realised in practice, it is important to learn how sensitive deviations from the optimised coalition structure would be to other feasible structures.

For small examples it is possible to compute and relatively easily analyse all solutions, with coalition structures from the first best (optimal) solution ranked by increasing cost. The optimal solution is computed by solving the problems (2) -( 4). As a result, we get the so-called first-best solution. The optimal costs are denoted Z1. Generally, we get the i-th solution by solving the problems (2) -( 4) with an added constraint

1 m h= ∑ C R ⊆ ∑ ch(C)yh(C) ≥ Zi -1 + ε , ( 6
)
Where ε is a small positive number.

In typical practical cases, the number of feasible coalition structures is huge. For this reason, it is not possible to analyse all of them individually, i.e. to follow the order of the second-best, third-best, etc. solutions.

We propose that sensitivity analysis, based on analysing coalition structures for specific cost levels, can still provide support for decision-making about the projects in such cases. The difference between costs for individual project structures and costs for the first best solution could be divided to several levels corresponding to politically acceptable deviations of the practical program from the first best solution. It is possible to work with quartiles, quintiles etc. in the space of all feasible solutions.

The solutions for the cost levels could be computed from the basic model (see formulas (2), (3), and (4)) adding constraints:

1 m h= ∑ C R ⊆ ∑ ch(C)yh(C) ≥ Li , i = 1, 2, …, n, (7)
where n is number of levels and Li are cost levels.

Suggestions for CRAB software modification

We have developed our own software tool, CRAB (CombinatoRial Auction Body Software System) [START_REF] Fiala | CRAB-CombinatoRial Auction Body Software System[END_REF]. CRAB is a non-commercial software system for generating, solving, and testing combinatorial auction problems. The system solves problems using Balas' method or the primal-dual algorithm [START_REF] Balas | An Additive Algorithm for Solving Linear Programs with Zero-one Variables[END_REF]. CRAB has several advantages over CATS software [START_REF] Leyton-Brown | Towards a Universal Test Suite for Combina-torial Auction Algorithms[END_REF], in particular, CRAB generates problems faster; combinations are generated in a more predictable way and only in given subset of all items; CSV is used as the primary data format; there is fine-grained control over the generated problem; a linear problem solver is a part of CRAB; and it provides multiple out-put formats. CRAB is implemented in Ruby, which enables us to quickly experiment with different approaches.

In the first phase of analysis, all combinations of goods in each package are generated (except empty set). This step is done for every package. In the second phase, the file is transformed into the binary programming problem. The bundles correspond to variables and bids correspond to prices of the objective function that is maximised. The problem consists of automatic constraints for each good (each good can be sold only once) and each buyer (buyer cannot get over his budget). The user of CRAB software can change automatically generated constraints and add or remove additional ones. The problem can be passed to the built-in binary programming solver to find out the optimal solution for a given combinatorial auction. Afterwards, the transformed model is passed to the Balas algorithm [START_REF] Balas | An Additive Algorithm for Solving Linear Programs with Zero-one Variables[END_REF].

The CRAB architecture provides the possibility of extending the system, especially with respect to the implemented models and algorithms. For the sensitivity analyses, we modified the CRAB software according to the approaches for sensitivity analysis, ( 6) and ( 7), above.

A problem occurs when entering data for complex applications in optimisation of coalition solutions, such as in the construction of a waste water treatment plant (WWTP). This is particularly the case when appropriate variable names for multiple coalitions derive from the encoding of individual municipalities entering into these multiple coalitions. Experts generating sets of "promising" coalitions progress by identifying coalition-names on maps and not by the order of the municipalities in their list. Clarity is lost by this encoding, but this sequence has its own logic, because two coalitions comprising the same set of municipalities, but in a different order, may provide different solutions, for example, with a different location of the common WWTP. The software compares the same combination and warns the user in the report.

Currently we are working on improving user comfort when loading large data describing the real situation in the river basins and reservoirs, where there is a large number of "promising" coalitions entering the optimisation calculations. The new version should communicate better with conventional spreadsheets than is currently the case.

Sensitivity analysis by CRAB software

Imagine a situation where four municipalities discharge their wastewater into a small river that flows into the reservoir intended for bathing (e. g. may be ranked in so called Bathing Water by the Directive 2006/7/EC [10]). If we want to restore the quality of water for bathing, it is necessary that all four municipalities built waste water treatment plant (WWTP). This can be done by each building an individual WWTP or, alternatively, it is possible to try to merge the villages into so-called multiple coalitions to build a common WWTP either for all or some of them. We let the experts estimate the necessary costs for the construction of the WWTP for the "promising projects". These data are contained in Table 1. The optimal solution for the numerical example given by the CRAB software:

Table 2. Optimal solution computed by CRAB software Sensitivity analysis can be performed for the above example. The analysis is described above by the model [START_REF]Combinatorial Auctions[END_REF]. The problem has 9 solutions in our case. For the results, see Table 3.

OPTIMAL SOLUTION

Total cost: 73000.00 Coalition structure:

1-member coalition: D 3-member coalition: ABC In practical cases, there are a large number of polluters, thus creating more complex models and calculations. In such cases, there are a large amount of feasible solutions. These situations can be solved in two ways:

1. In some cases, the solution of the entire case is divided into optimisation problems of sub-segments of river basin. A typical example is in a mountainous area, where it is possible to optimise the construction of wastewater treatment plants for each valley. For this situation, see the above numerical example. 2. If this is not possible, then one can work with "levels" between the cost of first best (optimal) solution and the cost of individual projects.

As a demonstration of the second case, we provide two practical applications from recreation lakes in the Czech Republic. Bathing water quality is an important issue in the EU (see Directive 2006/7/EC concerning the management of bathing water quali-ty [10]). In both cases, multiple small municipalities should build their own WWTP or join one or more other municipalities and build a common WWTP. Solving these problems in small municipalities is quite costly in comparison to building and operating WWTPs in larger cities and requires support from public financial sources. Calculating the (theoretically) optimal solution could support political decision making about allocation of public funds in this area. In the case of cleaning phosphorus from water in a recreation lake, it is important that all polluters contribute to the project. In practice, they negotiate a common project proposal and apply for financial support.

For assessing these proposals, it is useful to have the sensitivity analysis results available. Lake Rozkoš is the first case. It is located in the Elbe River basin in Bohemia [START_REF] Pl | Limnological dindings and possibilities to improve current condition in the Lake Rozkoš[END_REF], [START_REF]PL: Control order at the waterwork Rozkoš (in Czech), Povodí Labe, s[END_REF], [START_REF] Vrv/Pl | An Analysis of Importance of Impact of Eutrophication Pollution Sources at the River Basin of Water Lake Rozkoš (in Czech), Vodohospodářský rozvoj a výstavba a.s. nad Povodí Labe[END_REF]. Two scenarios for achieving environmental targets (required status of the lake water) were formulated by specialists, together with an assessment of the investment and operating costs of the projects. The optimal solution (investment program) for 41 polluter-municipalities, where 166 coalitions were considered (41 individual WWTPs and 125 joint WWTPs), was computed. The results of the optimisation modelling presented in this paper have shown that over 20% of the costs could be saved where selected joint WWTPs are realised.

A sensitivity analysis was performed. Since the number of feasible coalition structures is huge (there are 2 166 of them in the case of Rozkoš Lake), it would not be practical to analyse all of them (as it is done in our illustration presented above). For this reason, the difference ("space") between costs for individual projects and costs for the first best (optimal) solution was initially divided into six levels corresponding to policy decisions about potential (politically acceptable) deviation of the practical program from the (theoretical) first best solution. The levels create borders of quintiles in the space of all potential (feasible) solutions. Level 1 was defined as the cost for the first best solution, level 6 as the cost for individual projects. Other levels are always about 20 percent higher than the previous level, where the second level was suggested as the politically acceptable one. These calculations provided a useful picture for better assessment of potential projects submitted in the region. For more details, see [START_REF] Šauer | Coalition Projects to Cut Back Costs of Cleaning Recreational Water Bodies: The Case of the Bohemian Lake Rozkoš[END_REF].

Lake Pastviny is the second case. This lake is located in east Bohemia, near the Polish border [START_REF]PL: Process Rules for Hydraulic Structure on the Divoká Orlice -Pastviny I[END_REF], [START_REF]VIS: Basic strategy for attaining water quality for recreational purposes at Pastviny water reservoir (in Czech), Vodohospodářsko-inženýrské služby spol. s r.o. study for Povodí Labe[END_REF]. The initial set of projects aimed at achieving the environmental standards required for bathing water in Lake Pastviny consists of 24 individual projects (WWTPs) and 131 multiple-coalition projects. These included 32 twomember coalitions, 38 three-member coalitions, 38 four-member coalitions, and 22 five-to-eight-member coalitions. The abatement costs, in the form of investment and operating costs, were assessed by the specialists for all of these projects. The analysis indicated a potential saving of annualised abatement costs of 6% in the case where half of the municipalities located in the lake watershed join specific coalitions and the rest build an individual WWTP.

In this case, the initial sensitivity analysis works with 4 costs levels. Level 1 was defined as the cost for the first best (optimal) solution, level 4 as the cost for individual projects. Other levels are always about 33 percent higher than the previous level. Moreover, here, the results provide a picture of how changing the coalition structure by decreasing of the number of multiple-member coalitions leads to an increase of the costs. For more details, see [START_REF] Šauer | Improvement to green in-country tourism conditions: A case of the Czech recreation lake Pastviny[END_REF].

Conclusion

The paper is devoted to modification of the CRAB software for sensitivity analysis of solutions to combinatorial auction problems. The modification is used for analyses of coalition projects for the building of WWTPs.

We propose two possibilities. The first approach is appropriate for small examples, where it is possible to compute all feasible solutions ordered by total cost. In such cases, it is possible to analyse changes of coalition structures in terms of their increasing cost.

The second suggested modification of the CRAB software makes it possible to analyse a high number of feasible coalition structures located between the optimal coalition (i.e. the cost-effective one) and the structure consisting of individual projects. This approach is appropriate for setting of cost levels in complex real applications, including multiple-round subsidy negotiations (see [START_REF] Šauer | Negotiation between Authority and Polluters -Model for Support of Decision Making in Environmental Policy[END_REF]). The proposed approach of sensitivity analysis can be used not only in the case of reverse combinatorial auctioning in cleaning waste waters; the waste water treatment issue was used as a typical practical application.

Two practical applications are presented in the paper, together with a discussion of their contribution to relevant decision-making processes. In both cases, it is possible to continue to more detailed sensitivity analysis, according to the concrete requirements of participants in the decision making process. This could be particularly useful when the projects are multiple-round negotiated with the authority and other stakeholders.

Table 1 .

 1 Estimated costs for the "promising projects"

	Project	Participated mu-nicipalities	Project costs
	Individ-
	ual projects
	1.	A	7500
	2.	B	18000
	3.	C	31000
	4.	D	28000
	Coalition
	projects
	1.	AB	27750
	2.	BC	41750
	5.	BD	59000
	3.	CD	65000
	4.	ABC	45000
	6.	BCD	69000
	7.	ABCD	82750

Table 3 .

 3 Sensitivity analysis computed by CRAB software

	1st Solution (=first best)
	Total cost: 73000.00
	Coalition structure:
	One 1-member coalitions: D
	One 3-members coalitions: ABC
		6th Solution
	2nd solution	Total cost: 86750.00
	Total cost: 76500.00	Coalition structure:
	Coalition structure:	1-member coalitions: C,D
	1-member coalitions: A	2-member coalitions: AB
	3-member coalitions: BCD
		7th Solution
	3rd Solution	Total cost: 90500.00
	Total cost: 77250.00	Coalition structure:
	Coalition structure:	1-member coalitions: A,B
	1-member coalitions: A,D	2-member coalitions: CD
	2-member coalitions: BC
		8th Solution
	4th Solution	Total cost: 92750.00
	Total cost: 82750.00	Coalition structure:
	Coalition structure:	2-member coalitions: AB, CD
	4-member coalitions: ABCD
		9th Solution (least
	5th Solution	efficient solution)
	Total cost: 84500.00	Total cost: 97500.00
	Coalition structure:	Coalition structure:
	1-member coalitions:	1-member coalitions: A,C
	A,B,C,D	2-member coalitions: BD

Acknowledgement. The paper was developed with the support of the Czech Science Foundation, GACR č. 16-01687S: "Novel approach to seeking cost/effective water pollution abatement: Developing reverse combinatorial auctions theory".