The Internet-of-Things (IoT) has inspired numerous new applications ever since its invention. Nevertheless, its development and utilization have always been restricted by the limited resources in various application scenarios. In this paper, we study the problem of resource provisioning for real-time IoT applications, i.e., applications that process concurrent data streams from data sources in the network. We investigate joint application placement and data routing to support IoT applications that have both quality-of-service and robustness requirements. We formulate four versions of the provisioning problem, spanning across two important classes of real-time applications (parallelizable and non-parallelizable), and two provisioning scenarios (single application and multiple applications). All versions are proved to be NP-hard. We propose fully polynomial-time approximation schemes for three of the four versions, and a randomized algorithm for the forth. Through simulation experiments, we analyze the impact of parallelizability and robustness on the provisioning performance, and show that our proposed algorithms can greatly improve the quality-of-service of the IoT applications.

The scarcity of spectrum channels resides in the limited bandwidth resource and the exploding demand from spectrum-based services and devices. To help ease this scarcity, the concept of cognitive radio networks (CRNs) is proposed, where licensed spectrum holders (primary users) may lease their channels to unlicensed users (secondary users). Many CRN auctions are thus designed to incentivize primary users (PUs) to share their idle channels with secondary users (SUs). Most of these auctions assume that a transmitting PU does not lease its channel to SUs; if it leases its channel to SUs, it does not transmit itself. To further utilize the resource, researchers have studied the scenario where a transmitting PU is allowed to lease its channels to SUs if the transmissions of the SUs do not undermine the transmission of the PU. However, the study assumes that there is only one PU who owns the licensed channels, whereas in practice, channels may be contributed by multiple PUs. This prevents the result of the study from being directly applied to the multi-PU scenario, as the potential competitions among the PUs are neglected. We extend the scenario to the CRN with multiple PUs and propose TDSA-PS as a Truthful Double Spectrum Auction with transmitting Primary users Sharing. We prove that TDSA-PS is truthful, individually rational, budget-balanced, and computationally efficient.

S-The emergence of the Internet-of-Things (IoT) has inspired numerous new applications. However, due to the limited resources in current IoT infrastructures and the stringent quality-of-service requirements of the applications, providing computing and communication supports for the applications is becoming increasingly difficult. In this paper, we consider IoT applications that receive continuous data streams from multiple sources in the network, and study joint application placement and data routing to support all data streams with both bandwidth and delay guarantees. We formulate the application provisioning problem both for a single application and for multiple applications, with both cases proved to be NP-hard. For the case with a single application, we propose a fully polynomial-time approximation scheme. For the multi-application scenario, if the applications can be parallelized among multiple distributed instances, we propose a fully polynomial-time approximation scheme; for general non-parallelizable applications, we propose a randomized algorithm and analyze its performance. Simulations show that the proposed algorithms greatly improve the quality-of-service of the IoT applications compared to the heuristics.

With the proliferation of smart mobile devices (smart phone, tablet, and wearable), mobile crowdsensing becomes a powerful sensing and computation paradigm. It has been put into application in many fields, such as spectrum sensing, environmental monitoring, healthcare, and so on. Driven by promising incentives, the power of the crowd grants crowdsensing an advantage in mobilizing users who perform sensing tasks with the embedded sensors on the smart devices. Auction is one of the commonly adopted crowdsensing incentive mechanisms to incentivize users for participation. However, it does not consider the incentive for user solicitation, where in crowdsensing, such incentive would ease the tension when there is a lack of crowdsensing users. To deal with this issue, we aim to design an auction-based incentive tree to offer rewards to users for both participation and solicitation. Meanwhile, we want the incentive mechanism to be robust against dishonest behavior such as untruthful bidding and sybil attacks, to eliminate malicious price manipulations. We design RIT as a Robust Incentive Tree mechanism for mobile crowdsensing which combines the advantages of auctions and incentive trees. We prove that RIT is truthful and sybil-proof with probability at least H, for any given H ∈ (0, 1). We also prove that RIT satisfies individual rationality, computational efficiency, and solicitation incentive. Simulation results of RIT further confirm our analysis.

Cloud computing has emerged as a powerful and elastic platform for internet service hosting, yet it also draws concerns of the unpredictable performance of cloud-based services due to network congestion. To offer predictable performance, the virtual cluster abstraction of cloud services has been proposed, which enables allocation and performance isolation regarding both computing resources and network bandwidth in a simplified virtual network model. One issue arisen in virtual cluster allocation is the survivability of tenant services against physical failures. Existing works have studied virtual cluster backup provisioning with fixed primary embeddings, but have not considered the impact of primary embeddings on backup resource consumption. To address this issue, in this paper we study how to embed virtual clusters survivably in the cloud data center, by jointly optimizing primary and backup embeddings of the virtual clusters. We formally define the survivable virtual cluster embedding problem. We then propose a novel algorithm, which computes the most resource-efficient embedding given a tenant request. Since the optimal algorithm has high time complexity, we further propose a faster heuristic algorithm, which is several orders faster than the optimal solution, yet able to achieve similar performance. Besides theoretical analysis, we evaluate our algorithms via extensive simulations.

The ever-increasing mobile traffic has inspired deployment of capacity and performance enhancing network services within mobile networks. Owing to recent advances in network function virtualization, such network services can be flexibly and cost-efficiently deployed in the mobile network as software components, avoiding the need for costly hardware deployment. Nevertheless, this complicates network planning by bringing the need for service function chaining. In this paper, we study mobile network planning through a software-defined approach, considering both quality-of-service and reliability of different classes of traffic. We define and formulate the traffic steering problem for service function chaining in mobile networks, which turns out to be NP-hard. We then develop a fast approximation scheme for the problem, and evaluate its performance via extensive simulation experiments. The results show that our algorithm is near-optimal, and achieves much better performance compared with baseline algorithms.

The proliferation of crowdsourcing brings both opportunities and challenges in various fields, such as environmental monitoring, healthcare, and so on. Often, the collaborative efforts from a large crowd of users are needed in order to complete crowdsourcing jobs. In recent years, the design of crowdsourcing incentive mechanisms has drawn much interest from the research community, where auction is one of the commonly adopted mechanisms. However, few of these auctions consider the robustness against false-name attacks (a.k.a. sybil attacks), where dishonest users generate fake identities to increase their utilities without devoting more efforts. To provide countermeasures against such attacks, we have designed a Truthful Auction with countermeasures against False-name Attacks (TAFA) as an auction-based incentive mechanism for crowdsourcing. We prove that TAFA is truthful, individually rational, budget-balanced, and computationally efficient. We also prove that TAFA provides countermeasures against false-name attacks, such that each user is better off not generating any false name. Extensive performance evaluations are conducted and the results further confirm our theoretical analysis.

We propose a new network abstraction, termed critical network flow, which models the bandwidth requirement of modern Internet applications and services. A critical network flow defines a conventional flow in a network with explicit requirement on its aggregate bandwidth, or the flow value as commonly termed. Unlike common bandwidth-guaranteed connections whose bandwidth is only guaranteed during normal operations, a critical network flow demands strictly enforced bandwidth guarantee during various transient network states, such as network reconfiguration or network failures. Such a demand is called the bandwidth criticality of a critical network flow, which is characterized both by its flow value and capability to satisfy bandwidth guarantee in the transient states.We study algorithmic solutions to the accommodation of critical network flows with different bandwidth criticalities, including the basic case with no transient network state considered, the case with network reconfiguration, and the case with survivability against link failures. We present a polynomial-time optimal algorithm for each case. For the survivable case, we further present a faster heuristic algorithm. We have conducted extensive experiments to evaluate our model and validate our algorithms.

As more and more data-intensive applications have been moved to the cloud, the cloud network has become the new performance bottleneck for cloud applications. To boost application performance, the concept of coflow has been proposed to bring application-awareness into the cloud network. A coflow consists of many individual data flows, and a coflow is completed only when all its component flows are transmitted. The network performance of a cloud application is dependent on the completion time of coflows, rather than the completion time of each individual flow. Existing coflow-aware optimization solutions employ flow preemption to reduce the completion time, which brings difficulty in practical implementation and non-negligible overhead. In this paper, we study the non-preemptive coflow scheduling and routing problem in the cloud network. We propose an offline optimization framework for coflow scheduling, as well as two subroutines for coflow routing using single-path routing and multi-path routing respectively. We also show that our proposed framework is easily extensible to the online scenario. Extensive evaluations show that the proposed solutions can greatly reduce coflow completion time compared to coflow-agnostic solutions, and are also computationally efficient.

Dynamic Proof of Storage (PoS) is a useful cryptographic primitive that enables a user to check the integrity of outsourced files and to efficiently update the files in a cloud server. Although researchers have proposed many dynamic PoS schemes in singleuser environments, the problem in multi-user environments has not been investigated sufficiently. A practical multi-user cloud storage system needs the secure client-side cross-user deduplication technique, which allows a user to skip the uploading process and obtain the ownership of the files immediately, when other owners of the same files have uploaded them to the cloud server. To the best of our knowledge, none of the existing dynamic PoSs can support this technique. In this paper, we introduce the concept of deduplicatable dynamic proof of storage and propose an efficient construction called DeyPoS, to achieve dynamic PoS and secure cross-user deduplication, simultaneously. Considering the challenges of structure diversity and private tag generation, we exploit a novel tool called Homomorphic Authenticated Tree (HAT). We prove the security of our construction, and the theoretical analysis and experimental results show that our construction is efficient in practice.

Cloud computing has emerged as a prevailing platform for internet service hosting. To best utilize Cloud resources for profit making, Cloud providers rely on intelligent resource allocation algorithms when provisioning the virtualized environments for tenant service hosting. Conventional resource allocation proposals mainly focus on efficient allocation of the computing and storage resources, with little effort on ensuring the network performance of tenant services. To address this issue, a number of recent efforts abstract tenant services in the form of virtual infrastructures for resource allocation. A virtual infrastructure specifies the tenant's demand of both the computing resources for hosting virtual servers, and the network bandwidth for inter-virtual server communications. With the problem of resource allocation for virtual infrastructures being NP-hard in general networks, heuristic algorithms have been proposed for this problem. In this paper, we propose a novel optimization technique, named sequential rounding, to tackle the resource allocation problem for virtual infrastructures. The proposed technique extends the rounding technique used for the traditional virtual network embedding problem, while minimizing mapping conflicts introduced by the virtual infrastructure embed- ding problem. Experiments show that our proposed algorithm outperforms existing algorithms regarding both the acceptance ratio and average embedding cost of virtual requests.

Crowdsourcing incentive mechanism design has raised numerous interests from research communities in recent years. While most research focuses on contribution-based payment allocation, a solid crowdsourcing incentive mechanism should encourage users to both devote efforts to complete the task and refer other users to join into participation. In this paper, we adopt a data structure called incentive tree which has a unique advantage in incentivizing participants for solicitation. Furthermore, we consider the crowdsourcing scenario where the contribution model is submodular and time-sensitive, which is more realistic compared to the linear summation model adopted by previous works. Under this model, we design a reward mechanism based on the incentive tree, and prove that this mechanism satisfies several economic properties such as continuing contribution incentive, continuing solicitation incentive, θ-reward proportional to contribution, early contribution incentive, and sybil-proofness. We implemented our incentive mechanism and conducted extensive performance evaluations. The evaluation results confirm our theoretical analysis.

Auction is an effective method of allocating scarce spectrum resources in cognitive radio networks, where the primary users are sellers and the secondary users are buyers. In order for the buyers and sellers to act honestly during the auction, truthfulness has been identified as an important property. Current research focuses on the truthfulness and spatial reusability by either assuming that a conflict graph is given under the protocol model, or assuming that the grouping result is given under the physical interference model without power control. To fill this void, we design a framework of truthful double auctions, named TSA, for spectrum sharing in cognitive radio networks. TSA finds a feasible grouping profile such that users in the same group can be assigned to the same channel while each gets a satisfactory SINR value by an appropriate transmitting power allocation. We prove that TSA guarantees all the desired economic properties: individual rationality, budget-balance, computational efficiency, and truthfulness. Extensive performance evaluation also supports our theoretic analysis.

With the prosperity of smart devices, crowdsourcing has emerged as a new computing/networking paradigm. Through the crowdsourcing platform, service requesters can buy service from service providers. An important component of crowdsourcing is its incentive mechanism. We study three models of crowdsourcing, which involve cooperation and competition among the service providers. Our simplest model generalizes the well-known user-centric model studied in a recent Mobicom paper. We design an incentive mechanism for each of the three models, and prove that these incentive mechanisms are individually rational, budget-balanced, computationally efficient, and truthful.

Crowdsourcing is an emerging paradigm where users can have their tasks completed by paying fees, or receive rewards for providing service. A critical problem that arises in current crowdsourcing mechanisms is how to ensure that users pay or receive what they deserve. Free-riding and false-reporting may make the system vulnerable to dishonest users. In this paper, we design schemes to tackle these problems, so that each individual in the system is better off being honest and each provider prefers completing the assigned task. We first design a mechanism EFF which eliminates dishonest behavior with the help from a trusted third party for arbitration. We then design another mechanism DFF which, without the help from any third party, discourages dishonest behavior. We also prove that DFF is semi-truthful, which discourages dishonest behavior such as free-riding and false-reporting when the rest of the individuals are honest, while guaranteeing transaction-wise budget-balance and computational efficiency. Performance evaluation shows that within our mechanisms, no user could have a utility gain by unilaterally being dishonest.

Crowdsourcing is an emerging paradigm where users can pay for the services they need or receive rewards for providing services. One example in wireless networking is mobile crowdsourcing, which leverages a cloud computing platform for recruiting mobile users to collect data (such as photos, videos, mobile user activities, etc) for applications in various domains, such as environmental monitoring, social networking, healthcare, transportation, etc. However, a critical problem arises as how to ensure that users pay or receive what they deserve. Free-riding and false-reporting may make the system vulnerable to dishonest users. In this paper, we aim to design schemes to tackle these problems, so that each individual in the system is better off being honest. We first design a mechanism EFF which eliminates dishonest behavior with the help from a trusted third party for arbitration. We then design another mechanism DFF which, without the help from any third party, discourages free-riding and false-reporting. We prove that EFF eliminates the existence of free-riding and false-reporting, while guaranteeing truthfulness, individual rationality, budget-balance, and computational efficiency. We also prove that DFF is semi-truthful, which discourages dishonest behavior such as free-riding and false-reporting when the rest of the individuals are honest, while guaranteeing budget-balance and computational efficiency. Performance evaluation shows that within our mechanisms, no dishonest behavior could bring extra benefit for each individual.

Recent spectrum auction results have shown that the spectrum is usually sold at a very high unit price. Small network providers may not be able to afford it individually. Inspired by the group buying service on the Internet, group buying strategy has been introduced into the design for spectrum auctions to increase the buying power of small network providers as a whole. In this paper, we consider cognitive radio networks with multiple secondary networks, each of which consists of one secondary access point and a number of secondary users interested in accessing channels licensed to the primary user. We propose TRUBA, a truthful group buying-based auction to take advantage of the collective buying power of secondary users within each secondary network. We carefully design the budget extraction for each secondary access point within the secondary network to maximize the budget collected from the secondary users. In addition, we allow the primary user to assign its channels strategically so as to maximize its profit on each secondary network. These two features together make TRUBA significantly improve the system performance, compared to the existing group buying-based auction, in terms of the number of successful transactions (up to 105% in the evaluation results), the number of winning secondary users (up to 129%), the utility of secondary access points (up to 463%), and the utility of the primary user (up to 119%).

In a competitive environment, competing agents would maximize their ideas' influence for higher profits. For example, in an unsaturated market, when a new company participates in the market sharing competition, it would distribute free tryout or discount to several customers, let them adopt the product or service, and influence others to use this product as propagation goes. This situation can also be applied to other scenarios, such as spreading new ideas in online social networks, political elections, and so on. In this paper, we use a model called Dynamic Influence in Competitive Environments (DICE) to perform the influence propagation. We first prove that finding the optimal utility for the new agent is an NP-hard problem under DICE. Then, we provide an algorithm for these new companies, and prove that the algorithm has a (1/3 - ϵ/n)-approximation ratio to the maximum payoff value. Performance results show that our algorithm has a better performance compared to existing strategies in terms of maximizing the utility for new agents.

Auctions provide a platform for licensed spectrum users to trade their underutilized spectrum with unlicensed users. Existing spectrum auctions either do not apply to the scenarios where multiple sellers and buyers both make offers, or assume the knowledge of the users' valuation distribution for maximizing the profit of the auction. To fill this void, we design PROMISE, a framework for spectrum double auctions, which jointly considers spectrum reusability, truthfulness, and profit maximization without the distribution knowledge. We propose a novel technique, called cross extraction, to compute the bid representing a group of secondary users, who can share a common channel. We prove that PROMISE is computationally efficient, individual-rational, and truthful. In addition, PROMISE is guaranteed to achieve an approximate profit of the optimal auction.