Abstract Critical infrastructure mainly performs its role through an industrial control system (ICS). Organizations conduct cyber exercises between red and blue teams, focusing on offense and defense. Practical exercises require explicit attack scenarios and corresponding defense strategies. However, systematic guides for deriving cyberattack scenarios or defense strategies still need to be improved. This paper proposes a guide for establishing realistic attack scenarios and defense strategies for cybersecurity exercises in ICS environments. Attack scenario generation is divided into four steps: generating attack references, deriving attack sequences, mapping threat information, and mapping vulnerable implementation patterns. Deriving a defensive strategy consists of two steps parallel to developing an attack scenario: deriving containment and eradication. The methodology we propose guides exercise planning based on a knowledge base, thereby assisting exercise planners in generating various scenarios and deriving clear defense strategies. We showed that a clear exercise plan could be established through a case study.

COVID-19 vaccine distribution route directly impacts the community's mortality and infection rate. Therefore, optimal vaccination dissemination would appreciably lower the death and infection rates. This paper proposes the Epidemic Vulnerability Index (EVI) that quantitatively evaluates the subject's potential risk. Our primary aim for the suggested index is to diminish both infection rate and death rate efficiently. EVI was accordingly designed with clinical factors determining the mortality and social factors incorporating the infection rate. Through statistical COVID-19 patient dataset analysis and social network analysis with an agent-based model that is analogous to a real-world system, we define and experimentally validate the capability of EVI. Our experiments consist of nine vaccination distribution scenarios, including existing indexes which estimate the risk and stochastically proliferate the contagion and vaccine in a 300,000 agent-based graph network. We compared the outcome and variation of the three metrics in the experiments: infection case, death case, and death rate. Through this assessment, vaccination by the descending order of EVI has shown to have a significant outcome with an average of 5.0% lower infection cases, 9.4% lower death cases, and 3.5% lower death rate than other vaccine distribution routes.

IoT devices’ storage and computation capacities are constantly increasing in recent years, which brings critical challenges in data privacy protection. Federated learning (FL) and blockchain technology are two popular techniques used in IoT data aggregation, where FL enables data training with privacy protection, and blockchain provides a decentralized architecture for data storage and mining. However, very few the state-of-the-art works consider the applicability of the combination of FL and blockchain. In this paper, we adopt the federated averaging algorithm to reduce the communication overhead between the blockchain and end users to achieve higher performance. We also apply the double-mask-then-encrypt approach for end users to submit their local updates in order to protect data privacy. Finally, we propose and implement a non-interactive Public Verifiable Secret Sharing (PVSS) algorithm with Distributed Hash Table (DHT) that solves the user-drop-out problem and improves the communication efficiency between blockchain and end-users. At last, we theoretically analyze the security strengths of the proposed solution and conduct experiments to measure the execution time of PVSS on both the server and clients sides.

Nowadays, in almost every computer system, log files are used to keep records of occurring events. Those log files are then used for analyzing and debugging system failures. Due to this important utility, researchers have worked on finding fast and efficient ways to detect anomalies in a computer system by analyzing its log records. Research in log-based anomaly detection can be divided into two main categories: batch log-based anomaly detection and streaming log- based anomaly detection. Batch log-based anomaly detection is computationally heavy and does not allow us to instantaneously detect anomalies. On the other hand, streaming anomaly detection allows for immediate alert. However, current streaming approaches are mainly supervised. In this work, we propose a fully unsupervised framework which can detect anomalies in real time. We test our framework on hdfs log files and successfully detect anomalies with an F-1 score of 83%.

The development of communication technology has brought changes to various environments. The evolution from 3G to 4G Long-Term Evolution (LTE) was mainly aimed at improving communication speed. However, the evolution from 4G LTE to 5G New Radio (NR) is not aimed at improving speed alone. In addition to the existing communication types, 5G aims to improve communication to support the Internet of Things (IoT), media, and complex content to which things are connected. In such environments, point-to-point communication has a very inefficient structure to allow content providers to transmit data to many content users. In the 5G era, content providers must distribute content to numerous users, and in this process, they need to protect the content. Multireceiver encryption (MRE) is an encryption technology developed for this purpose. MRE allows multiple recipients to decrypt data using their own private key with single encryption of a data provider. With this technology, even if the number of data recipients is 100,000 or 1,000,000, data can be distributed with single encryption. Therefore, while using the existing 1 : 1 encryption method, it is possible to solve the problem of inefficiency in performing encryption for each recipient. However, existing proposed MREs can cause key escrow problems and partial key verification problems. Furthermore, the privacy issues identifying the recipient may arise because anonymity is not available to the recipient. In addition, it is necessary to ensure a fair decryption process for all recipients which a legitimate user cannot decrypt. In this study, we attempted to address these problems, and through our model, it is possible to distribute the data more securely and efficiently in a 5G environment.

In general, ID‐based proxy reencryption (IBPRE) includes data transfer in a 1 : 1 manner between a sender and receiver. Therefore, only the data owner has the authority to decrypt or reencrypt the data that is encrypted with his/her public key. However, in an environment with data self‐sovereignty, such as an enterprise IoT‐cloud environment, the data are directly managed by cloud once data is uploaded from user‐controlled IoT devices. In such a situation, there is no way of sharing data if the data owner has no access over the data due to being outside the workplace and other issues. In this study, to solve this problem, data can be shared even when the data cannot be accessed by delegating the authority of the data owner to generate the reencryption key to other users. In addition, by solving the security threats that may appear in this process, data sharing can be performed securely and efficiently in the corporate environment.

Recently, the concept of a decentralized data marketplace is getting much attention to exchange user data. Multi‐authority attribute‐based encryption (ABE), which can provide flexibility and user‐centric access control, is previously widely used in decentralized data sharing applications and also becoming a foundation to build decentralized data trading applications. It is known that users in a multi‐authority ABE system can collude by sharing their secret information for malicious purposes. To address this issue, the collusion‐resistant multi‐authority ABE model was introduced in which a unique global identifier (GID) is issued by the central authority (CA) to each user. Unfortunately, such approach cannot be used directly to build a decentralized data marketplace as (a) such intervention of the CA is directly against the main motivation of the decentralized trading platform and, mostly importantly, (b) the CA can exploit its full knowledge on users’ GID to launch various attacks against users. Motivated by these observations, this paper introduces a novel user collusion‐resistant decentralized multi‐authority ABE scheme for privacy preserving data trading systems. In the existing multi‐authority ABE systems, users utilize his/her GID that is solely assigned by the CA to generate his/her secret keys throughout the collaboration with authorities and a user can compute multi‐authority keys by combining the secret keys (stem from the same GID) in various ways. In the proposed system, the CA only has a partial knowledge of users’ GIDs, and thus, users’ privacy can be protected. On the other hand, we set the user’s own partial GID as a secret which can be used to withdraw his/her deposit to discourage any possible collusion among users.

In recent years, a series of researches have revealed that the Deep Neural Network (DNN) is vulnerable to adversarial attack, and a number of attack methods have been proposed. Among those methods, an extremely sly type of attack named the one‐pixel attack can mislead DNNs to misclassify an image via only modifying one pixel of the image, leading to severe security threats to DNN‐based information systems. Currently, no method can really detect the one‐pixel attack, for which the blank will be filled by this paper. This paper proposes two detection methods, including trigger detection and candidate detection. The trigger detection method analyzes the vulnerability of DNN models and gives the most suspected pixel that is modified by the one‐pixel attack. The candidate detection method identifies a set of most suspected pixels using a differential evolution‐based heuristic algorithm. The real‐data experiments show that the trigger detection method has a detection success rate of 9.1%, and the candidate detection method achieves a detection success rate of 30.1%, which can validate the effectiveness of our methods.

As a primitive function of location-based services (LBSs), the location sharing aims to provide a user's current location information to other designated users. In recent years, LBSs have become one of the most popular services provided by mobile online social networks (mOSNs). As LBSs actively exploit the users' identity and current location information, appropriate approaches have to be utilized to protect the location privacy of the users. Several recent reports have discussed the significance of friendship privacy protection with the goal of hiding the friendship relation of users from unintended entities. However, to the best of our knowledge, there hasn't been an approach for protecting the location sharing with complete privacy of location and friendship connections. To address this issue, we propose a new cryptographic primitive, functional pseudonym, for location sharing in mOSNs that ensures both of them. Unlike many of the existing solutions, our approach does not require a fully trusted server and does not assume pre-established secrets among friends, and therefore is highly practical. Also, the proposed approach significantly reduces computational overhead of users by delegating part of the computations for location sharing to a server, therefore it is highly sustainable. Our primitive can be widely used in many mOSNs to enable LBSs with improved privacy and sustainability. Consequently, it will contribute to proliferate LBSs by eliminating users privacy concerns.

Recently, the concept of fog-cloud storage is attracting lots of attentions to overcome the limit of the central cloud storage. A storage audit scheme aims to ensure user that his/her data on the storage is sound. So far, various audit schemes have been introduced for cloud storages. However, compared to a central cloud storage, a distributed fog-cloud storage consists of multiple local fog storages in addition to a global cloud storage and therefore it is not straightforward to directly apply an existing audit scheme for a cloud storage to a fog-cloud storage. To address this issue, this paper introduces a new fog-cloud storage architecture which can achieve much higher throughput compared to the traditional central cloud storage architecture by reducing the traffics at the routers nearby the cloud storage. The proposed architecture provides transparency such that an end user device does not know the existence of fog storages, and only needs to upload its request toward the central cloud. This means that there is no need to make a modification on the existing end user devices. Our system provides a stronger audit scheme which is naturally coupled with the initial data upload process and does not suffer from the replay attack using old proof of data soundness.

This paper introduces the concept of a new service for social Internet of Vehicles (IoV)-based clouds called incentives-based vehicle witnesses as a service (IVWaaS), which employs vehicles moving on the road as the witnesses to designated events. Specifically, we focus on two key enablers, a new secure and privacy preserving service framework as well as a new incentive mechanism to promote the wide adoption of the aforementioned social service. In IVWaaS, when confronted any events, the vehicles in the vicinity with mounted cameras collaborate with other roadside cameras to take pictures of the site of interest around them, and send the pictures to the cloud infrastructure anonymously so that the privacy of the vehicles can be preserved. To stimulate active participation from the users, we also introduce a new privacy-aware incentives mechanism called privacy-aware proportionate receipt collection, in which the contributors are credited according to their contribution to the service and can claim their incentives in a privacy-aware fashion. Service providers can also use the stored pictures as “on-demand picture service.” Other law enforcement agencies can obtain the stored pictorial information and use it as forensics in the investigations.

Over years, many efforts are made for the problem of constructing quality fault-tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g., with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum k-connected m-dominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers k and m satisfying m ≥ k ≥ 1 and k ≤ 3. This paper introduces an approximation algorithm for the problem with m ≥ k ≥ 1. This algorithm is simple to implement; it connects the components by adding a bounded number of paths, which first computes a 1-connected m-dominating set D and repeats the following steps: (a) search the separators arbitrarily in (i - 1, m)-CDS with i = 2, 3, ⋯ , k, (b) add a bounded number of paths connecting the components separated by separators in (i-1, m)-CDS to improve the connectivity of (i-1, m)-CDS, until it becomes k-connected, and (c) remove redundant paths if there exist at every iteration. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant, for any fixed k.

Summary The mobile cloud is a highly heterogenous and constantly evolving network of numerous portable devices utilizing the powerful back‐end cloud infrastructure to overcome their severe deficiency in computing resource and offer various services such as data sharing. Inherently, in mobile cloud, the risk of user privacy invasion by the cloud operator is high. The conditional proxy re‐encryption (CPRE) is a useful concept for secure group data sharing via cloud while preserving the privacy of the shared data from any unintended third parties including the cloud operator. Unfortunately, the state‐of‐art CPRE is not particularly designed for mobile cloud environment and therefore imposes heavy burdens to the weak mobile cloud clients. This paper introduces a new CPRE scheme, namely the CPRE for mobile cloud, which utilizes the back‐end cloud to the extreme extent so that the overhead of terminals is drastically reduced. Specifically, our scheme outsources a significant amount of computation overhead caused by the following functions at terminals: (a) re‐encryption key generation, (b) condition value change, and (c) decryption, to the cloud. The proposed scheme also allows users to verify the correctness of outsourced computation under refereed delegation of computation model. Our simulation results show CPRE for mobile cloud that outperforms its existing alternatives. Copyright © 2016 John Wiley & Sons, Ltd.

Recently, the concept of barrier-coverage of wireless sensor network has been introduced for various civilian and military defense applications. This paper studies the problem of how to organize hybrid sensor network, which consists of a number of energy-scarce ground sensors with homogenous initial battery level and energy-plentiful mobile sensors, to maximum the lifetime of barrier-coverage. Two key observations are (a) as the lifetime of each mobile sensor is much longer than that of the static ground sensors, each mobile sensor is capable of contributing multiple sensor barrier formations, and (b) no mobile sensor node can join two hybrid barriers which will be successively used to continuously protect the area of interest due to the moving delay. Based on these, we introduce a new maximum lifetime barrier-coverage problem in hybrid sensor network. We first propose a simple heuristic algorithm by combining existing ideas along with our own. Then, we design another efficient algorithm for the problem and prove that the lifetime of hybrid barrier constructed by this algorithm is at least three times greater than the existing one on average. Our simulation result shows that the second algorithm outperforms the first algorithm at least 33 percent and up to 100 percent.

Following the recent advances in drone technologies, various algorithmic optimization problems related to the effective operation of drones are drawing lots of attentions. This paper considers two interesting multiple-drone-assisted search-and-reconnaissance scenarios, in each of which, the trajectory optimization of multiple drones is of great significance to minimize the latency in the system. In the first scenario, multiple drones, whose moments of mobilization are not necessarily the same, are trying to urgently collect intelligence from a given point of interest, and we would like to minimize the task completion time, i.e., the time period between the moment that the first drone commences its operation to the moment that the intelligence from all of the points are collected, by optimizing their trajectories. In the second scenario, multiple drones with different speeds, are hovering around the same routes to regularly collect intelligence from highly geographically-diversified points of interest over an extended time period, and we would like to minimize the worst-case data refreshment rate, the largest time gap between two consecutive observations over the same point of interest. In this paper, we formally define each problem, prove its NP-hardness, and propose an approximation algorithm for it. We also conduct a simulation to study the performance of our result.

This paper proposes a new polynomial time constant factor approximation algorithm for a more-a-decade-long open NP-hard problem, the minimum four-connected m-dominating set problem in unit disk graph (UDG) with any positive integer m ≥ 1 for the first time in the literature. We observe that it is difficult to modify the existing constant factor approximation algorithm for the minimum three-connected m-dominating set problem to solve the minimum four-connected m-dominating set problem in UDG due to the structural limitation of Tutte decomposition, which is the main graph theory tool used by Wang et al. to design their algorithm. To resolve this issue, we first reinvent a new constant factor approximation algorithm for the minimum three-connected m-dominating set problem in UDG and later use this algorithm to design a new constant factor approximation algorithm for the minimum four-connected m-dominating set problem in UDG.

Recently an online electric vehicle (OLEV) concept has been introduced, where vehicles are propelled by the wirelessly transmitted electrical power from the infrastructure installed under the road while moving. The absence of secure-and-fair billing is one of the main hurdles to widely adopt this promising technology. This paper introduces a new secure and privacy-aware fair billing framework for OLEV on the move through the charging plates installed under the road. We first propose two extreme lightweight mutual authentication mechanisms, a direct authentication and a hash chain-based authentication between vehicles and the charging plates that can be used for different vehicular speeds on the road. Second, we propose a secure and privacy-aware wireless power transfer on move for the vehicles with bidirectional auditability guarantee by leveraging game theoretic approach. Each charging plate transfers a fixed amount of energy to the vehicle and bills the vehicle in a privacy-aware way accordingly. Our protocol guarantees secure, privacy-aware, and fair billing mechanism for the OLEVs while receiving electric power from the infrastructure installed under the road. Moreover, our proposed framework can play a vital role in eliminating the security and privacy challenges in the deployment of power transfer technology to the OLEVs.

Biological network inference is of importance to understand underlying biological mechanisms. Gene regulatory networks describe molecular interactions of complex biological processes. Graph models are mainly used for gene regulatory networks, where nodes and edges represent genes and their regulations respectively. In the most research, the molecular interactions (edges) of gene regulatory networks are inferred from a single type of genomic data, e.g., gene expression data. However, gene expression is a product of sequential interactions of DNA sequence variations, single nucleotide polymorphism, copy number variation, histone modifications, transcription factor, DNA methylation, and many other factors. There are high-throughput genomic data that measure the various biological processes. We call the multiple types of genomics data as ‘multi-omics data’. In this paper, we propose an Integrative Gene Regulatory Network inference method (iGRN) that can incorporate multi-omics data and their interactions in the graph model of gene regulatory network. Copy number variation and DNA methylation were considered for multi-omics data in this paper. The proposed method, iGRN, was applied to the human brain data of psychiatric disorder. Through the experiments, iGRN showed its better performance on model representation and interpretation than other integrative methods in gene regulatory network inference.

Over years, many efforts are made for the problem of constructing quality fault-tolerant virtual backbones in wireless network. In case that a wireless network consists of physically equivalent nodes, e.g. with the same communication range, unit disk graph (UDG) is widely used to abstract the wireless network and the problem is formulated as the minimum k-connected mdominating set problem on the UDG. So far, most results are focused on designing a constant factor approximation algorithm for this NP-hard problem under two positive integers k and m satisfying m ≥ k ≥ 1 and k ≤ 3. Very recently, Shi et. al. and Fukunaga separately introduced constant factor approximation algorithms for the problem with m ≥ k ≥ 1. However, we found the structures of the algorithms are extremely complicated, and thus it would be difficult to implement and use them in practice. Motivated by such observation, this paper introduces a novel approximation algorithm for the problem with m ≥ k ≥ 1. This algorithm is based on our new technique which first computes a 1-connected m-dominating set D and repeatedly (a) decomposes D into an i-connected block tree, with i = 2, 3, ··· , k, and (b) use this graph structure to improve the connectivity of D, until D becomes k-connected. We provide a rigorous theoretical analysis to prove that the proposed algorithm is correct and its approximation ratio is a constant. We compare the structure of our algorithm against the existing ones and show our algorithm is much simpler to understand and implement.

Location based services (LBSs), which are useful applications of mobile online social network (mOSN), exploit various geographic properties. Location sharing helps people to share their current locations with designated friends and is one important primitive to construct the LBSs. The recent reports showed that a poorly designed location sharing scheme could easily allow the privacy of users to be violated. Over years, lots of efforts are made to provide a privacy-preserving location sharing, but none of them is satisfactory. To address this issue, we introduce a new location sharing scheme in mOSNs with a strong user privacy protection mechanism such that (a) the user's current location as well as (b) the list of friends who will learn the user's current location will be protected from any unintended entity, while the designated friends in the list will learn the exact location of the user. For this purpose, we introduce a new cryptography primitive called the functional pseudonym scheme based on Lagrange polynomial with the public social network IDs of the designated friends. Then, the pseudonym of a user is posted on the server along with the current location of the user. While each user can see every posted messages (pseudonym and location pairs), the actual identify of the originator of each pair can be verified only by designated friends, whose identities are used to compute the pseudonym. Most importantly, unlike any of the existing counterparts, our scheme does not assume neither a trusted server nor pre-established secret among the friends.

Over years, virtual backbone has attracted lots of attention as a promising approach to deal with the broadcasting storm problem in wireless networks. Frequently, the problem of a quality virtual backbone is formulated as a variation of the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum k-connected m-dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph by Wang assumes k ≤ 3 and m ≥ 1, and its performance ratio is 280 when k = m = 3. In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for k ≤ 3 and m ≥ 1. In particular, the algorithm features with (a) a drastically simple structure and (b) a much smaller performance ratio, which is nearly 62 when k = m = 3. We also conduct simulation to evaluate the performance of our algorithm.

Visual sensor networks (VSNs) can track multiple pedestrians and capture high-quality videos of the monitored area. Therefore, VSNs is ideal for providing good broadcast service. In sports broadcasting, a basic requirement for broadcasters is to report the significant events as quickly as possible when they take place. To meet this requirement, we propose the Camera Scheduling for selected area coverage problem (CamS). Considering that Pan-Tilt-Zoom (PTZ) camera sensor has the flexibility of configuring its angle of view in both horizontal and vertical dimensions, we apply PTZ camera sensors to solve CamS. A polynomial time optimal algorithm that schedules PTZ camera sensors elegantly is devised for CamS. We set many realistic application scenarios in simulation and thoroughly study how our algorithm's performance is affected by different environmental parameters, including angle velocity, the number of camera sensors and the number of sub-areas.

Over years, virtual backbone has attracted lots of attentions as a promising approach to deal with the broadcasting storm problem in wireless networks. One popular way to construct a quality virtual backbone is to solve the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum k-connected m-dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph assumes k ≤ 3 and m ≥ 1 and its performance ratio is 280 when k = m = 3. In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for k ≤ 3 and m ≥ 3. In particular, the algorithm features with much simpler structure and much smaller performance ratio, e.g. nearly 66 when k = m = 3. We also conduct simulation to evaluate the performance of our algorithm.

Recently a new concept of online electric vehicle (OLEV) has been introduced in South Korea, where vehicles are propelled through the transmitted energy from the infrastructure installed underneath the road. However, for billing and audit reasons only authentic vehicles with necessary credentials are allowed to charge their batteries and pay the designated amount to the service provider. Moreover, due to the massive budget requirements for such infrastructure, only designated road segments will offer the charging service. As a result, a tradeoff solution to the charging of electric vehicles is needed to both fulfill the charging requirements of the electric vehicles and reduce the upfront costs for the service providers. To obtain electric charge from the charging plates beneath the road, vehicles need to authenticate themselves beforehand for twofold purposes: to bill the vehicles accordingly and to let the revocation authorities revoke the vehicle in case of a dispute. In this paper, we use the core concept of the OLEV and introduce extreme lightweight privacy-aware authentication schemes for charging-on-the-move through the charging plates installed under the road. More precisely we propose two mutual authentication mechanisms between charging plates and the vehicles, a direct authentication and a hash chain-based authentication. In the direct authentication scheme, we leverage multiple pseudonyms for conditional privacy. Vehicles use different pseudonyms every time they use the charging-on-the-move service. Whereas in case of hash chain-based authentication mechanism, the vehicles mutually authenticate with charging plates through service provider. Our proposed authentication mechanisms preserve conditional privacy throughout the protocol and is computationally lightweight than the existing mechanisms.

The aim of influence maximization problem is to find a k-size seed set that has the maximum influence. In previous works the modification of user's attitude is seldom paid attention to. However from the psychology research, we know that people's opinions are affected by their friends. Base on this, we present a new Linear Threshold model with Instant Opinions (LT-IO). We devise an attitude function Atuthat describes node u's attitude at time t, and the broadcast attitude which is the attitude when a node becomes active. To simulate information propagation in real world, we define a trust threshold η to justify whether a node follows or opposes the influence from its neighbor. We propose a heuristic algorithm IMLT-IOA to solve our problem, prove its submodularity and monotonicity and then obtain its approximation ratio which is (1 - 1/e). To the best of our knowledge, this is the first work that focuses on the influence maximization with user's attitude modification. To verify our IMLT-IOA algorithm, we conduct extensive experiments on a large data collection obtained from real social networks, the results show that IMLT-IOA reduces the running time and meanwhile keeps effectiveness comparing to other algorithms.

A wireless sensor network is said to form a belt-barrier for a region if it is able to detect any object moving from outside the region to inside. Recently, Cheng and Tsai found if camera sensors are used to form a belt-barrier, the breadth of the barrier becomes an important quality factor to ensure high quality of monitoring (QoM). Then, they proposed the minimum β-breadth belt-barrier construction problem ((β,1)-B3CP) whose goal is to select a minimum number of camera sensors to form a β-breadth belt-barrier, which ensures the width of the picture of any object which moves through the barrier is at least β. In this paper, we perform more thorough investigation of the problem and introduce a new polynomial time exact algorithm for the problem under the assumption that the angle of each camera is fixed. Our simulation result shows our algorithm outperforms Cheng and Tsai's algorithm. We also introduce a variation of (β, 1)-B3CP, namely (β, k)-B3CP, which aims to construct k node-disjoint β-breadth belt-barrier for fault-tolerance purpose, propose a new heuristic algorithm for it, and conduct simulations to evaluate its performance.

This paper investigates two new groups of trajectory optimization problems which stem from networked multi-robotic systems. In particular, we study how to efficiently collect data from stationary sensor nodes using multiple robotic vehicles such as data ferries under different circumstance. The first group includes two new problems which aim to find the tours and the paths, respectively, of k robot vehicles with different mobilization conditions to collect data from ground sensor nodes with minimum latency. The second group consists of one new problem whose goal is to determine the quality tours of k robot vehicles with different speeds, where each of which follows its corresponding tour to repeatedly collect data from stationary sensors. We prove the three problems are NP-hard and propose constant factor approximation strategies for them. Through a simulation, an analytical study is conducted to evaluate the average performance of our core contribution.

Recently, vehicular ad hoc network (VANET) is receiving lots of attentions as this new networking technology is expected to improve our daily driving experience greatly and will enable a number of emerging applications. It is envisioned that the vehicles in VANETs are armed with a number of advanced technologies such as wireless transceiver, video cameras, etc. This paper investigates the potential of the advanced VANET nodes to construct an impromptu surveillance system to surround an area of interest, which can be a city block, such that any suspect of interest leaving the city block can be monitored by a VANET node participating the surveillance system. Such a system can be useful to provide an emergency response system to keep the track of suspects who are leaving the area by walk or by car after committing a crime inside the block, e.g. Boston bombing suspects. We observe that as the network bandwidth is limited, not all vehicles can participate and transmit video to the control center in real time. Therefore, we propose new scheduling algorithms for the VANET nodes, which consider the mobility of each vehicle as well as the network bandwidth and continuously provides barrier-coverage circumventing the city block over a given mission period. Via simulation, we show the efficiency of our algorithms.

Barrier coverage based on Wireless Sensor Networks (WSNs) has been widely used to prevent intruder trespassing in monitoring systems. Traditionally, enabling perfect barrier coverage is considered the most important goal of barrier coverage studies. Imperfect coverage has been deemed to be a failure. In our research, we attempted to use the redundant sensor nodes in WSNs to prolong the optimal network lifetime of barrier coverage by adding imperfect barrier coverage. Specifically, we devised two schemes, CIBC-1 and CIBC-2, to construct imperfect barrier coverage in order to improve the performance of the existing optimal network lifetime scheduling algorithms for barrier coverage. Our simulation results indicate that our schemes can significantly extend the network lifetime resulting from the state-of-the-art network lifetime scheduling algorithms.

The term "smart grid" refers to the next generation power supply system. A smart meter, an essential component of the grid system, is installed at each housing unit and acts as an agent for the unit. While the smart meter is a key enabler of great opportunities and conveniences in smart grid, it is susceptible to various cyber-security attacks, especially privacy invasion from electricity providers. Trusted third party (TTP) and homomorphic encryption are two favorite tools to deal with this issue in the literature. Unfortunately, the use of TTP does not completely eliminate the privacy risk. On the other hand, the use of homomorphic encryption makes it harder for the providers to support various services whose demand can be highly diversified. In this paper, we introduce a drastically new approach to deal with the consumer privacy issue in smart grid. Our key idea is let each consumer to determine the frequency of the measurement report. In this way, each consumer can responsibly make a trade-off between the level of privacy preservation with the quality of the services it will receive.

This paper investigates the problem of computing the optimal trajectories of multiple data MULEs (e.g., robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks. By relying on a slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood ( k-TSPN) and the k-rooted path cover problem with neighborhood ( k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them along with two simpler heuristic algorithms. We also conduct simulations to compare the performance of the proposed approaches with the existing alternatives. Our simulation results indicate that the proposed algorithms outperform the competitors on average.

Inspired by the dramatic evolution of VANE clouds, this paper proposes a new VANET-cloud service called VWaaS (Vehicle Witnesses as a Service) in which vehicles moving on the road serve as anonymous witnesses of designated events such as a terrorist attack or a deadly accident. When confronted the events, a group of vehicles with mounted cameras collaborate with roadside stationary cameras to take pictures of the site of interest (SoI) around them, and send the pictures to the cloud infrastructure anonymously. The pictures are sent to the cloud in a way that the privacy of the senders can be protected, and kept by the cloud for future investigation. However, for the case that the pictures are used as an evidence of court trial, we made the privacy protection to be conditional and thus can be revoked by authorized entity(s) if necessary.

This paper introduces two new coverage problems in mission-driven camera sensor networks, namely the target temporal effective-sensing coverage with non-adjustable cameras (TEC-NC) problem and the target-temporal effective-sensing coverage with adjustable cameras (TEC-AC) problem. Given a mission period, the objective of the problems is to find a sleep-wakeup schedule of the camera sensor nodes such that the overall target-temporal coverage is maximized. We formally introduce a method called Identifiability Test to check if a target with a face direction is effectively-covered by a camera sensor, and prove the problems are NP-hard. For TEC-NC, we propose a 2-approximation algorithm and two heuristic algorithms. We also design a greedy strategy which can be combined with our solutions for TEC-NC to solve TEC-AC. The simulation results indicate the quality of the outputs of our algorithms are much better than that of the existing alternative as well as close to the theoretical optimum on average.

Online Social Networks (OSNs) have recently emerged as an effective medium for information sharing. Unfortunately, it has been frequently observed that malicious rumors being spread over an OSN are not controllable, and this is not desirable. This paper proposes a new problem, namely the γ - k rumor restriction problem, whose goal is, given a social network, to find a set S of nodes with k protectors (γ * k protectors from the contaminated set, and (1 - γ) * k protectors from the decontaminated set) to protect the network such that the number of decontaminated nodes is maximum. We show that the objective function of the γ - k rumor restriction problem is submodular, and use this result to design a greedy approximation algorithm with performance ratio of 1 - 1/e for the problem under the linear threshold model and independent cascade model, respectively. To verify our algorithms, we conduct experiments on real word social networks including NetHEPT, WikiVote and Slashdot0811. The results show that our algorithm works efficiently and effectively.

In this paper, we study the problem of computing quality fault-tolerant virtual backbone in homogeneous wireless network, which is defined as the$k$-connected$m$-dominating set problem in a unit disk graph. This problem is NP-hard, and thus many efforts have been made to find a constant factor approximation algorithm for it, but never succeeded so far with arbitrary$k\geq 3$and$m\geq 1$pair. We propose a new strategy for computing a smaller-size 3-connected$m$-dominating set in a unit disk graph with any$m\geq 1$. We show the approximation ratio of our algorithm is constant and its running time is polynomial. We also conduct a simulation to examine the average performance of our algorithm. Our result implies that while there exists a constant factor approximation algorithm for the$k$-connected$m$-dominating set problem with arbitrary$k\leq 3$and$m\geq 1$pair, the$k$-connected$m$-dominating set problem is still open with$k>3$.

This paper identifies a new security problem of existing scheduling algorithms for barrier-coverage of sensors, which never considered before. A barrier-cover of wireless sensors is a subset of sensors seamlessly spanning between two opposite sides such that no intruder can move from one side to the other without being detected. The goal of the scheduling algorithms is to find a sleep-wakeup schedule of sensors such that the time to protect an area of interest using a series of alternating barrier-covers can be maximized. We introduce a new security problem which may exist when two barrier-covers, whose covered areas are not completely disjoint, alternate. We show how an intruder can utilize a set of points, namely “barrier-breaches”, to penetrate the alternating barrier-covers. We also propose two remedies for this problem for existing scheduling algorithms. Our analysis shows that depending on the input graph, one of our approaches works better than the other. Given that such scheduling algorithms only need to run during the initialization phase of a sensor network, we suggest to apply both approaches and pick the better schedule rather than relying solely on the approach which works well on average.

Recently, geometric routing has emerged as an efficient routing strategy on wireless networks. An ideal geometric routing is memoryless and does not suffer from the drawbacks of traditional proactive/reactive routings. All existing geometric routings on 3-D wireless networks either work deterministically only on the networks with special properties or do not guarantee delivery. In this paper, we divide the memoryless requirement into two sub-requirements, node-memoryless-ness and message-memoryless-ness. Then, we propose a new node-memoryless geometric routing, which is still free from the drawbacks of traditional routings. Our algorithm partitions the 3-D space with regular cubes and converts the routing problem over nodes into a routing problem over cubes. With minimal information attached to the header of a message, our algorithm deterministically delivers a message to its destination in any connected 3-D wireless networks. The forwarding decision on the message is made in a completely localized manner. The simulation results indicate that our algorithm outperforms its competitors on average.

MultiMedia DataBase Management System (MMDBMS) becomes more popular in recent years, which supports complex and large multimedia data like images, audios, and videos etc. Data Broadcasting is an attractive approach for data dissemination to improve the limitations in mobile environment, such as narrow bandwidth, unreliable connections, and battery limitation. However, existing data broadcast schemes are inefficient for MMDBMS. In this paper, we present four novel multimedia data broadcast schemes (namely, SDAA, MDAA, AEA, and COA) specifically for wireless multichannel communications. The major strategies are scalable coding to generate data segments to different qualities, indexing and channel assignment to minimize the expected waiting time for clients. We prove theoretically that SDAA is a 2-approximation. COA performs best when we release the constraints and it can be judged as an theoretical lower bound, while AEA outputs local optimal solution with quality allocation constraints. Finally, SDAA+AEA form a best scheduling for practical applications. We also provide numerical experiments to evaluate the system performance, proving the efficiency of our schemes.

This paper considers the problem of computing the optimal trajectories of multiple mobile elements (e.g. robots, vehicles, etc.) to minimize data collection latency in wireless sensor networks (WSNs). By relying on slightly different assumption, we define two interesting problems, the k-traveling salesperson problem with neighborhood (k-TSPN) and the k-rooted path cover problem with neighborhood (k-PCPN). Since both problems are NP-hard, we propose constant factor approximation algorithms for them. Our simulation results indicate our algorithms outperform their alternatives.

In this paper, we propose a new multiple-sink positioning problem in wireless sensor networks to best support real-time applications. We formally define this problem as thek-Sink Placement Problem (k-SPP) and prove that it is APX-complete. We show that an existing approximation algorithm for the well-knownk-center problem is a constant factor approximation ofk-SPP. Furthermore, we introduce a new greedy algorithm fork-SPP and prove its approximation ratio is very near to the best achievable, 2. Via simulations, we show our algorithm outperforms its competitor on average.

In this paper, we study the problem of constructing quality fault-tolerant Connected Dominating Sets (CDSs)in homogeneous wireless networks, which can be defined as minimum k-Connected m-Dominating Set ((k,m)-CDS) problem in Unit Disk Graphs (UDGs). We found that every existing approximation algorithm for this problem is incomplete for k ¿3 in a sense that it does not generate a feasible solution in some UDGs. Based on these observations, we propose a new polynomial time approximation algorithm for computing (3,m)-CDSs. We also show that our algorithm is correct and its approximation ratio is a constant.

A Virtual Backbone (VB) of a wireless network is a subset of nodes such that only VB nodes are responsible for routing-related tasks. Since a smaller VB causes less overhead, size is the primary quality factor of VB. Frequently, Unit Disk Graphs (UDGs) are used to model 2D homogeneous wireless networks, and the problem of finding minimum VBs in the networks is abstracted as Minimum Connected Dominating Set (MCDS) problem in UDGs. In some applications, the altitude of nodes can be hugely different and UDG cannot abstract the networks accurately. Then, Unit Ball Graph (UBG) can replace UDG. In this paper, we study how to construct quality CDSs in UBGs in distributed environments. We first give an improved upper bound of the number of independent nodes in a UBG, and use this result to analyze the Performance Ratio (PR) of our new centralized algorithm C-CDS-UBG, which computes CDSs in UBGs. Next, we propose a distributed algorithm D-CDS-UBG originated from C-CDS-UBG and analyze its message and time complexities. Our theoretical analysis shows that the PR of D-CDS-UBG is 14.937, which is better than current best, 22. Our simulations also show that D-CDS-UBG outperforms the competitor, on average.

Connected Dominating Sets (CDSs) can serve as virtual backbones for wireless networks. A smaller virtual backbone incurs less maintenance overhead. Unfortunately, computing a minimum size CDS is NP-hard, and thus most researchers in this area concentrate on how to construct smaller CDSs. However, people neglected other important metrics of network, such as diameter and average hop distances between two communication parties. In this paper, we investigate the problem of constructing quality CDS in terms of size, diameter, and Average Backbone Path Length (ABPL). We present two centralized algorithms having constant performance ratios for its size and diameter of the constructed CDS. Especially, the size of CDS computed by the second algorithm is no more than 6.906 times of its optimal solution. Furthermore, we give its distributed version, which not only can be implemented in real situation easily but also considers energy to extend network lifetime. In our simulation, we show that in average the distributed algorithm not only generates a CDS with smaller diameter and ABPL than related work but also suppresses its size well. We also show that it is more energy efficient than others in prolonging network lifetime.