Humans usually have conversations by making use of prior knowledge about a topic and background information of the people whom they are talking to. However, existing conversational agents and datasets do not consider such comprehensive information, and thus they have a limitation in generating the utterances where the knowledge and persona are fused properly. To address this issue, we introduce a call For Customized conversation (FoCus) dataset where the customized answers are built with the user's persona and Wikipedia knowledge. To evaluate the abilities to make informative and customized utterances of pre-trained language models, we utilize BART and GPT-2 as well as transformer-based models. We assess their generation abilities with automatic scores and conduct human evaluations for qualitative results. We examine whether the model reflects adequate persona and knowledge with our proposed two sub-tasks, persona grounding (PG) and knowledge grounding (KG). Moreover, we show that the utterances of our data are constructed with the proper knowledge and persona through grounding quality assessment.

Both entity typing and relation extraction from text corpora are widely used to identify the semantic types of an entity and a relation in a knowledge graph (KG). Most existing approaches rely on a pre-defined set of entity types and relation types in a KG. They thus cannot map entity mentions (relation mentions) to unseen entity types (relation types). To fundamentally overcome the limitations, we should add new semantic types of entities and relations to a KG schema. However, schema expansion traditionally requires manual conceptualization through a user’s observation on the text corpus while assuming the existence of suitable target KG schemas. In this work, we propose anActive learning framework forKnowledge graphSchemaExpansion (AKSE), which can generate a new semantic type for KG schemas, without depending on a set of target schemas and human users’ observation. Specifically, a granularity based active learning algorithm determines whether a KG schema requires new semantic types or not. We also introduce a KG schema attention-based neural method which assigns semantic types to the entities and relationships extracted. To the best of our knowledge, our work is the first study to expand a KG schema with active learning.

This paper presents an efficient method of extracting n-ary relations from multiple sentences which is called Entity-path and Discourse relation-centric Relation Extractor (EDCRE). Unlike previous approaches, the proposed method focuses on an entity link, which consists of dependency edges between entities, and discourse relations between sentences. Specifically, the proposed model consists of two main sub-models. The first one encodes sentences with a higher weight on the entity link while considering the other edges with an attention mechanism. To consider various latent discourse relations between sentences, the second sub-model encodes discourse relations between adjacent sentences considering the contents of each sentence. Experiment results on the cross-sentence relation extraction dataset, PubMed, and the document-level relation extraction dataset, DocRED, show that the proposed model outperforms state-of-the-art methods of extracting relations across sentences. Furthermore, ablation study proves that both the two main sub-models have noticeable effect on the relation extraction task.

We investigate competitive online algorithms for online convex optimization (OCO) problems with linear in-stage costs, switching costs and ramp constraints. While OCO problems have been extensively studied in the literature, there are limited results on the corresponding online solutions that can attain small competitive ratios. We first develop a powerful computational framework that can compute an optimized competitive ratio based on the class of affine policies. Our computational framework can handle a fairly general class of costs and constraints. Compared to other competitive results in the literature, a key feature of our proposed approach is that it can handle scenarios where infeasibility may arise due to hard feasibility constraints. Second, we design a robustification procedure to produce an online algorithm that can attain good performance for both average-case and worst-case inputs. We conduct a case study on Network Functions Virtualization (NFV) orchestration and scaling to demonstrate the effectiveness of our proposed methods.

Pricing and task allocation are vital to improving the efficiency in mobile crowdsensing, an emerging human-in-the-loop application paradigm. Previous studies focused on incentive mechanism design for specific sensing applications where one party (either task initiators or platform) can dominate the pricing and task allocation process. These results, however, are not applicable to a free crowdsensing market where multiple task initiators and task participants (mobile users), as peers, are engaged to maximize their own interests. New incentive mechanisms are pressingly needed to produce a solution, so that the interests of all participating parties can be considered. In this paper, appealing to exchange economy theory, we employ the notion of “Walrasian Equilibrium” as a comprehensive metric, at which there exists a price vector for mobile users and an allocation for task initiators such that the allocation is Pareto optimal and the market gets cleared (i.e., all sensing tasks are performed). We consider a standard model where the utility function for sensing quality is monotonically increasing, differentiable, and concave, and the payoff function for a mobile user is linear. To address the problem, we first characterize the supply-demand pattern for a given price vector, which is the subset of mobile users selected by each task initiator to perform the task. We then devise methods for validating the existence of a Walrasian Equilibrium within each supply-demand pattern. One key step is to divide the space of prices into a collection of appropriate cells, based on the hyperplane arrangement, so that each cell has a unique supply-demand pattern. We devise an algorithm that can find a Walrasian Equilibrium in polynomial time, for a case of practical interest where the classes of mobile devices are bounded. Based on the insight, we further consider the general case and design an efficient pattern search (EPS) algorithm to reduce the search space, thus accelerating the search process accordingly. This is realized by choosing the supply-demand pattern which is closer to the “Walrasian Equilibrium” than the pattern in previous iteration in the search process. Our results show that EPS can find an $\epsilon $ -approximation Walrasian Equilibrium in polynomial time for the general case, given a constant $\epsilon $ .

With increasing popularity of location-based services (LBSs), there have also been growing concerns for location privacy. To protect location privacy in an LBS, mobile users in physical proximity can work in concert to collectively change their pseudonyms, in order to hide spatial-temporal correlation in their location traces. In this paper, we leverage mobile users' social tie structure to motivate them to participate in pseudonym change. Drawing on a social group utility maximization framework, we cast users' decision making of whether to change pseudonyms as a socially aware pseudonym change game (SA-PCG). The SA-PCG further assumes a general anonymity model that allows a user to have its specific anonymity set for personalized location privacy. For the SA-PCG, we show that there exists a socially aware Nash equilibrium (SNE), and quantify the system efficiency of SNEs with respect to the optimal social welfare. Then, we develop a greedy algorithm that myopically determines users' strategies, based on the social group utility derived from only the users whose strategies have already been determined. We show that this algorithm efficiently finds an SNE that enjoys desirable properties: 1) it is socially aware coalition-proof, and thus is also Pareto-optimal; 2) it achieves higher social welfare than any SNE for the socially oblivious pseudonym change game. We further quantify the system efficiency of this SNE with respect to the optimal social welfare. We also show that this SNE can be achieved in a distributed manner. Numerical results using real data corroborate that social welfare can be significantly improved by exploiting social ties.

This paper studies an optimal channel assignment problem for passive monitoring in multi-channel wireless networks, where a set of sniffers capture and analyze the network traffic to monitor the wireless network. The objective of this problem is to maximize the total amount of traffic captured by sniffers by judiciously assigning the radios of sniffers to a set of channels. This problem is NP-hard, with the computational complexity growing exponentially with the number of sniffers. We develop distributed online solutions for large-scale and dynamic networks. The dynamism in the network may arise from mobility of the nodes being monitored. Our algorithm is guaranteed to achieve at least 1 - 1/e times the optimum, regardless of the network topology and the channel assignment of nodes to be monitored, while providing a distributed solution amenable to online implementation. Further, our algorithm is cost-effective, in terms of communication and computational overheads, due to the use of purely local communication and the incremental adaptation to network changes. We present two operational modes of our algorithm for two types of networks that change at different rates; one is a proactive mode for fast-varying networks, while the other is a reactive mode for slowly-varying networks. Simulation results demonstrate the effectiveness of the two modes of our algorithm and compare it to the theoretically optimal algorithm.

Cyber-Physical Systems (CPS) are emerging as the underpinning technology for major industries in this century. Wide-area monitoring and control is an essential ingredient of CPS to ensure reliability and security. Traditionally, a hierarchical system has been used to monitor and control remote devices deployed in a large geographical region. However, a general consensus is that such a hierarchical system can be highly vulnerable to component (i.e., nodes and links) failures, calling for a robust and cost-effective communication system for CPS. To this end, we consider a middleware approach to leverage the existing commercial communication infrastructure (e.g., Internet and cellular networks) with abundant connectivity. In this approach, a natural question is how to use the middleware to cohesively “glue” the physical system and the commercial communication infrastructure together, in order to enhance robustness and cost-effectiveness. We tackle this problem while taking into consideration two different cases of middleware deployment: single-stage and multi-stage deployments. We design offline and online algorithms for these two cases, respectively. We show that the offline algorithm achieves the best possible approximation ratio while the online algorithm attains the order-optimal competitive ratio. We also demonstrate the performance of our proposed algorithms through simulations.

Quality of service (QoS)-aware optimal service composition aims to maximize the overall QoS value of the resulting composite service instance while meeting user-specified global QoS constraints. Traditional methods only consider as candidates service instances that implement one abstract service in the composite service and neglect those that could perform multiple abstract services. To overcome this shortcoming, this paper proposes the concept of generalized component services (GCSs), which is defined in a semantic manner, to expand the selection scope so as to achieve a better solution. A QoS-aware multigranularity service composition model is formulated and how to identify all the GCSs for a composite service is elaborated. A backtracking-based algorithm and an extended genetic algorithm are proposed to optimize the resulting composite service instance. Lastly, evaluation results of these algorithms are described.

We study data fusion schemes for early detection of anomalies in an interconnected power grid and communication network, where power nodes rely on the real-time control via communication nodes, which in turn, depend on the former for power supply. Based on a key observation that failures are spatially correlated and propagate through neighboring nodes, we propose a data fusion scheme, which "scans" an anomalous cluster, i.e., a connected component of nodes, in each individual network. We show that the proposed scheme can detect weaker signals of anomalies, compared to baseline approaches, and further its detection capability increases with the size of the anomalous cluster. This finding leads us to further exploit the interdependent structure of failures across two networks and design a more powerful data fusion scheme, which jointly detects an anomalous cluster over the two interconnected networks. To analyze the detection gain of the joint data fusion scheme, we first characterize how quickly the anomalous behavior propagates, in both the power grid and the power- communication network, based on random graph and epidemic models. We then present numerical results to quantify the detection gain of the joint data fusion scheme.

In this paper, we study a privacy-preserving spectrum sharing system to protect secondary users' location privacy while enhancing spectrum access. The location privacy of secondary users can be compromised by an external adversary via the received signal strength (RSS)-based localization technique. To mitigate such privacy threat, we employ a random power perturbation approach that allows each secondary user to judiciously obfuscate the RSS captured by the adversary. While it can protect users' location privacy, the power perturbation approach would inevitably degrade the system performance and bring challenges to the design of the spectrum allocation algorithm. In this work, we adopt a socially-aware database assisted spectrum access system and cast the spectrum allocation under users' power perturbation as a stochastic channel selection game played among the users. To tackle the challenge brought by the privacy protection, we develop a two time-scale distributed learning algorithm, which is shown to converge almost surely to a socially-aware ε-Nash equilibrium. The numerical results show that the higher the privacy protection level is, the more significant the degradation of the network throughput would be.

With increasing popularity of location-based services (LBSs), there have been growing concerns for location privacy. To protect location privacy in a LBS, mobile users in physical proximity can work in concert to collectively change their pseudonyms, in order to hide spatial-temporal correlation in their location traces. In this study, we leverage the social tie structure among mobile users to motivate them to participate in pseudonym change. Drawing on a social group utility maximization (SGUM) framework, we cast users' decision making of whether to change pseudonyms as a socially-aware pseudonym change game (PCG). The PCG further assumes a general anonymity model that allows a user to have its specific anonymity set for personalized location privacy. For the SGUM-based PCG, we show that there exists a socially-aware Nash equilibrium (SNE), and quantify the system efficiency of the SNE with respect to the optimal social welfare. Then we develop a greedy algorithm that myopically determines users' strategies, based on the social group utility derived from only the users whose strategies have already been determined. It turns out that this algorithm can efficiently find a Pareto-optimal SNE with social welfare higher than that for the socially-oblivious PCG, pointing out the impact of exploiting social tie structure. We further show that the Pareto-optimal SNE can be achieved in a distributed manner.

While most of existing efforts for dynamic spectrum access have focused on spectrum sensing of a narrowband band in a given region, this paper takes a holistic perspective to determine the usage profile of wide spectrum bands over a large geographic region. Specifically, a mobile crowdsensing approach is taken to develop a spectrum-profiling framework, which leverages the wisdom of many mobile devices to accomplish large-scale sensing tasks. A key step for spectrum profiling via mobile crowdsensing is to strategically assign sensing tasks to mobile users, so as to maximize the utility of the sensing data acquired. We cast this problem as a joint sensing task and subband allocation problem for utility maximization, capturing the location-specific characteristics of spectrum sensing. Since the problem is NP-hard, we design approximation algorithms. First, we design a greedy approximation algorithm as a baseline. Our analysis shows that the proposed greedy algorithm achieves an approximation ratio of 1/6, i.e., at least 1/6 of the utility obtained by the optimal allocation. Next, we design a Linear Program (LP) rounding based approximation algorithm, aiming to achieve a better approximation ratio than the greedy algorithm. We show that the propopsed LP-rounding algorithm attains an approximation ratio of 1/2 (1 - 1/e) for the general case, and further it achieves 1 - 1/e for a special case of the problem, which is the best possible approximation ratio. We also present the complexity analysis of the two proposed algorithms. We perform numerical experiments to evaluate the average performance of the the proposed algorithms.

Crowdsensing offers an efficient approach to meet the demand in large scale sensing applications. In crowdsensing, it is of great interest to find the optimal task allocation, which is challenging since sensing tasks with different requirements of quality of sensing are typically associated with specific locations and mobile users are constrained by time budgets. We show that the allocation problem is NP hard. We then focus on approximation algorithms, and devise an efficient local ratio based algorithm (LRBA). Our analysis shows that the approximation ratio of the aggregate rewards obtained by the optimal allocation to those by LRBA is 5. This reveals that LRBA is efficient, since a lower (but not tight) bound on the approximation ratio is 4. We also discuss about how to decide the fair prices of sensing tasks to provide incentives since mobile users tend to decline the tasks with low incentives. We design a pricing mechanism based on bargaining theory, in which the price of each task is determined by the performing cost and market demand (i.e., the number of mobile users who intend to perform the task). Extensive simulation results are provided to demonstrate the advantages of our proposed scheme.

Wide-area monitoring, protection and control (WAMPAC) plays a critical role in smart grid, for protection against possible contingencies, by using the Supervisory Control and Data Acquisition (SCADA) system. However, a general consensus is that such a hierarchical system can be highly vulnerable to component (i.e., nodes and links) failures, calling for a robust and cost-effective communication system for smart grid. To this end, we consider a middleware approach to leverage the existing commercial communication infrastructure with abundant connectivity. In this approach, a natural question is how to use the middleware to cohesively “glue” the power grid and the commercial communication infrastructure together, in order to enhance robustness and cost-effectiveness. We tackle this problem while taking into consideration the multi-stage deployment of power devices and their redundant connections. We show that this problem can be cast as a minimum-cost middleware design under incremental deployment — an “online” problem where the input is provided gradually due to the incremental deployment. We design a randomized “online” algorithm, and show that it achieves the order-optimal average competitive ratio. Simulation results demonstrate the performance of our proposed algorithm, compared to the optimal offline solution.

Most of the mobile platforms provide a keyword based full text search (FTS) for users to find what they want. However, FTS has difficulties in dealing with the cases where a user cannot remember the exact keywords about target data or the number of search results is too many. To overcome these limitations of FTS, we propose a semantically enhanced method of searching for data on mobile devices along with mobile ontology. Experimental results of the proposed method show that our method provides accurate search results and is suitable for a mobile environment.

This paper studies the optimal sniffer-channel assignment for reliable monitoring in multi-channel wireless networks. This problem concerns how to deploy certain sniffers in a network (and tune their channels) so that they can overhear and verify communication among the other nodes, referred to as normal nodes. Prior works have studied the optimal sniffer-channel assignment, but they assume perfect sniffers. However, in practice, sniffers may probabilistically make errors in monitoring, e.g., due to poor reception and compromise by an adversary. Hence, to maintain acceptable monitoring quality, a node needs to be overheard by multiple sniffers. We show that the optimal sniffer-channel assignment with sniffer redundancy differs fundamentally from the previous works due to the absence of a desirable property called submodularity. As a result, in our problem, the prior approximation algorithms no longer maintain their performance guarantees. We propose a variety of approximation algorithms based on two approaches-greedy strategy and relaxation-and-rounding approach. We present an empirical performance analysis of the proposed algorithms through simulations in practical networks. Our results suggest that our two algorithms show a performance trade-off between coverage and running time and are therefore suitable for different kinds of deployment.

This paper studies an optimal channel assignment problem for passive monitoring in multi-channel wireless networks, where a set of sniffers capture and analyze the network traffic to monitor the network. The objective of this problem is to maximize the total amount of traffic captured by sniffers by judiciously assigning the radios of sniffers to a set of channels. This problem is NP-hard, with the computational complexity growing exponentially with the number of sniffers. We develop distributed online solutions to this problem for large-scale and dynamic networks. Prior works have attained a constant factor equation of the maximum monitoring coverage in a centralized setting. Our algorithm preserves the same ratio while providing a distributed solution that is amenable to online implementation. Also, our algorithm is cost-effective, in terms of communication and computational overheads, due to the use of only local communication and the adaptation to incremental network changes. We present two operational modes of our algorithm for two types of networks that have different rates of network changes. One is a proactive mode for fast varying networks, while the other is a reactive mode for slowly varying networks. Simulation results demonstrate the effectiveness of the two modes of our algorithm.

To enhance the correctness of the composition of services, we propose a graph-based composition method that explicitly specifies and uses the functional semantics of Web services. Actions, which represent what services actually do, are identified to specify the functional semantics of services. Dependencies among services are organized and stored as an AND/OR graph, on which composition is performed. Rules are devised to map a service into an appropriate action and to identify the combined action of a composite service. The experimental results show the superiority of the proposed method in terms of the correctness of service composition.

Wireless mesh networks (WMN) are finding increasing usage in city-wide deployments for providing network connectivity. Mesh routers in WMNs typically use multiple wireless channels to enhance the spatial-reuse of frequency bands, often with multiple radios per node. Due to the cooperative nature of WMNs, they are susceptible to many attacks that cannot be defeated by using traditional cryptographic mechanisms of authentication or encryption alone. A solution approach commonly used for defending against such attacks is behavior-based detection in which some nodes overhear communication in their neighborhood to determine if the behavior by a neighbor is legitimate. It has been proposed to use specialized monitoring nodes deployed strategically throughout the network for performing such detection. The problem that arises is where to deploy these monitoring nodes, how to minimize their number, and which channels to tune their radios to, such that the maximum part of the network can be covered. This problem has been solved for single channel networks by a greedy approximation algorithm since the exact solution is NP-hard. The greedy algorithm achieves the best performance, in terms of the worst case, possible among all polynomial-time algorithms provided that P!=NP. In this paper, we solve the problem for multi-channel multi-radio WMNs. The intuitive extension of the greedy algorithm destroys the property of best performance. Instead, we formulate the problem as an integer linear program, solve its linear program relaxation, and then use two rounding techniques that we develop by adapting existing rounding schemes. We thereby present two approximation algorithms. The first, computationally-light algorithm, called probabilistic rounding algorithm gives an expected best performance in the worst case. The second, called deterministic rounding algorithm achieves the best worst-case performance in a deterministic manner. To evaluate how the three algorithms perform in practice, we simulate them in random networks and scale-free networks.

As ITS technology evolves, very large volume of traffic data can be obtained in real-time. Traffic data are continuously produced and they can be considered as a kind of stream data. Currently, such traffic data are not maintained permanently because of the storage limitations of operational systems. Therefore, it was impossible to compare temporal historical patterns over long time periods. In this paper, we propose a traffic data management scheme, which can handle historical data as well as current data. The proposed scheme is based on the GALIS architecture, which is a cluster-based distributed computing system architecture that consists of multiple data processors, each dedicated to keeping records relevant to a different geographical zone and a different time zone. Some experimental results showing performance factors are also explained.

We introduce a new synchronization scheme to improve the synchronization performance in a ultra-wideband (UWB) non-coherent energy collection receiver. Our proposed scheme exploits the mean normalized energy profile, which is known at the receiver, to acquire synchronization. The synchronization process is performed through comparing the energy collected from the received signal with the mean normalized energy profile and correcting the timing error. The synchronization performance is investigated in terms of the normalized mean squared synchronization error (NMSSE) in IEEE 802.15.3a UWB indoor channel environment. Through simulation results, we show that the proposed scheme enhances the synchronization performance.