Mining Map Interaction Semantics in web-based Geographic Information Systems (WebGIS) for Usability Analysis

Due to the increased availability of geospatial data, web-based geographic information systems (WebGIS) have become more popular in recent years. However, the usability of these systems poses new challenges as user interactions are strongly affected by the map and are thus different from interactions with traditional user interface elements. In this paper, we propose a method for evaluating the usability of web-based geographic information systems by analyzing user intentions through map interaction patterns. We use a pattern mining algorithm to extract frequent interaction sequences from user sessions and label these with their interaction semantics that represent the users’ immediate intentions. To evaluate our approach, we conducted a user study with 60 participants in a WebGIS scenario and identified varying user strategies for a selection task based on two different geovisualizations. Our results indicate that the chosen approach can uncover the underlying intentions of users’ interaction patterns and facilitate insights into the usability of WebGIS.

Introduction
The increased availability of geospatial data, public participation initiatives, and the technical capabilities of modern web browsers have led to the proliferation of web-based geographic information systems (WebGIS) across multiple platforms (mobile and desktop) in recent years. As a result, the variety of WebGIS contents and applications has grown and includes, for example, extensive map search engines like Google Maps 1 for contemporary points of interests, fully-featured map builder and exploration tools like the ArcGIS Map Viewer 2 for businesses and organizations as well as open government initiatives for citizen participation in urban planning processes (Rall et al., 2019). Some of these systems with extensive functionality may require complex user interfaces while, for example, a visualization of search results is only built for simple purposes (Fechner et al., 2015;Lobo et al., 2015;Roth and MacEachren, 2016). Thus, users' knowledge of geospatial visualization and interactions differs greatly and the design of user interfaces (UIs) might yield diverse and potentially conflicting requirement (Roth et al., 2015b;Hoover et al., 2014;Traynor and Williams, 1995). However, all users expect good usability. As a result, designing WebGIS UIs is difficult and requires evaluation approaches that go beyond efficiency and effectiveness to evaluate the usability (Rzeszewski and Kotus, 2019;Poplin et al., 2017;Kiefer et al., 2017).
Evaluating the usability of a WebGIS is difficult, too, as the map represents a central component and is thus the target of most interactions. Compared to traditional UI elements (such as buttons, sliders, and dropdowns) interactions with the map are more strongly affected by its state. For example, the current scale of the map significantly affects users' zoom interactions for a given task. If the zoom level is badly chosen for a specific task users might need longer, are dissatisfied with their experience, or even unable to finish. Treating map interactions like any other functionality can cause problems and misunderstanding as they have a significant impact on how successful users are when accessing a WebGIS and considerably affect which UI elements are used in which order and how often. Consequently, the map state and multi-scale navigation technique affects the efficiency, effectiveness and satisfaction of users. It is, therefore, essential to thoroughly evaluate map interactions to understand these issues better and to assess the usability of WebGIS.
Companies like Google have been doing work on the usability of their web mapping products for more than 10 years (Riegelsberger and Nakhimovsky, 2008). To create interaction models that are independent of a particular interface, research in the field of cartography has evolved taxonomies and topologies that describe single actions such as search, selection, and manipulation (Crampton, 2002;Roth, 2012) in geographic maps. Recording and analyzing such actions allows for optimizations of, for example, the ratio of displayed information or recommendations of individual spatial content (Tahir et al., 2012;Aoidh et al., 2009;Weakliam et al., 2005). Despite this trend, there is only few research that analyzes the semantics of map interaction sequences and thus the usability of the used WebGIS (Roth and MacEachren, 2016;Unrau et al., 2017). Map interaction semantics are the logical aspects of the process that underlies the user's actions and thus reflect the user's immediate intentions. The interpretation of interaction patterns through semantic descriptions may facilitate the understanding of these intentions and reveal further insights into the usability of the application that would otherwise remain hidden.
In this paper, we propose an approach for identifying and analyzing map interaction semantics in geospatial tasks for usability assessment. We (a) instrument We-bGIS clients to collect map interactions, (b) apply data mining techniques to retrieve recurring patterns of action sequences from this data, and (c) create labels for the resulting map interaction semantics to (d) analyze the users' behavior for usability assessment. To evaluate our approach, we conducted a user study with 60 participants in a WebGIS scenario. While the overall goal for all participants was the same, we created two different geovisualizations and analyzed differences in the map interaction semantics. In contrast to traditional usability measures, our approach explicitly considers the semantics of map interactions and facilitates the comparison of user strategies in WebGIS workflows beyond efficiency and error rates.
Our contributions are (1) a new approach for evaluating the usability of WebGIS by comparing map interaction semantics through empirically derived interaction patterns; and (2) the usability assessment of an adapted geovisualization method for a selection task based on our approach. Although we only investigate a small set of map interactions (pan, zoom-in/-out, and select), our approach is the first step towards a usability assessment for WebGIS based on map interaction semantics.
The remainder of this paper is structured as follows: First, we review related work in the fields of multi-scale navigation as well as user session analysis and map interaction semantics. Next, we provide the motivation and rationale for our approach and describe the steps that are required to generate map interaction semantics. In section four, we evaluate the approach in a realistic user study that we conducted with 60 participants. The discussion section gives an overview of the implications and limitations of the obtained results and our approach. The paper concludes with a summary of our key findings and contributions.

Related Work
In this section, we present work that is related to We-bGIS evaluation scenarios and software instrumentation in this domain. First, we provide an introduction to multi-scale navigation. Second, we discuss existing evaluation approaches that use map interactions to analyze user behavior. Finally, we show how map interaction semantics have been defined and manually derived in previous work to detect the underlying user intentions.

Multi-scale navigation
Multi-scale navigation is a technique that is used by systems with varying uses of space, time or visual effect to allow users to attain both focused and contextual views of their information space (Cockburn et al., 2009). It was developed to address the breadth of information that often can't be conveniently displayed at one time on a single screen or view. The resulting interfaces allow users to work at multiple levels of detail. Evaluations of multi-scale navigation need to identify effective and ineffective uses of these interfaces. Therefore, terms like the level of details or the visible extent are translated into a computational model, which is used to calculate an analytic solution for optimal animations (Furnas and Bederson, 1995). These models can be tested via user experiments that include free parameters like animation speed. For example, JellyLens is a context-aware and adaptive lense technique that smoothly integrates two levels of details in one view (Pindat et al., 2012). In a controlled experiment the authors showed that this improves the visibility of content in the focus region and preserves a larger part of the context region. Similarly, PolyZoom allows multi scale and multi focus exploration of 2D spaces by building hierarchies of focus regions, stacked on each other such that each subsequent level shows a higher magnification (Javed et al., 2012). In their validation, the authors showed that this approach performed better then contemporary standard techniques. These evaluations usually include quantitative measures such as the task completion time, number of interactions, and error rate to rate the effectiveness of novel approaches.
In this paper, we aim to go beyond these numerical results and evaluate the usability of an interface by interpreting the exact interaction patterns of participants and analyzing their sessions.

User Session Analysis
In the past, large-scale analyses of map interaction data have been conducted for various reasons. For example, Aoidh et al. investigated mouse trajectories on the map element to understand the geospatial interests of users (Aoidh et al., 2009). They captured the users' mouse movements, clustered the geographic locations of the mouse cursor positions and visualized the results for exploratory analysis on a new map. Although this approach is sufficient for obtaining insights into the geospatial interests of users, it does not incorporate interactions with traditional UI elements that may provide tools for working with the geospatial data on the map. When a user moves the mouse cursor to a UI element next to the map (e.g., to toggle between various geographic layers) a gap between the following mouse cursor positions is created (Tahir et al., 2012).
Using eye-tracking for data collection is in particular interesting for applications that focus on exploratory usages, such as WebGIS which governmental authorities provide to integrate citizens into planning processes. By tracking the users' focus points and focus duration, eye-tracking has been applied for investigating map interactions (May and Gamble, 2014;Kiefer et al., 2017;Manson et al., 2012) or users' exploration of buttons and icons (Alaçam and Dalcı, 2009;Çöltekin et al., 2009) in WebGIS. However, additional hardware is required and needs to be calibrated for each user.

Map Interaction Semantics
Sequential patterns of map interactions can be extracted for interpreting the users' intentions and provide helpful information. For example, Hiramoto et al. defined operation chunks and complex chunks to query the web for information related to the users' map interactions and visible contents (Hiramoto and Sumiya, 2006). Operation chunks describe "operation sequences that carry meaning" and complex chunks "reflect the users' intentions". A hierarchy of operations (e.g., panning), operation chunks (e.g., narrowing-down) and complex chunks (e.g., comparing points) can then be used to conclude from the users' behavior. Hirose et al. extended this approach and enhanced map interfaces with an additional overview map (Hirose et al., 2007). They also provide a link between the inferred intention and the spatial content by determining the center point or a spatial area for complex chunks. Although their model represents a good baseline for aggregating single map interactions into patterns, the analysis of user intentions for usability evaluation has not been evaluated yet.
Roth developed the idea of interaction primitives for cartographic interfaces by giving an overview of existing taxonomies that focus on the stages of interaction (Roth, 2012). He investigated the usability of a WebGIS by creating relationships between interaction primitives and intentions to articulate user personas in a controlled interaction study (Roth and MacEachren, 2016). In this paper, we take the next logical step beyond prior research, reporting on a large-scale user study to learn how variations of the UI impact users' intentions for WebGIS. In particular, we will answer the question if different map-based UIs have an impact on the users' interaction patterns for a predefined task.

Approach
The overall goal of our approach is to detect common interaction patterns in WebGIS sessions and provide semantic labels which aim to describe the users' immediate intentions. We thus complement traditional metrics to evaluate the efficiency and effectiveness by explicitly capturing map-related aspects and interactions. To accomplish this task, we design and evaluate a prototypical toolkit for integration into existing WebGIS that combines tailored data collection and pattern mining techniques. The resulting map interaction semantics may facilitate the identification of usability issues and support the improvement of map UIs.
To capture the users' map interactions, we instrument the client software of a WebGIS and send logs with meta information to a central database. Next, we identify common interaction sequences by applying a wellknown pattern mining algorithm to this dataset. Finally, we manually interpret these patterns and assign semantic labels. The first part of this non-intrusive and scalable approach can be automated and is, therefore, implemented into a holistic toolkit that collects the required data and extracts map interaction patterns for analysis. In the following, we provide an overview of each step.

Software Instrumentation
Instrumenting software for usability analysis has become a common technique in HCI research (Lazar et al., 2010). The goal is to collect the required data automatically and facilitate remote user studies. Although the initial development cost might be higher, the instrumented software can be mass deployed and thus reduce the effort for experimenters. Furthermore, instrumenting software allows the conduction of user studies in the user's environment and, thereby, reduces experimenter bias and novelty effects. As modern We-bGIS use a variety of web browser technologies to provide tools for displaying, editing and analyzing geospatial data, many user interactions cannot be retrieved from server logs but must be collected from within the client (i.e., the users' web browser). To implement our approach for the evaluation, we make use of three software components.
First, we instrument the JavaScript source code of the WebGIS client by connecting user interaction events with a custom logging script. Most WebGIS rely on mapping frameworks to provide geographic maps and tools in web browsers (Roth et al., 2015a). Frequently, these frameworks already provide programming interfaces that allow developers to subscribe to user interaction events and can thus be used for our purpose. For our evaluation, we connected our logging script to the ArcGIS API for JavaScript 3 and subscribed to the following events which may be carried out via various input types (e.g., mouse click, keyboard, touch gestures): • Zoom In (I) Increasing the scale of the map to reveal more details.
• Zoom Out (O) Decreasing the scale of the map to get an overview.
• Pan (P) Moving the visible extent without changing the scale to explore the map content.
• Select (S) Selecting a map entry to reveal more details about it or adding it to a collection However, our implementation is framework agnostic and accepts any events that are configured on startup. Listing 1 shows a JavaScript code snippet that demonstrates how events of a mapping framework are connected to our logging module. This lightweight approach allows developers to easily instrument the code of other WebGIS clients as they only need to learn the interfaces for retrieving the desired information. While this process still requires access to the WebGIS source code the required effort is low. The developer does not need profound programming skills or an extensive knowledge of the WebGIS code base for carrying out this task. For our evaluation, the instrumentation of the JavaScript code for an existing WebGIS client was completed within a few hours.
Listing 1. JavaScript sample code for connecting logging module to third-party mapping framework events // import logging module import { logger } from "interaction-logging" // subscribe to changes of map's zoom level mapView.watch("zoom", (newZoom, oldZoom) => { // identify event type var evt = newZoom > oldZoom ? "in" : "out"; // log event type and properties logger.log("zoom-" + evt, newZoom); }); We used the open-source database engine Elasticsearch 4 as a central archive that runs on a central server. Elasticsearch provides a schema-less index and can thus be filled with custom data fields without adjusting the data model. These capabilities ensure that our approach is customizable and facilitates the realization of further logging scenarios in the future with little effort.
Finally, in our third software component, we extract patterns in the logged data via a python script that automatically retrieves the map interaction data from our Elasticsearch instance and extends an implementation of GSP (Prado Lima, 2019) to mine the recorded user sessions for reoccurring patterns.

Sequential Pattern Mining
WebGIS capabilities are usually limited compared to rich desktop GIS because WebGIS are accessed via web browsers and sometimes mobile devices with less computing power. For example, WebGIS do not provide extensive functionality for creating custom maps and analyzing large datasets in the client but instead consume preprocessed data and provide carefully selected tools. Therefore, most WebGIS are built with focused scenarios in mind and designers strive to identify the most usable interface for the task at hand. Nevertheless, these scenarios may consist of multiple steps that result in numerous (map) interactions and are thus difficult to interpret. The extraction of recurring interaction patterns facilitates the identification of typical user behavior which, then, must be analyzed.
We will make use of Sequential Pattern Mining for this extraction process. Sequential pattern mining is an area of Data Mining or Knowledge Discovery that scans and detects all data sequences which contain recurring patterns (Srikant and Agrawal, 1996). Developed initially to analyze customer behavior, it also serves our purpose to interpret the underlying intentions of WebGIS interactions. We adapt GSP (Generalized Sequential Pattern), an improved pattern detection algorithm that scales linearly with the number of data sequences (Agrawal and Srikant, 1995). This level-based algorithm iterates multiple times through the dataset. First, the frequency (support of a pattern) of all sequences with the length of one (n = 1) is determined. Next, non-frequent sequences are removed and the remaining sequences are used for the next iteration that determines the frequency of patterns with the length of two (n = 2). This procedure is repeated until the set of frequent items is empty for the next iteration.
A typical uses case of the GSP algorithm is the identification of shopping patterns in a web shop to infer what customers might buy next. The input sequences, in this case, are the ordered lists of previously bought items for each customer. The resulting patterns are frequent transaction sequences that could be used to display recommendations to customers. Customers who buy some other articles in between also support a pattern that does not include every of their items. Note that these transactions do not need to be consecutive. For our application of the algorithm, we use lists of interactions that represent WebGIS user sessions as input sequences.
A minimal support threshold (minsup) must be defined as an additional parameter [0,1] and determines the number of occurrences of sequences in the dataset to remain for the next iteration. The algorithm, then, returns the sequences for all iterations that fulfill this criteria and can thus be recognized as common patterns in the dataset. The minsup value is usually determined by trial and error until a value is found that reveals interesting patterns. However, the size of the dataset (x) plays an important role for the minsup value. If the dataset is small, the threshold must be set to a high value while a low value is required for large dataset. The exponential decay function (Fournier-Viger, 2010) can be used to describe a curve that represents such a behavior: The parameters a, b, and c are static values that must be adjusted to make the curve behave differently. The value of c represents the minimal minsup value (i.e. the threshold for large datasets) of the curve. The values of a and b determine the decline of the curve (i.e. the minsup values will be lower for larger datasets) and thus describe how long it will take before the minsup value converges to the value of c.

Semantic Labeling
Finally, we assign descriptive labels to the detected interaction patterns by interpreting the semantics. We distinguish between basic actions, the fundamental operations for manipulating digital maps (i.e. the recorded input events), and complex actions that are sequences of basic actions and represent more complex interaction semantics.
Complex actions are the result of our sequential pattern mining algorithm. These actions facilitate the interpretation of user intentions that are executed via multiple basic actions and, thus, reflect broader user strategies for the overall task (e.g., Relative Position Confirmation). In the following, we will denote the length of interaction patterns that underlie our complex actions as complexity. Complex actions will help us to detect if there is common user behavior, depending on the chosen threshold for recognizing patterns and the frequency of identified patterns.

Evaluation
To evaluate our approach, we conducted a user study and extracted interaction patterns for a localization tasks. Two groups of participants were provided with different multi-scale navigation techniques. The first group was equipped with a novel technique that made use off-screen indicators (OSI) (Gustafson et al., 2008;Ballatore, 2019). These OSI consists of triangles whose sides can be traced and extrapolated to locate the off-screen object (i.e. map features that are outside the currently visible view) (Baudisch and Rosenholtz, 2003). By tracking the relative position of these objects continuously users are able to estimate where the triangle's sides intersect and navigate precisely to the desired entry ( Figure 1). Additionally, an alphabetical coding could be used by this group to match the features on the map to the corresponding row in the table below. The coding was displayed next to the OSI on the map and as an attribute in the table rows to facilitate the assignment of both representations. The second group used a traditional geovisualization technique for dynamic maps that simply highlights the map features with a point symbol and does not indicate if and where additional features might be located outside of the current map view. This group also had to mentally match the table rows to the features on the map by either hovering the one of them which highlighted the correspondent feature or row (Figure 2). We randomly assigned participants to one of the two groups in a between-group user study.
Participants: We opportunistically recruited 60 participants during a user conference of the tested WebGIS to participate in the study using our optimized OSI version. The primary criteria for participation in our study included basic knowledge and experience with WebGIS (i.e., participants were actual end-users). The resulting sample set of participants consisted of regular users with high levels of motivation and WebGIS expertise. Our sample size of n = 60 for two different scenarios is sufficient to achieve a high level of thoroughness based on recommendations for usability testing (Nielsen and Landauer, 1993).

Material and Procedure:
We conducted the study during the mentioned conference in a quiet area at the conference venue. As the data collection was performed automatically, our simple usability setup consisted of a laptop computer, an external monitor, and a mouse that were used by the participants during testing. We completed all sessions over two days, with our setup remaining in the same configuration throughout the period.  The second group was equipped with a common geovisualization that display map entries as simple dots on the map. The connection between map and table entries is not initially available, and users must hover or select table entries to mentally establish the connection.
Similar to the idea of a usability kiosk (Nielsen, 1993), we invited passing-by persons to participate in a 10minute user study that investigated an experimental design for visualizing the relationship between data in a table and on the map. First, participants sat down in front of our setup that guided users through the required steps and automatically assigned them to one of our two groups. Next, we asked participants to rate their experience with GIS on a Likert scale based on the following statement: I have experience in working with GIS (1: strongly disagree, 5: strongly agree). Before starting with the study, participants also had to confirm an informed consent form about the anonymously collected data. Without any initial exploration period, every participant was tasked to select property entries on the map that had a rectangular shape and an area bigger than a 5km 2 . Attributes of the map entries, such as the area, were displayed in the table below the map. By using the checkbox in one of the table rows, the corresponding entry was added to or removed from the set of selected entries. This task layout was created to require participants to interact with the map as well as with the table. We chose the initial extent of the map view not to show all entries and, thus, required participants to interact with the map element via pan or zoom actions. During the study, participants were allowed to ask questions for clarification, and all sessions were finished with a set of properties that fulfilled the given criteria.

Results
In total, we collected 1248 map interactions from 60 user sessions (44 male, 16 female). Both geovisualization types were used by two groups of 30 participants each and an overall mean age of 38.3 (σ = 10.13) and a self-rated GIS experience of 4.6 (σ = 0.95, Likert scale: 1 to 5). An independent-samples t-test was conducted to compare the task completion times. There was no significant differences in the times with OSI (M = 89.3 seconds, SD = 41.7) and without OSI (M = 92.2, SD = 86) conditions; t(54) = 0.2658, p = .7914. About 60% of the users in the scenario with OSI selected all property entries that fulfilled the required criteria. In the scenario without OSI, the success rate was 73%. In both scenarios, properties that did not fulfill the required criteria were selected by 6 or less participants. We performed a chi-square test of independence to examine the relation between the geovisualization and the count of basic actions. The relation between these variables was significant, X2 (3, N = 60) = 7.94, p = .47. Users with OSI were more likely to perform basic actions.
For mining complex interaction in our dataset, we determined a threshold of 30%, meaning that at least 30% of the groups' participants (i.e., user sessions) must have performed a particular sequence to be recognized as a pattern. This minsup value was established via the exponential decay function (final parameters: x = 1248 a = −0.0017, b = −0.2, and c = 0.2). The pattern mining algorithm detected 11 complex actions which were interpreted through the following map interaction semantics: • Detail Verification (I-O): Zooming in to inspect details of the entry or its surroundings before zooming out again to establish the previous scale.
• Detail Selection (I-S): Zooming in to inspect details and select an entry.
• Inspection (I-P): Zooming in and panning the map to investigate details in a particular area.

• Relative Position Confirmation (O-I):
Zooming out to localize the current position based on the surroundings before zooming in again to establish the previous scale.
• Spread-Out Search (P-O or O-P): Searching for further entries by increasing the visible area through panning the map and zooming out to move on to a different location (faster).
• Narrow-Down Search (P-I): Searching the map by panning around before zooming in to a particular area.
• Browse Selection (P-S): Scanning entries by panning the map before selecting an entry.
• Scale Choice (I-S-P): Reducing the scale to select an entry and panning the map to search for the next entry of interest. As the user keeps the reduced scale after the selection, this semantic also determines a selection of a new scale by the user for his search process.

• Surroundings Inspection (S-O-I):
Confirming the own position after selecting an entry to get an overview of remaining entries and their relative position.
• Spread-Out Selection (O-P-S): Zooming out to move to a different selection faster and selects an item here.

• Supervised Selection ([S-]P-S[-P]):
Keeping the same scale and continuously selecting entries by panning the map to get to items outside of the visible extent. This semantic manifests in multiple similar interaction patterns that are either subsets or vary in the starting interaction before alternating between Pan and Select.
In contrast to the basic interactions, the side-by-side comparison of these complex actions reveals significant differences between participants in the group with OSI and those without OSI (see Figure 3). While we found ten different semantic interaction patterns in the group of participants with OSI, participants without OSI executed only four different patterns (see Table  1). As the total interaction count is similar for both groups, the small set of map interaction semantics for the group without OSI (as well as the often lower execution count for the remaining semantics) indicates a lack of a common strategy for these participants. Instead, we expect a variety of individual patterns below our chosen threshold for this group.
Browse Selection represents the most often detected map interaction semantic for both groups (see Table  1) and could describe the participants' aim to scan the map with the same scale while selecting entries. However, participants that were provided with OSI show a higher proportion for this semantic. Despite the variety of map interaction semantics for the group with OSI, Supervised Selection stands out in our data. This complex action is the result of multiple and similar underlying interaction patterns while also being the only one with a complexity higher than two and an average execution per user above one (P,S,P: 31 executions for 30 participants). Thus, the simple alternation of Pan and Select seems to be a characteristic behavior of participants for this scenario. It seems plausible that Supervised Selection is a result of the optimized indicators which direct users to map entries outside of the visible map extent without having to zoom out.
The algorithm detected four additional complex actions, but we could not assign any meaningful map interaction semantic (see Table 2). However, these patterns seem to be exceptions that can be explained in the context they were executed. The S,P pattern is a subset of the more complex Supervised Selection and did not pass the threshold for the group without OSI, for the described reasons. The remaining three patterns without a semantic description could indicate that users carried out their goal to select an entry and begin with a new semantic interaction.

Discussion
To provide a positive experience for users of a We-bGIS, it is essential to assess the usability of these systems. Prior work has analyzed the usage of We-bGIS to learn about users' interaction with geospatial data and inform the design of UIs. Roth, for example, compared the performance and used map operators via interaction logs to identify user personas (Roth and MacEachren, 2016). Our findings confirm that map interactions can be used to interpret the users' immediate intentions which are essential for detecting flaws in the UI. This study, therefore, indicates that the steps for retrieving the required data could be carried out by a holistic toolkit that supports UI designers in the decision-making process.
By applying our new approach, presented in this paper, and comparing map interaction semantics through empirically derived interaction patterns we were able to identify that the majority of participants equipped with OSI approached the given localization task with the same interaction strategy. By making use of Supervised Selections these users could stay on a map scale that allowed them to verify details on the map that were required for the given task while also being able to pan to the next map entry. In contrast, traditional usability measures, like task completion times, could not indicate significant differences between both groups. We can attribute this to the novelty of OSI for most users that might not result in increased performance initially but requires some learning first. However, our approach can help usability experts to gain deeper insights into user strategies from remotely logged map interaction data and provide indicators that show if UI changes result in changed user behavior.
Our results also indicate open usability issues with the WebGIS that was evaluated. While OSI users were able to make use of the provided indicators the extracted patterns reveal that some of these users performed Relative Position Confirmations. While OSI should support users in navigating to map entries without having to zoom out it seems like these participants still wanted to keep track of their position on the map. Thus adding an overview map to our UI could enhance the usability of the evaluated WebGIS.
In addition, we found that some OSI participants (9 out of 30) performed exactly one Scale choice in their session. This could be an indicator for a poorly chosen initial scale that requires users to zoom in at the beginning of their session before they can benefit from the OSI and focus on the task at hand. Usability designers can use findings like this one to further analyze the logged interaction data to confirm this hypothesis and adjust the initial scale of the evaluated WebGIS.
Although zooming and panning represent the most critical map interactions in WebGIS scenarios, our evaluation covered only a small subset of possible map interactions and a single selection task. Frequently, modern WebGIS provide tools for spatial selections or drawing notes which may lead to more complex interaction patterns. However, as WebGIS are designed to cover only a limited number of workflows, the interpretation of these patterns should be feasible if the aim of the user is known to the analyst.
Regarding our approach, further work is needed to evaluate the correctness of our map interaction semantics. In this study, the assumptions about the underlying intentions were not validated by, for example, conducting follow-up interviews with the participants. While the quantitative results of our study indicate that many users with OSI followed a common strategy, it remains unclear if, for example, the intention of I,O was always Detail Verification. However, the design of our focused task, as well as the detected patterns, do not leave room for arbitrary interpretations in this context. Future work should investigate more complex scenarios and validate the resulting map interaction semantics by consulting the study's participants.
Further limitations of our evaluation are the type of our study participants as well as the complexity of the tested geovisualizations. The overall self-rated GIS experience of our users was very high and the chosen approach for recruiting participants on a conference certainly contributes to a homogeneous cohort. Last, the tested scenarios represent simple tasks compared to modern WebGIS that offer numerous tools and data sources. However, our work can be considered a first step in to the investigation of the benefits of interaction semantics for this domain. Instrumenting We-bGIS for automatic data collection and pattern extraction also simplifies the conduction of future studies in more complex environments and with heterogeneous users.
Furthermore, it would be interesting to investigate the temporal and spatial correlation of interaction patterns within user sessions. Finding out whether users with the same immediate intentions carried out the corresponding interaction patterns at the same geographic location on the map or at the same point in time relative to their session start could reveal further insights and help to differentiate groups of users with the same strategy further. Therefore, future work could visualize this data as a map layer that can be explored by usability analysts to detect spatial and temporal patterns.

Conclusion
The evaluation of map interaction patterns is critical for usability assessment in web-based geographic information systems because they differ from interactions with traditional UI elements. Recent trends, such as the Internet of Things, increase the dissemination of geospatial data and the need for appropriate mediums to display and manipulate location information in their context. Dynamic maps as a medium can handle these vast amounts of data and are increasingly accessed by non-expert users via the World Wide Web.
In this paper, we present an approach and toolkit for detecting, describing and comparing map interactions in WebGIS sessions for usability analysis. Map interaction semantics describe the users' immediate intentions while interacting with the WebGIS and, thus, increase insights into user behavior compared to analyzing isolated interactions. To extract these intentions from users' sessions, we mined all user interactions for common patterns as they usually manifest in sequences of interactions. Because the data was collected automatically via an instrumented WebGIS software, our approach facilitates the extraction of map interaction patterns without an experimenter on site or additional hardware, such as eye-tracking devices.
We conducted a kiosk study to investigate the feasibility and potential of our approach. Overall, the result provides evidence that the chosen geovisualiza-tion affects the users' immediate intentions for the same task. We showed that off-screen indicators encourage specific user approaches and result in common user strategies, whereas the lack of these indicators results in a variety of individual approaches. Our method, therefore, can be used to compare the influence of UI changes on the users' intentions and assist decision makers in usability evaluations. Our key contributions are a new approach for evaluating the usability of web-based geographic information systems by comparing map interaction semantics through empirically derived interaction patterns; and the usability assessment of an adapted geovisualization method for a selection task based on our approach. In the future, we will extend our toolkit to visualize the results and thus provide more spatial and temporal context to analysts, and we will assess the usefulness of our approach for more complex scenarios.

Data and Software Availability
The computational environment was provided by using a virtual machine (OS: Windows 10) with an Elasticsearch cluster (version 2.1). For collecting user interactions during our study and retrieving this data for the analysis, the virtual machines were accessed via a local network. As the used open source version of Elasticsearch does not provide any security layer, it is not possible to share any connection details to our datasets. To mine the retrieved data for pattern a publicly available Python implementation of GSP was used (https://doi.org/10.5281/zenodo.3333988).


extfieldsofstudy:
Computer Science
Engineering
Mathematics

text:
MEC-Empowered Non-Terrestrial Network for 6G Wide-Area Time-Sensitive Internet of Things

In the upcoming sixth-generation (6G) era, the demand for constructing a wide-area time-sensitive Internet of Things (IoT) keeps increasing. As conventional cellular technologies are hard to be directly used for wide-area time-sensitive IoT, it is beneficial to use non-terrestrial infrastructures including satellites and unmanned aerial vehicles (UAVs), where a non-terrestrial network (NTN) can be built under the cell-free architecture. Driven by the time-sensitive requirements and uneven distribution of IoT devices, the NTN is required to be empowered by mobile edge computing (MEC) while providing oasis-oriented on-demand coverage for the devices. Nevertheless, communication and MEC systems are coupled with each other under the influence of complex propagation environment in the MEC-empowered NTN, which makes it hard to orchestrate the resources. In this paper, we propose a process-oriented framework to design the communication and MEC systems in a time-division manner. Under this framework, the large-scale channel state information (CSI) is used to characterize the complex propagation environment with an affordable cost, where a non-convex latency minimization problem is formulated. After that, the approximated problem is given and it can be decomposed into subproblems. These subproblems are further solved in an iterative way. Simulation results demonstrate the superiority of the proposed process-oriented scheme over other algorithms. These results also indicate that the payload deployments of UAVs should be appropriately predesigned to improve the efficiency of resource use. Furthermore, the results imply that it is advantageous to integrate NTN with MEC for wide-area time-sensitive IoT.

I. INTRODUCTION
In future sixth-generation (6G) networks, the concentration of cutting-edge technologies will change from humans to intelligent machines [1]. Different from human beings, these machines are usually unevenly distributed in remote C. Liu In view of previous works, it is advantageous to jointly use satellites and UAVs with MEC for wide-area timesensitive IoT [8], [30], [31]. Liu et al. presented a task-oriented intelligent architecture for IoT-oriented space-aerialground-aqua integrated networks in [30]. Cheng et al. investigated the joint design of computing resource allocation and task offloading strategy for IoT-oriented space-aerial-ground integrated networks in [8], where stringent latency constraints were regarded and a learning-based approach was proposed. Cao et al. discussed the coupling of trajectory design and task offloading strategy in an integrated satellite-UAV network under wind influence in [31]. Despite all of these achievements, when an NTN is integrated with MEC under the cell-free architecture, it will encounter new challenges. First, due to the complex propagation environment, channel state information (CSI) is hard to be perfectly acquired by the NTN, which indicates that it is complicated to provide oasis-oriented on-demand coverage for machines under the cell-free architecture. Furthermore, it is challenging to orchestrate the resources in the MECempowered NTN because communication and MEC systems are coupled with each other. In our previous works [6], we discussed the cell-free coverage patterns of integrated satellite-UAV networks. In this work, we go a step further to investigate the design of an MEC-empowered NTN for wide-area time-sensitive IoT. The relationships between existing technologies and the specific research area that we focus on is summarized in Table I.

B. Main Contributions
In this paper, the design of an MEC-empowered NTN is studied for wide-area time-sensitive IoT. Particularly, we focus on the design of NTN, which consists of hierarchically integrated satellite and UAVs, while considering the overall communication and computing latency as the metric of latency performance. To satisfy the service Wide-area IoT NB-IoT [9] Cellular-based Large latency allowed LoRa [10] Expanded cellular Satellite-based IoT [21]- [23] Ubiquitous TSN WIA-FA [12] Indoor Sensitive to latency WirelessHP [13] 3GPP 5G URLLC [14] Cellular-based 3GPP Industrial IoT [15] Wide-area time -sensitive IoT MEC-empowered NTN Oasis-oriented under a cell-free architecture requirements of wide-area time-sensitive IoT, the MEC-empowered NTN is designed under a process-oriented framework in a time-division manner [6], where a latency minimization problem is formulated using the large-scale CSI. Then, a process-oriented joint resource orchestration scheme is proposed to solve the latency minimization problem. Concretely, the main contributions of this paper are summarized as follows.
• A process-oriented framework is presented for the MEC-empowered NTN. This framework can jointly design the communication and MEC systems in a time-division manner for hierarchically integrated satellite and UAVs.
After that, an overall communication and computing latency minimization problem is formulated, where the large-scale CSI is used to characterize the complex propagation environment with an affordable cost.
• As the latency minimization problem is a non-convex stochastic optimization problem, we propose an approximation of this problem. The approximated problem can be further decomposed into subproblems according to the properties of the overall communication and computing efficiency function.
• To provide solutions to the subproblems, we propose a joint power allocation and data stream scheduling scheme, where block coordinate descent and successive convex approximation techniques are applied. Furthermore, the process-oriented joint resource orchestration scheme is derived in an iterative way.
The rest of this paper is organized as follows. We introduce the system model and process-oriented framework in Section II. In Section III, we investigate the solution to the overall communication and computing latency minimization problem, where a joint power allocation and data stream scheduling scheme is proposed. Simulation results and discussions are presented in Section IV, while the conclusions of this paper are drawn in Section V.

II. SYSTEM MODEL
We consider an MEC-empowered NTN with hierarchically integrated satellite and UAVs as shown in Fig. 1, where there are U single-antenna IoT devices, K UAVs in a swarm where each UAV is equipped with an MEC server and M antennas, and a satellite that can transmit data back to the cloud server via a gateway. We assume that the UAVs are flying around IoT devices following a predetermined circular trajectory, which can save energy with guaranteed stability [32]. To accommodate the distribution of devices in wide-area time-sensitive IoT, the  hierarchical NTN is designed under a cell-free architecture [6], where an oasis-oriented coverage pattern can be observed. Based on such coverage pattern, the associations between the devices and UAVs can be predetermined.
For the convenience of mathematical analysis, the indicator set of user association is denoted as z = {z u,k }, where z u,k = 1 means that the u-th device is associated with the k-th UAV.
In practical systems, the computing ability of each IoT device is usually weak, so the devices must upload data to the satellite or UAVs to accomplish computation-intensive but time-sensitive tasks [8]. After the cloud server successfully receives all the data from the devices, the communication and computing process is finished [33], [34].
The u-th device is assumed to have D u data to upload. To cope with the influence of UAV movement on data transmission, the communication and computing process is designed under a process-oriented framework, which can reduce the complexity of optimizing the whole process [6]. As illustrated in Fig. 2, the whole process is divided into N T segmentations. At the beginning of a segmentation, parameters of the MEC-empowered NTN are updated, and these parameters are assumed to be constant during each segmentation and may vary with each other in different segmentations. Denoting the update interval of system parameters as δ T , the overall communication and computing latency can be expressed as T total = N T δ T + a , where a denotes the total propagation time of the electromagnetic wave. More specifically, in the t-th segmentation, the u-th IoT device can send a ratio of η L t data directly to satellite, a ratio of η S u,t data to satellite via device-UAV and UAV-satellite links, and a ratio of η C u,t data via device-UAV links into on-board MEC servers for computing. Thus, we have as practical constraints of these ratios. Particularly, after the data are computed by MEC server, the results of computing are transmitted from MEC servers to satellite via UAV-satellite links. For the convenience of mathematical analysis, we assume that the size of the output data is proportional to that of input data for MEC servers [35], [36], where the proportion of the data from the u-th device is denoted as ζ u .
In each segmentation of the process, the data from IoT devices are transmitted to the satellite or UAVs at first.
Under the cell-free architecture, all devices are assumed to share the same frequency band [6], where the bandwidth is denoted as B. When an IoT device is directly connected with the satellite, we assume that the UL rate between the device and satellite is a constant [37], which is R L . Moreover, when IoT devices are connected with UAVs, they consist of a multi-user multiple-input-multiple-output (MU-MIMO) UL system for data transmission. Therefore, the received symbol of the u-th user from the k-th UAV in the t-th segmentation is formulated as where x u,t is the transmitted symbol, n u,k,t denotes the additive white Gaussian noise which satisfies n u,k,t ∼ N (0, σ 2 I M ), h u,k,t is the channel vector, which is written as h u,k,t = s u,k,t l u,k a u,k .
In (4), s u,k,t denotes the fast-varying small-scale parameters with identical distribution, whose phase is uniformly distributed in [0, 2π], while amplitude obeys Nakagami-m distribution, where the probability density function is In (5), m and Ω are parameters of Nakagami-m distribution, Γ(m) denotes the Gamma function with respect to m.
These small-scale parameters are assumed to be independent with each other for different u, k and t [38]. Besides, l u,k is the slowly-varying path loss of UAV channel, which is expressed as follows [32]: where A 0 = η LOS − η NLOS , B 0 = 20 log 10 (d u,k ) + 20 log 10 (4πf /c) + η NLOS , f is the carrier frequency, c denotes the speed of light, η LOS , η NLOS , a and b are constants related to propagation environment, d u,k denotes the distance between the device and UAV, θ u,k = 180 π arcsin( h k d u,k ) represents the azimuth angle of the device-UAV link, h k is the height of k-th UAV. Moreover, a u,k ∈ C M ×1 denotes the array manifold vector of receive antenna array. We assume that uniform linear array (ULA) can be carried on UAVs, so that we have the following expressions [39]: where d 0 is the distance between adjacent antennas. In this MU-MIMO system, the process of data transmission from devices to UAVs is designed prior to UAV take-off, and this has a much larger time scale than the channel coherence time. Therefore, using pilot symbols, the UL CSI in (4) can be accurately estimated by UAVs within the channel coherence time, but such CSI cannot be perfectly acquired prior to UAV take-off with respect to the large time scale of the whole process. As a result, perfect CSI is difficult to use for designing the data transmission process. Specifically, we regard the position-related parameters, i.e., l u,k and a u,k as slowly varying large-scale channel parameters, which can be perfectly acquired using radio maps in practical systems [4]. These parameters are assumed to be constant during the whole process. In contrast, s u,k,t varies rapidly due to the movement of UAVs, and only its distribution is known. Under these assumptions, the efficiency of data transmission in each segmentation of the process can be evaluated by the ergodic rate [6]. In addition, it is reasonable to assume that minimum mean square error (MMSE) detection is used at the receiver [33], where the detection vector for the u-th device at the k-th UAV in the t-th segmentation is denoted as w u,k,t [40]. As a result, the UL ergodic rate of the u-th device at the k-th UAV in the t-th segmentation can be formulated as follows [41]: where γ UL denotes the fraction of transmitted signals that are used as reference signals, which which means that R U u,k,t (P) can be regarded as the achievable net rate [42], P = (p u,t ) ∈ R U ×N T denotes power matrix, p u,t = E{x H u,t x u,t } is signal power. After the UAVs receive the data streams from IoT devices, these streams are further scheduled for communication and computing. To guarantee the stability, the system is assumed to work in a non-blocking mode [35],where any packet of data in the data stream can be transmitted from devices to the cloud server without any waiting time.
Therefore, the constraints of the data streams are derived as follows [35]: where R C k denotes the average throughput of MEC server, R S k is the data rate of UAV-satellite link, both of them are parameters of the k-th UAV. Furthermore, for the u-th device in the t-th segmentation, the average overall communication and computing efficiency is expressed as follows: • If only the satellite is used for communication, we have R a u,t = R L (12) • If the MEC server on UAV is not used for computing, we have • If the MEC server on UAV is used for computing, we have where 0 is the transmission time of a data packet. In (12)-(14), R a u,t has different values in different cases. The reason for this phenomenon is that in practical systems, data are transmitted from devices to satellite and UAVs in sequential packets. To keep the system stable, update interval should be longer than the packet transmission time.
As indicated by Fig. 2, it requires at least 2 0 packet transmission time to send data to satellite via device-UAV links and UAV-satellite links, while at least 3 0 packet transmission time is consumed to send data to satellite via device-UAV links, MEC servers and UAV-satellite links. Thus, UAVs and MEC servers can only be used when the update interval is sufficiently large, which makes R a u,t become a piecewise function. On the basis of (1)- (14), the overall communication and computing latency minimization problem under a process-oriented framework can be formulated as where N T is predetermined and δ T is optimized to find the minimum overall latency, (15b) can guarantee that the service requirements of all IoT devices are satisfied, (15c) and (15d) are rate constraints of data streams, (15e) denotes the power constraints of the devices where P max is the maximum transmit power, (15f) represents the practical constraints of data stream scheduling and (15g) shows the range of variables.

A. Problem Decomposition
Observing (15b)-(15d), we can find that (15) is a non-convex stochastic optimization problem, which is difficult to solve directly using existing tools. To further simplify (15), an approximation of R U u,k,t (P) is given as follows [41], [43] where According to (16) and (17), θ = {θ u,v,k ∀u, v, k} is calculated prior to resource orchestration, which can be regarded as deterministic parameters, indicating that the expectation operator in (16) could be eliminated. With randomly generated channel vectors and transmit power, it is demonstrated in Fig. 3 that the proposed approximation is accurate, while a justification of such approximation is given in Appendix A.
Based on (16) and (17), R U u,k,t (P) in (15b)-(15d) can be replaced byR U u,k,t (P). Then, (15) is further decomposed into three subproblems regarding the segmentation of R a u,t , which are illustrated as follows.
It is not difficult to certify that the subproblems in (18)- (20) are independent with each other. For the simplification of notations, if we have (P, η) as the solution to (18), (19) or (20), the corresponding objective function is expressed as δ T (P, η). Then, we discuss the solutions to these subproblems respectively.
B. The Solution to (18) According to the constraints in (18), we can find that (18c)-(18g) have no influence on the objective function in (18a). Therefore, (18) can be equivalently transformed to whose solution can be directly given by and the minimum update interval of process becomes Remark 1: The solution to (18) provides the joint resource orchestration scheme when we only use the satellite to transmit data. Intuitively, we point out that the minimum communication and computing latency is achieved by this strategy when D u is sufficiently small. The reason is that the communication and computing latency may be less than 2 0 if we only use the satellite for data transmission, but the latency is at least 2 0 if UAVs are used, as shown in (18h), (19h) and (20h). Such intuition can be further certified by simulation results.
C. The Solution to (19) Due to the coupling of P and η in (19b)-(19d), (19) is non-convex and hard to be solved directly. To handle this problem, we decompose (19) into two subproblems following the block coordinate descent technique [6], which are formulated as where i is denoted as iteration index, (24) is the power allocation subproblem and (25) denotes the data stream scheduling subproblem. After these, we discuss the solutions to (24) and (25) respectively.
1) The solution to (24): At first, the properties ofR U u,k,t (P) should be clarified in order to give the solution to (24).
Theorem 1:R U u,k,t (P) is concave with respect to p u,t and convex with respect to {p v,t ∀v = u}. Accordingly, at any given point P 0 , we havê where Proof: See Appendix B.
Theorem 2: The problem in (31) is convex, whose optimal solution is a feasible solution to (24).
Proof: See Appendix C.
Theorem 2 shows that (31) can be solved using conventional convex optimization tools [45], which also indicates that the solution to (24) can be derived by using the solution to (31) in an iterative way. Detailed steps of this method are recorded in Algorithm 1.
2) The solution to (25): The problem in (25) is non-convex, because (25b) is concave with respect to η i . Further by using successive convex approximation technique [44], denoting the iteration index as j, (25) is reformulated as follows.
Property 1: The optimal solution to (34) is a feasible solution to (25).
Proof: See Appendix D.
On the basis of Property 1, the solution to (25) can be iteratively derived based on the solution to (34), which is recorded in Algorithm 2.
After the problems in (24) and (25) are solved, the solution to (19) can be iteratively derived by jointly using Algorithm 1 and Algorithm 2, according to block coordinate descent technique [6]. Detailed steps of the proposed joint resource orchestration scheme are summarized in Algorithm 3.

D. The Solution to (20)
Comparing (20b) with (19b), we can give the following property.

Property 2:
The optimal solution to (20) must satisfy η C u,t = 0 for ∀u, t.

E. Convergence Analysis
In this section, we analyze the convergence of Algorithm 1-3. For the problem in (31) during the j-th iteration step, we have because both P i,j and P i,j−1 are feasible solutions to (31) according to Theorem 1, and the minimum value of δ T is achieved by P i,j . Thus, Algorithm 1 is guaranteed to converge according to (36), where we can derive P i, * as the locally optimal solution which satisfies Similarly, for the problem in (34) at the j-th iteration step, we have based on Property 1, which indicates that Algorithm 2 is also guaranteed to converge. Therefore, we have η i, * as the locally optimal solution which satisfies According to (36)-(39), we can conclude that which shows that the objective function in (19a) keeps decreasing when i goes larger. Due to the constraints in (19b)-(19h), the objective function must have lower bound. As a result, the convergence of Algorithm 3 is proved, and the locally optimal solution to (19) can be derived.  [46], where the degree of user aggregation is set as β = 0.5. The minimum distance between UAVs is set as d UAV = 30 km, and the height of UAV swarm is set as h k = 3 km ∀k. We assume that the data sizes of all IoT devices are the same, and this size is denoted as D u = D where we set D = 1 Gbits ∀u, and the maximum transmit power of each IoT device is set as P max = 2 W [47]. For the satellite system, the data rate of device-satellite link is set as R L = 9.6 kbits/s [37], the maximum rate of UAV-satellite link is set as R S k = 2 Mbits/s ∀k [48], and the overall propagation time of electromagnetic wave is set as a = 240 ms [49]. For UAV channel parameters, we set m = 4.02, Ω = 25 × 10 −3 , η LOS = 0.1, η NLOS = 21, f = 5.8 GHz, c = 3 × 10 8 m/s, λ = c/f , d 0 = λ/2, a = 5.0188 and b = 0.3511 [32], [38]. For the integrated communication and MEC system, we set ζ u = 0.01 ∀u [41] and 0 = 500 ms [49] 1 . First, we evaluate the convergence performance of the proposed algorithms by numerical simulations, where we set R C k = 10 Mbits/s ∀k [34], and N T is randomly generated in each snapshot. As shown in Fig. 4, we can find that Algorithm 1 converges after approximately 5 iterations, while Algorithm 2 only needs 2 iterations to converge, showing that the data stream scheduling subproblem is nearly a convex problem. In addition, because Algorithm 3 requires higher precision than the other algorithms, more iterations are needed to converge. These results indicate that the proposed process-oriented scheme has much potential for use in practical systems.  Then, we compare the proposed algorithm with other schemes. A simple scheme is considered first, where we only use the satellite for communication. Furthermore, the following three schemes are also considered.
• Scheme 1: We allocate the total bandwidth among multiple devices using the bandwidth allocation method proposed in [33], where the maximum transmission power is used, while a greedy data stream scheduling strategy is applied according to [8].
• Scheme 2: The transmission power of each IoT device is set to be equal [6], where power backoff is used to satisfy the constraints of the data stream, while a greedy data stream scheduling strategy is applied according to [8].
• Scheme 3: A simplified version of the proposed algorithm is used, where we assume that N s1 T = N s2 T = N s3 T = 1 always holds.
In this simulation, we set R C k = 6 Mbits/s ∀k, and different algorithms are evaluated when the data sizes are varying. Observing Fig. 5 and Fig. 6, we can find that the proposed algorithm has the best performance in comparison with other algorithms, but the performance gain varies with different data sizes. As illustrated in Fig. 5, when D is less than 1 Mbits, the proposed algorithm has a similar performance to that of Scheme 3 because the communication and computing process can be accomplished in one segmentation of the process when the data size is small. In addition, a piecewise communication and computing latency pattern can be observed when the proposed algorithm is used because the design of the proposed scheme can adapt to varying data sizes. This phenomenon demonstrates the advantages of jointly designing power allocation and data stream scheduling schemes. Furthermore, the curves in Fig. 6 demonstrate that an approximately 30 percent performance gain is achieved by the proposed algorithm compared with Scheme 3, because N T and δ T can be appropriately designed using Algorithm 1-4. To further clarify the insights of the proposed scheme, some typical values of communication and computing latency are demonstrated in Table II, where the data sizes and update intervals are varying. The minimum communication and computing latencies with different data sizes are marked in bold type, and these demonstrate the phenomenon described in Remark 1 and Remark 2. It can also prove that the proposed scheme has the ability to adapt to different data sizes. From these results, we can conclude that it is beneficial to use the proposed process-oriented scheme in a hierarchical NTN with MEC.
In Fig. 7, we evaluate the minimum overall latency derived by the proposed algorithms when the process is designed with different numbers of segmentations, where we set R C k = 6 Mbits/s ∀k and N s1 T = N s2 T = N s3 T = N T as the segmentation number. On one hand, we can observe that the latency performance can be improved by dividing the process into more segmentations. On the other hand, the computational complexity is also increased with more segmentations, but the performance gain that we can acquire become less. These results indicate that the value of  segmentation number should be appropriately selected in order to balance the computational complexity and the performance of the proposed algorithms.
In Fig. 8, we investigate the influence of UAV payload on the latency performance of the proposed algorithm, where the average throughputs of MEC servers and the data rates of UAV-satellite links are varying. In this simulation, we set R S k = R S and R C k = R C ∀k. As illustrated in Fig. 8, the overall communication and computing latency is kept constant with respect to R C when R C is smaller than R S because of the fact that most data would be scheduled to be sent back to the satellite through UAV-satellite links. Besides, we can also observe that the latency cannot be infinitely reduced by increasing R C because the limited data rates of device-UAV links may become the bottleneck in this case. These phenomena imply that the payload deployment of UAVs should be appropriately designed prior to the communication and computing process, as this could improve the efficiency of resource consumption regarding communications and MEC in a hierarchical NTN.
In Fig. 9, we discuss the influence of user distribution on latency performance, where varying average throughputs of MEC servers are regarded. We set R C k = R C ∀k in the simulation. From the curves, we can observe that decreased latencies can be achieved when β increases because the proposed process-oriented scheme can reduce the interference between neighboring devices to some extent due to the fact that the diversity in time is fully used under the process-oriented framework. Specifically, when β ≥ 0.7 and R C = 2 Mbits/s, changing the degree of aggregation will not influence the latency performance, because limited throughput of MEC is the bottleneck for latency in this case. Moreover, it can be found that the gaps between curves decrease when R C continues to increase, and this can be illustrated by the phenomena shown in Fig. 8.
Furthermore, we evaluate the change of latency performance when different numbers of IoT devices are served in Fig. 10. In the simulation, we set R C k = 6 Mbits/s ∀k and M = 16. It is observed that the overall latency is larger when more IoT devices are served, because the resources of communication and MEC are more limited for more devices. Moreover, we can observe that the degree of aggregation has more influence on the latency performance with larger numbers of devices, for the reason that the interferences between IoT devices have more chances to be increased. These results indicate that the latency performance of MEC-empowered NTN is sensitive to user distribution, especially when the number of IoT devices is large in this network.
Furthermore, we investigate the relationship between UAV positions and latency performance in Fig. 11, where we   set R C k = 10 Mbits/s ∀k. As elaborated by the curves, it is observed that the overall communication and computing latency does not always monotonically increase with respect to the height of the UAV swarm. The reason is that although the path loss is larger with higher UAVs, the interference between multiple devices could decrease, showing that higher altitudes of UAVs may have positive effects on the latency performance of the algorithms. Such results indicate that the position and height of the UAV swarm should be appropriately designed in a hierarchical NTN to improve its latency performance.

V. CONCLUSIONS
In this paper, the design of an MEC-empowered NTN for wide-area time-sensitive IoT has been investigated.
To jointly design the communication and MEC systems for hierarchically integrated satellite and UAVs, a processoriented framework has been presented in a time-division manner. Under this framework, a latency minimization problem has been formulated using the large-scale CSI. Then, the problem can be transformed to a simplified form.
After that, an approximation of the simplified problem has been derived. Then, based on the properties of the overall communication and computing efficiency function, the approximated problem has been decomposed into subproblems. Furthermore, an iterative algorithm has been proposed to solve these subproblems by jointly using block coordinate descent and successive convex approximation techniques. Based on the solutions to the subproblems, a process-oriented joint resource orchestration scheme has been proposed for the MEC-empowered NTN. Simulation results have demonstrated that the proposed process-oriented scheme has the best performance in comparison with those of other algorithms. In addition, it has been observed in simulations that the proposed process-oriented scheme can flexibly adapt to varying data sizes. These results have also indicated that the payload deployments of UAVs should be appropriately predesigned to improve the efficiency of resource use in the hierarchical NTN. Furthermore, the results have implied that it is advantageous to integrate NTN with MEC for wide-area time-sensitive IoT.

APPENDIX A JUSTIFICATION OF THE ERGODIC RATE APPROXIMATION
According to the signal model in (3), for any given normalized detection vector which satisfies ||w|| = 1, the received signal of the u-th IoT device at the t-th time can be expressed as In (A.1), h u,k,t , x u,t and n u,k,t can be regarded as independent variables. Therefore, when U → ∞, we can apply Central Limit Theorem to (A.1), so that U v=1,v =u w H h v,k,t x v,t can be regarded as a Gaussian random variable. Thus, we have On the basis of (A.2), the ergodic rate can be approximated by where the last inequality holds because the log function is concave and Jensen inequality can be applied, which gives a justification of the approximation in (16).

APPENDIX C PROOF OF THEOREM 2
Observing (31), we can find that the objective function in (31a) and the constraints in (31c)-(31f) are convex.
For the simplification of notations, the constraints in (31b) are reformulated to where g u (x) = x C u,t (η i−1 )x + 1 − η L,i−1 t . (C. 2) The first-order and second-order derivative of f u (δ T , P i,j ) with respect to δ T is derived as which shows that f u (δ T , P i,j ) is monotonically decreasing and convex with respect to δ T ∀u. Then, we can also give the first-order and second-order derivative of g u (x) as which shows that g u (x) is monotonically increasing and concave with respect to x. According to [45],R U u,t (P i,j |P i,j−1 ) is concave with respect to P i,j ∀u, so that the composition function g u (R U u,t (P i,j |P i,j−1 )) is concave with respect to P i,j . As a result, f u (δ T , P i,j ) is convex with respect to the joint of δ T and P i,j , which can guarantee the convexity of (31).
Furthermore, denoting the optimal solution to (31) as (δ * T , P * ), we have which shows that (δ * T , η * ) belongs to the feasible region of (25). Thus, the conclusion of Property 1 is derived.