With the rapid advancement of the Internet of Things and 5G technologies, edge computing has emerged as a vital paradigm for supporting real-time processing and low latency applications. At the core of edge computing lies Virtual Network Embedding (VNE), whose resource allocation efficiency directly influences both service quality and revenue generation in edge environments. Recent research has identified reinforcement learning (RL) as a promising approach to enhance the VNE process. However, most existing RL-based methods overlook the potential of attention mechanisms, which can help agents better understand complex network topologies and thereby improve embedding performance. To address this gap, we propose a novel algorithm, D2ARL (Dual Dynamic Attention-driven Reinforcement Learning), which adaptively captures the dynamic characteristics of both physical and virtual networks through a dynamic attention mechanism. D2ARL is built on a sequence-to sequence (seq2seq) architecture, leveraging dynamic attention in the encoder to capture local features of the networks, and in the decoder to extract globally fused features. Experimental results show that D2ARL outperforms state-of-the-art methods across various network environments. It achieves higher overall benefits and demonstrates stable performance under diverse conditions. Notably, D2ARL improves long-term average revenue by 14.5% compared to the best-performing existing method.

In the digital age, the rapid spread of misinformation and rumors poses a critical challenge for social media platforms and users. Existing rumor containment methods often overlook the diverse range of topics associated with information and fail to consider user interests, resulting in incomplete understanding of rumor propagation. To address this issue, we introduce the Topic-aware Rumor-Truth Cascade (TRTC) model, which incorporates user interests and topic relevance to better capture the dynamics of information propagation. We define the Topic-aware Rumor Containment Maximization (TRCM) problem within TRTC model and prove its monotonicity and submodularity properties. To solve this problem, we propose Topic-aware Reverse Reachable Count (TopicRRC), an efficient index-based algorithm that leverages reverse sampling techniques to quickly identify effective truth seed sets for multiple online TRCM queries, thereby reducing both computational time and memory usage. The extensive experiments on real-world datasets demonstrate that TopicRRC outperforms existing approaches in terms of rumor containment effectiveness and computational efficiency.

Achieving full-view coverage of dynamic targets in camera sensor networks (CSNs) remains a significant challenge, particularly in large-scale and dynamic environments where traditional optimization-based methods struggle to achieve efficient coordination. This study aims to develop an adaptive and scalable framework that enables coordinated sensing and dynamic reconfiguration of camera agents to maximize full-view coverage in real time. To this end, we propose an Automatic Grouping Algorithm (AGA) that reformulates the full-view coverage problem as a multi-agent cooperativecompetitive learning process. AGA integrates three synergistic mechanisms: (i) the Inter-group Competition Mechanism (IeCmM), which enhances adaptive camera positioning through competitive group evolution; (ii) the Intra-group Collaboration Mechanism (IrClM), which optimizes local sensing parameters to improve the coverage rate; and (iii) the Adaptive Adjustment Mechanism (AAM), which dynamically reconfigures group assignments to maintain optimal coverage under environmental variations. These modules are jointly optimized under a multi-agent reinforcement learning (MARL) framework with coordinated policy updates. Extensive experiments demonstrate that AGA consistently outperforms both traditional and state-of-the-art MARL-based baselines, achieving 16%–44% higher full-view coverage efficiency than traditional methods and beyond 71% improvement over advanced learning-based approaches such as HYGMA, HGAP, and GACG. Moreover, AGA exhibits rapid convergence, reaching near-optimal coverage within 10 episodes, and strong scalability across dynamic large-scale environments, demonstrating its effectiveness in complex CSN deployments.

NOR flash has been increasingly popular for RAM-restricted microcontrollers due to its small package, high reliability, etc. To satisfy RAM restrictions, existing NOR flash file systems migrate their functionalities, i.e., block-level data organization and wear leveling (WL), from RAM to NOR flash. However, such fine-grained block-level management introduces frequent index updates and NOR flash scanning, leading to severe I/O amplification, which further deteriorates as they are decoupled in existing NOR flash file systems.

Service migration is crucial in mobile edge computing (MEC) to ensure seamless service provision as users move. Although some migration schemes have been proposed, they fail to efficiently support the migration of microservices in a directed acyclic graph (DAG)-based service across different edge servers, resulting in high service latency. This paper focuses on the DAG-based service migration problem and proposes a collaborative microservice migration framework for MEC, aiming to minimize the service migration latency while efficiently distributing the migration workload across edge servers. We divide edge servers into clusters and formulate the DAG-based service migration problem as a two-stage optimization problem. In the first stage, a deep reinforcement learning-based service pre-migration algorithm is developed to identify the optimal cluster of edge servers for hosting the migrated service. In the second stage, a microservice migration algorithm is devised, utilizing topological sorting and network flow techniques to further determine the target edge server for each microservice. Our design addresses the inherent dependencies among microservices within a DAG task and adapts well to dynamic network environments. Experimental results on real-world datasets demonstrate that our approach significantly reduces service migration latency.

With the widespread use of GPS-enabled smart devices, online social networks are increasingly integrated with offline local services. People are also more inclined to share their real-time offline location and time information with friends on online platforms. Influence maximization, which involves selecting a set of seed nodes to maximize influence within an online social network, has gained significant attention, especially on location-based social networks. However, most recent studies have focused on users’ discrete check-in data and used bipartite graphs to model the one-way relationship between online users and offline locations, without considering the interactions between different offline location. To address this gap, we introduce the location promoting influence maximization (LPIM), which aims to maximize the number of online users visiting promotional offline location. We also propose the TrajectoryCompetition algorithm, which takes into account users’ movement trajectories to capture their mobility patterns and characteristics, along with the competitive relationships between similar offline locations. Furthermore, the algorithm explores potential connections between online users to better estimate their influence. Extensive experiments conducted on datasets from six real-world cities validate the efficiency and effectiveness of the TrajectoryCompetition algorithm.

Influence maximization(IM) aims to identify a set of nodes$S$to maximize the expected number of nodes influenced during the information propagation starting from$S$. Some works had extended this problem to betopic-aware, where each node is associated with a topic distribution and tends to be activated with different probabilities by different topics. However, whether it is topic-aware or not, IM problem only focuses on the active nodes and overlooks all the inactive ones. Actually, an inactive node may receive the information from their active in-neighbors and become informed. Therefore, this type of nodes should also be considered when measuring the coverage of information propagation. Inspired by this, we formulate a new problem calledtopic-aware information coverage maximization(TAICM), which aims to maximize the sum of the expected number of both active and informed nodes in topic-aware social networks. Then we devise a heuristic method to solve it. Experiments on three real-world datasets demonstrate that our method can achieve similar or higher information coverage in much less or at least acceptable time than some commonly used IM algorithms.

There is a huge amount of information generated in online social networks, which is filled with a lot of rumors. The spread of a rumor often leads to the generation of a causal related rumor, and when users believe the first kind of rumor, the probability of being influenced by another causal related rumor is larger. Therefore, the influence probability will change with the process of rumor spreading. In this paper, we design the Causal Rumors Enhance Cascade ($CREC$) model to describe the spreading process of causal related rumors. Then we attempt to select a set of seed users that minimizes the number of users expected to be influenced by rumors, which we call the Causal Related Rumors Controlling (CRRC) problem. The main challenges of this problem are that the influence probability is constantly changing during the spread process, so the reverse sampling technique cannot be used, and the greedy mechanism is not suitable for massive-scale datasets. For the sake of overcoming these challenges and solving the problem, we put forward the Degree Trigonometric Metrology (DTM) algorithm, which uses the property of three-directed circles in the directed network to select seed nodes. Finally, experiments on three massive-scale datasets show that our algorithm outperforms the other algorithms.

The study focuses on achieving full view coverage in a camera sensor network to effectively monitor moving objects from multiple perspectives. Three key issues are addressed: camera direction selection, location selection, and moving object monitoring. There are three steps to maximize coverage of moving targets. The first step involves proposing the Maximum Group Set Coverage (MGSC) algorithm, which selects the camera sensor direction for traditional target coverage. In the second step, a composed target merged from a set of fixed directional targets represents multiple views of a moving object. Building upon the MGSC algorithm, the Maximum Group Set Coverage with Composed Targets (MGSC-CT) algorithm is presented to determine camera sensor directions that cover subsets of fixed directional targets. Additionally, a constraint on the number of cameras is imposed for camera location selection, leading to the study of the Maximum Group Set Coverage with Size Constraint (MGSC-SC) algorithm. Each of these steps formulates a problem on group set coverage and provides an algorithmic solution. Furthermore, improved versions of MGSC-CT and MGSC-SC are developed to enhance the coverage speed. Computer simulations are employed to demonstrate the significant performance of the algorithms.

Abstractive text summarization is to generate concise summaries that well preserve both salient information and the overall semantic meanings of the given documents. However, real-world documents, e.g., financial reports, generally contain rich data such as charts and tabular data which invalidates most existing text summarization approaches. This paper is thus motivated to propose this novel approach to simultaneously summarize both textual and tabular data. Particularly, we first manually construct a “table+text → summary” dataset. Then, the tabular data is respectively embedded in a row-wise and column-wise manner, and the textual data is encoded at the sentence-level via an employed pre-trained model. We propose a salient detector gate respectively performed between each pair of row/column and sentence embeddings. The highly correlated content is considered as salient information that must be summarized. Extensive experiments have been performed on our constructed dataset and the promising results demonstrate the effectiveness of the proposed approach w.r.t. a number of both automatic and human evaluation criteria.

With the rapid development of science and technology, influence maximization (IM) problem has been a hot research issue. There are positive and negative relations in social networks, so the problem of IM in signed networks has a wide range of applications. Moreover, the dissemination of information is usually time-sensitive in social networks. Therefore, in this article, we propose a problem about maximizing the positive influence in signed networks within a limited time (PIMST), further we utilize the influence path to calculate the influence probability and propose an algorithm that is based on forwarding index and inverted index. In the proposed algorithm, we first select candidate seed nodes by combining two effective heuristic methods. Then, we design an algorithm to get the activation probability between node pairs in social networks. At last, we devise a method which combining forward index, inverted index with the idea of cost delay, this method speed up the selection process of seed nodes. Finally, the experimental results on three social network datasets illustrate the effectiveness of our approach compared with other algorithms.

Mobile Edge Computing (MEC) is an emerging computation paradigm that enables mobile devices to offload computation-intensive tasks to edge servers in order to speed up task processing. However, there are still a few challenging problems with MEC before it can be widely adopted. For instance, due to storage and computation constraints, only a limited set of services can be deployed on an edge server. If a mobile device requires a specific service, it can only offload its task to the edge servers that provide the corresponding service. In addition, a task might be composed of several dependent subtasks. The subtask that depends on other subtasks cannot be offloaded until the prerequisite subtasks are completed. Finally, due to the heterogeneity of edge servers, offloading a task to different edge servers could lead to varied energy consumption performance. Few studies consider both of these scenarios and to fulfill the gap, we investigate the task offloading problem in MEC under the dependency and service caching constraints. Specifically, we propose a heuristic algorithm named Table Based Task Offloading Algorithm (TBTOA), which is capable of predicting the impact of offloading decisions. Our experimental results indicate that TBTOA outperforms the existing offloading schemes for MEC in terms of makespan and energy consumption.

Mobile edge computing (MEC) can significantly reduce latency by pushing resources away from remote clouds to distributed base stations (BSs) equipped with MEC servers, which are closer to users and deployed by service providers (SPs) at the edge of cellular networks. To improve user experience and increase their own revenue, SPs tend to use resources in their deployed BSs to provide services instead of using resources in BSs deployed by other SPs. We envision a densely-deployed multi-SP MEC network where a user equipment (UE) is covered by multiple BSs from different SPs. As the resource in BSs and MEC servers is limited, it is a challenging problem for SPs to reasonably allocate resources in the edge computing (EC) layer to improve the quality of service. In this article, we propose a novel resource allocation scheme, Decentralized Multi-SP Resource Allocation (DMRA), which aims to maximize the total profit of all SPs at the EC layer and provide high-quality services. Then, we extend our design to the online scheme. The algorithm Decentralized Multi-SP Online Resource Allocation (DMORA) is proposed to fit the dynamic network environment. Simulation results indicate that our proposed schemes can effectively maximize the total profit of all SPs at the EC layer while improving user experience.

Distributed fog computing has received wide attention recently. It enables distributed computing and data management on the network nodes within the close vicinity of IoT devices. An important service of fog-cloud based systems is data deduplication. With the increasing concern of privacy, some privacy-preserving data deduplication schemes have been proposed. However, they cannot support lossless deduplication of encrypted similar data in the fog-cloud network. Meanwhile, no existing design can protect message equality information while resisting brute-force and frequency analysis attacks. In this paper, we propose a privacy-preserving and compression-based data deduplication system under the fog-cloud network, which supports lossless deduplication of similar data in the encrypted domain. Specifically, we first use the generalized deduplication technique and cryptographic primitives to implement secure deduplication over similar data. Then, we devise a two-level deduplication protocol that can perform secure and efficient deduplication at distributed fog nodes and the cloud. The proposed system can not only resist brute-force and frequency analysis attacks but also ensure that only the data operator can capture the message equality information. We formally analyze the security of our design. Performance evaluations demonstrate that our proposed design is efficient in computing, storage, and communication.

Generating long text conditionally depending on the short input text has recently attracted more and more research efforts.Most existing approaches focus more on introducing extra knowledge to supplement the short input text, but ignore the coherence issue of the generated texts.To address aforementioned research issue, this paper proposes a novel twostage approach to generate coherent long text.Particularly, we first build a document-level path for each output text with each sentence embedding as its node, and a revised selforganising map (SOM) is proposed to cluster similar nodes of a family of document-level paths to construct the directed semantic graph.Then, three subgraph alignment methods are proposed to extract the maximum matching paths or subgraphs.These directed subgraphs are considered to well preserve extra but relevant content to the short input text, and then they are decoded by the employed pre-trained model to generate coherent long text.Extensive experiments have been performed on three real-world datasets, and the promising results demonstrate that the proposed approach is superior to the state-of-the-art approaches w.r.t. a number of evaluation criteria.

Mobile edge computing (MEC) is a promising cloud computing convergence paradigm that improves the quality of services and reduces the traffic load on the core network. By deploying base stations (BSs) endowed with computing resources on the edge of network, MEC system can response to the user requests more efficiently and faster than the traditional cloud center which is far away from the end users. However, limited by the capacity of the computing resource and radio resource on a BS, only a few services can be placed on each BS, and the number of users that each BS can serve in each time slot is also limited. Moreover, in a densely deployed network, service placement decisions of adjacent BSs are influenced by each other, because their communication ranges are overlapped. Thus, service provider (SP) who deploys the BSs on the MEC system has to coordinate service placement among BSs so as to maximize its profit. Moreover, there are different kinds of users on the MEC system, some of them would like to pay more for higher priority to acquire computing resource. Therefore, SPs need to design a pricing method to distinguish users' priorities to get higher profit. In this paper, we will design a novel method to coordinate service placement among BSs and propose a pricing method that considering the difference of users. Our service placement method can theoretically achieve optimal result in single BS. And the simulation results also indicate that our service placement method achieve better performance in the cluster than the existing methods.

With the proliferation of wireless networks, such as WiFi and LTE/5G, Mobile Edge Computing (MEC), is expected to be a promising solution to the resource constraint problem in mobile devices. Technically, MEC is composed of two types of devices: resource-hungry end devices and resource-rich base stations equipped with edge servers. Despite the popularity of MEC, efficient task offloading and resource allocation have been two challenging problems to be tackled. In this paper, we propose an innovative scheme, HTR, that jointly solves the task offloading and resource allocation problem in MEC. Specifically, the problem of task offloading and resource allocation is formulated as a Mixed Integer Non-Linear Programming (MINLP) problem. To reduce the computation complexity of the solution to the MINLP problem, HTR decouples the MINLP problem into two sub-problems: one of them solves the resource allocation problem while the other tackles the task offloading issue. With this carefully-designed approach, both the task offloading and resource allocation problem could be solved with light computation complexity. Our experiment results indicate the HTR outperforms the existing task offloading/resource allocation schemes.

With the development of wireless network technologies, such as LTE/5G, Mobile Cloud Computing (MCC) has been proposed as a solution for mobile devices that need to carry out high-complexity computation with limited resources. Technically, with MCC, high-complexity computation tasks are offloaded from mobile devices to cloud servers. However, MCC does not work well for time-sensitive mobile applications due to the relatively long latency between mobile devices and cloud servers. Mobile Edge Computing (MEC), is expected to solve the problem with MCC. With MEC, edge servers, instead of cloud servers, are deployed at the edge of the network to provide offloading services to mobile devices. Since edge servers are much closer to mobile devices, the resulting latency is significantly lower. Despite the advantages of MEC over MCC, edge servers are not as resource-abundant as cloud servers. Consequently, when many offloaded tasks arrive at an edge server, admission control needs to be in place to arrive at the best performance. In this paper, we propose a Deep Reinforcement Learning (DRL) based admission control scheme, DAC, to maximize the system throughput of an edge server. Our experimental results indicate that DAC outperforms the existing admission control schemes for MEC in terms of system throughput.

The Internet of Things (IoT) can connect intelligent agents, sensors, and many other different devices that facilitate our daily works and lives. With the help of wireless sensor networks (WSNs), the devices can interact with the environment, which is a significant part in the IoT. Coverage is one of the most challenging issues in WSNs. To utilize mobile sensor nodes to provide periodic coverage, a new type of coverage, named sweep coverage, has been proposed and it attracts a lot of attention. To improve data availability in sweep coverage, we introduce the concept of$k$-coverage in conventional coverage to sweep coverage and propose$t, K$-sweep coverage problem in this article, where$t$is the sweep period constraint to finish the whole coverage process and$K$is the set of coverage time requirements. To achieve$t, K$-sweep coverage with the minimum number of mobile sensor nodes, we propose an algorithm named 2-partition sweep coverage (2-PSC) based on a partition of the coverage time requirements and positions. Simulation results indicate that our proposed algorithm outperforms the existing algorithms in terms of the number of required mobile sensor nodes.

With the rapid development and widespread application of crowdsourcing, the limitations of traditional systems are gradually exposed. First, traditional systems fail to protect the privacy of task requesters and workers. They typically rely on a centralized server to aggregate the task content and workers' interests, while these data contain sensitive information. Second, crowdsourcing resources in each system are isolated. The tasks in one system cannot reach potential workers in other systems. Thus, there is a great need to build a new privacy-preserving and federated crowdsourcing system. However, the existing privacy-preserving solutions rely on a trusted third party to perform key management, which is not applicable in a federated setting. To this end, we propose the first proxy-free privacy-preserving and federated crowdsourcing system. It interconnects the existing crowdsourcing systems and can perform encrypted task matching across various systems without relying on a trusted third-party authority. Our main idea is to achieve federated crowdsourcing by moving secure task matching to the trusted smart contract. To get rid of the dependence on the trusted authority, we combine the rewritable deterministic hashing technique with searchable encryption schemes to achieve secure on-chain task-matching authorization. Moreover, we utilize the puncturable encryption technique to implement secure authorization revocation. We formally analyze the security of our design and implement a prototype on Ethereum. Evaluation results demonstrate that our design is secure and efficient for blockchain-based crowdsourcing.

In this article, we present an approach based on counterexample-guided abstraction refinement to verifying full regular temporal properties of C programs by means of combining both static analysis and dynamic verification. To this end, a desired property is specified by a propositional projection temporal logic formula$p$, and the labeled normal form graph (LNFG) of$\lnot p$is automatically produced. Furthermore, the control flow automaton of the C program is constructed, and an enriched abstract reachability tree is generated under the guidance of the LNFG. Throughout the construction of the eART, whenever a candidate counterexample$cp$is found, a verification input w.r.t$cp$is generated by the SMT solver Z3. Subsequently, the C program is converted into a modeling, simulation, and verification language (MSVL) program$m$, and$\lnot p$is also transformed to an MSVL program$m^{\prime }$. As a result,$m\; \text{and} \;m^{\prime }$is executed to check whether the counterexample is spurious. The$cp$is returned if it is a real counterexample; otherwise, the eART is refined. This process is repeated until no counterexample is found, namely the property is valid, or the counterexample is a real one The proposed approach enables us to not only verify full regular properties of C programs, but also produce precise results, neither false negatives nor false positives. The approach has been implemented in a tool named SDMC. Experiments show that SDMC outperforms the relevant tools available.

Energy consumption is one of the most important issues for mobile devices such as smartphones and laptops. For mobile devices that execute multiple computation-intensive or delay-sensitive applications simultaneously, Mobile Edge Computing (MEC) based offloading provides a promising solution to the energy problem. However, blindly offloading all tasks to MEC servers is not the best choice because transferring a simple task to a MEC server via wireless networks might consume more energy than processing the task locally. In addition, Dynamic Voltage and Frequency Scaling (DVFS) could be utilized to reduce the energy consumption associated with locally processed tasks by appropriately lowering CPU frequency. In this paper, we propose a realtime reinforcement learning based offloading scheme, RRLO, which is based on both MEC-based offloading and DVFS-based energy consumption reduction. Technically, RRLO jointly learns the optimal offloading policy and DVFS-based scheduling method. Depending on the workload and network condition, RRLO not only determines whether a task should be offloaded to a MEC server, but also selects the best DVFS method used to schedule local tasks. Our simulation results indicate that RRLO outperforms the existing MEC-based offloading schemes.

Crowdsourcing is a promising computing paradigm that utilizes collective intelligence to solve complex tasks. While it is valuable, traditional crowdsourcing systems lock computation resources inside each individual system where tasks cannot reach numerous potential workers among the other systems. Therefore, there is a great need to build a federated platform for different crowdsourcing systems to share resources. However, the security issue lies in the center of constructing the federated crowdsourcing platform. Although many studies are focusing on privacy-preserving crowdsourcing, existing solutions require a trusted third party to perform the key management, which is not applicable in our federated platform. The reason is that it is difficult for a third party to be trusted by various systems. In this paper, we present a secure crowdsourcing framework as our initial effort toward this direction, which bridges together the recent advancements of blockchain and cryptographic techniques. Our proposed design, named PFcrowd, allows different crowdsourcing systems to perform encrypted task-worker matching over the blockchain platform without involving any third-party authority. The core idea is to utilize the blockchain to assist the federated crowdsourcing by moving the task recommendation algorithm to the trusted smart contract. To avoid third-party involvement, we first leverage the re-writable deterministic hashing (RDH) technique to convert the problem of federated task-worker matching into the secure query authorization. We then devise a secure scheme based on RDH and searchable encryption (SE) to support privacy-preserving task-worker matching via the smart contract. We formally analyze the security of our proposed scheme and implement the system prototype on Ethereum. Extensive evaluations of real-world datasets demonstrate the efficiency of our design.

Location-Based Service (LBS) has been widely deployed. One of the key components of LBS is the positioning algorithm. For outdoor environments, the Global Positioning System (GPS) has been used as the default positioning scheme. However, GPS requires the line of sight to the satellites. When the line of sight is blocked, GPS simply stops working. To tackle the problem with GPS, varied WiFi-based positioning schemes have been proposed. However, the positioning precision of the existing methods is not satisfactory. In this paper, we present a high-precision positioning scheme named Deep Learning based Positioning (DLP). Technically, DLP utilizes both Received Signal Strength Indicator (RSSI) and Channel State Information (CSI) to improve the positioning precision. In detail, a deep neural network is used to model the received RSSI and CSI measurements, which leads to satisfactory positioning accuracy. Our experimental results acquired from a large-scale testbed indicate that DLP outperforms the existing positioning schemes in terms of positioning precision.

Social networks are becoming important dissemination platforms, and a large body of works have been performed on viral marketing, but most are to maximize the benefits associated with the number of active nodes. In this paper, we study the benefits related to interactions among activated nodes. Furthermore, due to the uncertainty in edge probability estimates in social networks, we propose the robust profit maximization problem to have the best solution in the worst case of probability settings. We design a double sandwich algorithm to this problem and further improve the algorithm with sampling method such that it increases robustness of the output. Through real data sets, we verify the effectiveness of our proposed algorithm.

Mobile Edge Computing (MEC) is a burgeoning paradigm that pushes data and services away from remote clouds to distributed Base Stations (BSs) equipped with MEC servers, which are deployed by Service Providers (SPs) at the edge of cellular networks. Normally, a SP prefers to use its own BSs, instead of those deployed by other SPs, to provide data and storage services. This can not only improve the quality of user experience but also increase its own revenue. In a densely deployed MEC network where a User Equipment (UE) tends to be covered by multiple BSs from varied SPs, how to allocate the resources in the BSs to provide the best service is a challenging problem. In this paper, we propose a novel resource allocation scheme, Decentralized Multi-SP Resource Allocation (DMRA), for densely-deployed MEC networks in order to maximize the total profit of all SPs and provide high-quality services. Our experimental results indicate that the proposed scheme outperforms the existing resource allocation algorithms for MEC.

Energy saving is critical for the cloud radio access networks (C-RANs), which are composed by massive radio access units (RAUs) and energy-intensive computing units (CUs) that host numerous virtual machines (VMs). We attempt to minimize the energy consumption of C-RANs, by leveraging the RAU sleep scheduling and VM consolidation strategies. We formulate the energy saving problem in C-RANs as a joint resource provisioning (JRP) problem of the RAUs and CUs. Since the active RAU selection is coupled with the VM consolidation, the JRP problem shares some similarities with a special bin-packing problem. In this problem, the number of items and the sizes of items are correlated and are both adjustable. No existing method can be used to solve this problem directly. Therefore, we propose an efficient low-complexity algorithm along with a context-aware strategy to dynamically select active RAUs and consolidate VMs to CUs. In this way, we can significantly reduce the energy consumption of C-RANs, while do not incur too much overhead due to VM migrations. Our proposed scheme is practical for a large-size network, and its effectiveness is demonstrated by the simulation results.

Online social networks (OSNs) have become effective platforms for influence diffusion. Finding a positive influence dominating set (PIDS) in OSNs can be used to help mitigate social problems such as adolescent drinking and smoking. A set is positive influence dominating if each node in the network is either in the set or has half neighbors in the set. In this article, we propose an efficient greedy algorithm to identify connected PIDS (CPIDS) in large-scale social networks, which utilize two hop coverage information of nodes in the network. Our simulation results show that the proposed approach outperforms existing algorithms in real-world large-scale networks in terms of time cost. Our approach can be potentially used in designing efficient influence diffusion algorithms in OSNs.

Wireless sensor networks (WSNs) are used to cover destination areas for a lot of practical applications. To enhance the performance of the WSN, the virtual backbone based on the connected dominating set is an efficient way with respect to the routing cost between sensors, lifetime of entire network, and so on. In this paper, especially for the WSN with different transmission radii among different sensors, we study the problem of constructing the minimum ρ-range connected dominating set under the constraint α-times of the minimum routing cost (αMOC-ρCDS), where α ) 5 and ρ is the ratio of the maximum-to-minimum transmission radius. Our contributions are three folds. First, we propose a polynomial time approximation scheme which generates the αMOC-ρCDS with the size of at most (1 + ϵ) times of the optimum solution, where ϵ is the error parameter. Second, we propose a polynomial time algorithm and prove that it has two approximation ratios (6ρ+1)2(2ρ+1)2and 10[(2π/θ)I[(ln 3ρ/(ln(1/ cos θ)))] [(ln ρ/(ln(2 cos(π/5))))], where θ <; arcsin(1/3ρ). Finally, we propose the distributed version of the constant approximation ratio algorithm which has both the time complexity and message complexity O(n3), where n is the number of sensor nodes. Besides, the simulation results demonstrate the efficiency of our algorithms.

Multicasting is an important task in Wireless Sensor Networks (WSNs). The minimum energy multicasting problem has been studied intensively. In duty-cycled WSNs, switching between the active and sleep state makes this problem more complicated. In this paper, the problem of minimum energy multicasting with adjustable transmission power in duty-cycled WSNs is studied. Specifically, we propose a novel algorithm named ATPM, with which an extended graph is first constructed, then a multicast tree and the transmission schedule are generated. Our experimental results indicate that the proposed algorithm outperforms the state-of-art algorithms in terms of energy cost.

Mobile edge computing (MEC) can improve the quality of services and save the bandwidth of backhual networks, by placing application services in the base stations (BSs), which are endowed with computing resources and are in close proximity to user equipments (UEs). Since the capacity of an individual BS is limited, only a small number of service instances can be allowed for each BS at the same time. Meanwhile, in a densely deployed network, the coverage areas of adjacent BSs are overlapped. Therefore, these capacity-limited BSs can collaboratively optimize their service placements to improve the performance of MEC. In this paper, we investigate the collaborative service placement (CSP) problem in MEC, which aims to minimize the traffic load caused by service request forwarding. The CSP problem involves several difficult issues, including correlations of adjacent BSs' service placement decisions, joint service placement and UE association, and joint allocation of computing and radio resources. This makes the CSP problem be a complex combinatorial optimization problem. To solve the CSP problem, we propose an efficient decentralized algorithm based on the Matching Theory. It can optimize the decisions of service placement and BS-UE association for BSs, according to local interactions between BSs and UEs. Our proposed algorithm is practical for large-size networks, and its effectiveness is demonstrated by the simulation results.

Sweep coverage is an important problem in Wireless Sensor Networks (WSNs). Technically, sweep coverage makes use of mobile sensor nodes that move around to collect sensing data from Points of Interest (POIs) at a low cost. Since POIs can often be sensed remotely, mobile sensor nodes do not have to arrive at the location of POIs to gather sensing data. Sweep radius, the maximum distance between a mobile sensor node and a POI that enables sensing, is an important factor in sweep coverage planning. In addition, because mobile sensor nodes are typically powered by batteries, they tend to have a limited lifetime. To continue the coverage, mobile sensor nodes have to periodically return to the base station to replenish their energy. In this paper, sweep coverage based on sweep radius and energy limitation is formulated as the (t, T, R)-SCBR problem. To tackle the (t, T, R)-SCBR problem, a centralized algorithm (i.e. CPS) and a distributed algorithm (i.e. DPP) are proposed. Through extensive simulations, we found that the proposed algorithms significantly outperform the existing schemes.

Knowledge based approaches developed for AI planning can convert an intractable planning problem to a tractable one. Current techniques often use temporal logics to express Search Control Knowledge (SCK) in logic based planning. However, traditional temporal logics are limited in expressiveness since they are unable to express spatial constraints which are as important as temporal ones in many planning domains. To this end, we propose a two-dimensional (spatial and temporal) logic namely PPTLSL by temporalizing separation logic with PPTL (Propositional Projection Temporal Logic) which is well-suited to specify SCK involving both spatial and temporal constraints in planning. We prove that PPTLSL is decidable essentially via an equisatisfiable translation from PPTLSL to its restricted form. Moreover, we implement a tool, S-TSolver, which effectively computes plans under the guidance of the spatio-temporal SCK expressed by PPTLSL formulas. The effectiveness of the tool is evaluated on selected benchmark domains from the International Planning Competition.

This paper proposes a novel approach to modeling and verifying real-time systems for high reliability. To do so, we first extend projection temporal logic to timed projection temporal logic. Further, we define a timed modeling, simulation, and verification language (TMSVL) for real-time systems. As a result, both systems and desired properties can be expressed in TMSVL. In particular, real-time behaviors such as delay, timeout, and interrupt can be formalized. Compared with commonly used property specification language, TMSVL is capable of specifying more sophisticated properties such as quantitative timing properties, interval-related properties, and periodically repeated properties. Moreover, the unified model checking approach to verifying real-time systems via dynamical program execution is implemented. In addition, a case study for modeling and verifying a μC/OS-III multitask system with interrupt is conducted to demonstrate how the proposed approach works.

Wireless Sensor Networks(WSNs) are expected to be used in a variety of different applications. One of the most important problems in WSNs is sweep coverage. Sweep coverage utilizes mobile sensor nodes to monitor Points Of Interests (POIs). Thanks to the mobility, sweep coverage can cover more POIs using fewer sensor nodes. In practice, mobile sensor nodes can often collect the data from POIs at a distance via wireless communication. Namely, mobile sensor nodes do not have to reach the physical location of each POI in order to collect the sensing data. Consequently, the route required to provide a sweep coverage can be significantly shortened if the communication range of POIs can be fully utilized. In this paper, we first define the novel problem of Sweep Coverage Based on POI Communication Range. Then we present a centralized and a distributed algorithm, RS and DRS, to solve the novel sweep coverage problem. The performance of the proposed algorithms is evaluated via extensive simulations.

Computational resource allocation is a critical issue for the baseband unit (BBU) pool in a cloud radio access network (C-RAN). There are multiple resources in a BBU, including CPU, memory, disk, etc. The virtual machines (VMs) have diverse requirements along these resources to handle the baseband signal processing of corresponding remote radio units (RRUs). Consolidating VMs to BBUs based on single resource incurs over-allocation of the resources that are not explicitly allocated. Therefore, we study the multi-resource allocation problem in CRANs, which aims to minimize the number of active BBUs that are required to serve all users in the network. Since the RRU can be set to an idle state when its traffic is low, the number of VMs and their resource demands are all adjustable. We propose an efficient algorithm to solve this problem. This algorithm selects active RRUs and associates users with these RRUs in an iterative way. It adapts a heuristic for the multi-dimensional bin packing problem to assign VMs to BBUs. Our proposed method can significantly reduce the number of required active BBUs, while satisfying the VMs' demands for multiple computational resources. Simulation results demonstrate the effectiveness of our proposed algorithm.

Many distributed applications, such as BitTorrent, need to know the distance between each pair of network hosts in order to optimize their performance. For small-scale systems, explicit measurements can be carried out to collect the distance information. For large-scale applications, this approach does not work due to the tremendous amount of measurements that have to be completed. To tackle the scalability problem, network coordinate system (NCS) was proposed to solve the scalability problem by using partial measurements to predict the unknown distances. However, the existing NCS schemes suffer seriously from either low prediction precision or unsatisfactory convergence speed. In this paper, we present a novel distributed network coordinate system (DISCS) that utilizes a limited set of distance measurements to achieve high-precision distance prediction at a fast convergence speed. Technically, DISCS employs the innovative robust nonnegative matrix completion method to improve the prediction accuracy. Through extensive experiments based on various publicly-available data sets, we found that DISCS outperforms the state-of-the-art NCS schemes in terms of prediction precision and convergence speed, which clearly shows the high usability of DISCS in real-life Internet applications.

Sweep coverage is an important problem in wireless sensor networks. With sweep coverage, more Points Of Interests (POIs) can be monitored with fewer mobile sensor nodes thanks to the mobility of the nodes. Most existing studies on sweep coverage focus on the trajectory of the mobile sensor nodes to guarantee the sweep coverage of the POIs. Considering the fact that, in many applications, the collected data is only useful during a fixed period, we studied the problem of sweep coverage with return time constraint. This problem requires that the POIs should be covered and the collected data should be delivered to the base station within a preset time window. In this paper, we prove that the problem of finding the minimum number of mobile sensor nodes required to guarantee sweep coverage with return time constraint is NP-hard. In addition, we present two novel heuristic algorithms, G-MSCR and MinD- Expand, to provide sweep coverage with return time constraint in practice. Our experimental results indicate that, compared to MinD-Expand, G-MSCR requires more sensor nodes and leads to shorter return time. To our knowledge, G-MSCR and MinD- Expand are the only algorithms that attempt to solve the problem of sweep coverage with return time constraint.

Mobile indoor localization is the foundation for the location-based features of many pervasive computing applications. Due to the popularity of WiFi networks in indoor environments, WiFi-based indoor localization has been considered to be a promising approach. Despite the feasibility of WiFi-based localization, the existing WiFi-based schemes suffer from the serious problem of low precision. In this paper, we propose a high-precision indoor localization scheme for mobile networks, Mobile Indoor Localization (MIL). Technically, MIL adopts a matrix completion approach which efficiently utilizes the collected information to achieve high localization precision at low computation cost. Our experimental results indicate that MIL outperforms the state-of-the-art mobile indoor localization schemes in terms of localization precision.

In this paper, we consider the real-time pricing problem for a small scale local power supplier (LPS) in a smart energy community. The LPS supplies power to the residential users (RUs) in a local area and sells the remaining power to the main grid. Since the selling price to the main grid is relative low, LPS intends to sell more power to the RUs with an appropriate price. The LPS determines the price based on the proposed pricing scheme to maximize its revenue. The price is informed to RUs through the communication infrastructure. According to the announced price of LPS, each RU schedules its power consumption to maximize its utility. We model the interactions between the local power supplier and all users as a one-leader multi-followers Stackelberg game, where the LPS acts as the leader and RUs act as the followers. To address this problem, a distributed algorithm based on information exchange between the LPS and RUs is proposed. Simulation results show that the distributed algorithm converges to the Stackelberg equilibrium.

Over the past decades, many large-scale social network systems, such as Facebook and Twitter, have been deployed in different countries. How to efficiently analyze the topological characteristics of large-scale social networks has been a challenging problem in the research community. One of the critical topological characteristics is the shortest distance between two nodes in a network. The existing shortest distance algorithms, such as Breadth First Search (BFS), work well with small networks. For a network with billions of nodes, calculating the pairwise shortest distances with these algorithms requires an overlong period of time. In this paper, we present a high-precision ShOrtest Distance Approximation (SODA) scheme, which utilizes a small set of pre-calculated distances to estimate the shortest distance between each pair of nodes in large-scale social networks. Compared with the existing shortest distance estimation schemes for social networks, SODA leads to high estimation accuracy since it utilizes a novel optimization method, Robust Discrete Matrix Decomposition (RDMD), to eliminate the impact of significant errors/outliers and generate the coordinates of the nodes in a network simultaneously. In addition, SODA differentiates the asymmetric distances in directed graphs. Consequently, SODA works well with both directed and undirected social networks. Finally, SODA only involves convex optimization. Therefore, SODA is highly competitive in terms of computation complexity. Our experimental results indicate that SODA outperforms the state-of-the-art shortest distance estimation schemes in terms of estimation accuracy and running time.

In wireless sensor networks, Virtual Backbone (VB) construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Transmission ranges of sensors are not always equivalent. A sensor networks is modeled as a directed graph while sensors have different transmission ranges. In this paper, we will try to find a special Strongly Connected Bidirectional Dominating Set (SCBDS) within minimum routing cost for each pair of nodes in directed graphs. The SCBDS forms a VB of the networks whose sensors have different transmission radius. For any pair of sensors, the length of the shortest path they communicate with each other through VB should be no more than a constant times the length of the shortest path without using VB. We propose a constant approximate scheme to construct the SCBDS with the bounded size 3*(8ρ+1)2(2ρ+1)2/2 opt. A centralized and a distributed algorithm with the same performance ratio are presented to show the details to construct the SCDS in directed graphs. Simulation results show that the average shortest path length through our algorithms is reduced greatly compared with other algorithms.

The most efficient way to save energy in cellular networks is to switch ON/OFF base stations (BSs) dynamically according to the distribution of user equipment (UE) at real time. When a BS is switched ON/OFF, there is a switching energy cost incurred, which is a significant amount and cannot be ignored. By considering this switching cost, we formulate the energy saving problem of BSs in cellular networks as the minimum energy cost problem (MECP). The objective of MECP is to choose the BSs to be active during a period of time and determine the levels of transmission power of the active BSs according to the UEs that are served by the BSs, such that the total energy cost of the BSs is minimized. We propose a scheme to solve the MECP in two steps. In the first step, we aim to minimize the energy cost of all BSs in a time unit independently, without considering the switching ON/OFF BSs across adjacent time units. In the second step, we consider the switching cost of state transitions of BSs by introducing a state transition graph a BS over an entire time period, and transform the MECP into a minimum energy cost flow problem. A minimum cost flow algorithm is developed to solve this problem. Simulation results show that our proposed scheme can achieve significant energy cost reduction of the cellular network, compared with the existing methods.

Localization is one of the key operations in mobile networks. Due to the limitations of GPS, many researchers have devised a variety of different range-free and range-based localization schemes. Range-free schemes utilize the connectivity information to localize mobile nodes. However, the use of the connectivity information allows a high degree of freedom in terms of pinpointing the location of mobile nodes, which leads to low localization precision. Range-based schemes can achieve high localization precision because they require the fine-granularity distance information. Nevertheless, they normally result in high computation complexity and do not work well when part of the distance measurements are missing. In this paper, we propose a distributed range-based localization scheme, DISCO, that uses a series of minimization problems that only involve convex optimization to arrive at high localization precision and low computation complexity. In addition, when some distance measurements are not available, DISCO utilizes the partial distance information to achieve satisfactory localization results. Furthermore, DISCO is a distributed algorithm, which means that it scales well. The performance of DISCO is analyzed through simulation experiments. An in-depth analysis of the time complexity of DISCO is also included in this paper.

In this paper, we investigate the residential load scheduling problem within a smart energy community, which is powered by a primary utility along with a small scale local power supplier. As a premise, unit prices set by these two suppliers are different and both are time-varying. Therefore, users are motivated to control their household appliances' operation time and calculate appropriate portions of power purchased from these two suppliers to achieve bill curtailments. The capacity constraint of local power supplier, arising from the renewable energy source and the limited storage capability, also should not be violated. We formulate a residential load scheduling problem to address this situation. Distributed scheme based on information exchange among users is proposed, without over revealing individual user's load profile. Then we propose a distributed algorithm to solve this scheduling problem. Simulation results show that the proposed approach can reduce energy cost of the community and cut down electricity payments of users, and the peak-to-average ratio in load demand is also decreased.

Finding a maximum-weighted independent set of links is a fundamental problem in wireless networking and has broad applications in various wireless link scheduling problems. Under protocol interference model, it is NP-hard even when all nodes have uniform (and fixed) interference radii and the positions of all nodes are available. On one hand, it admits a polynomial-time approximation scheme (PTAS). In other words, for any fixed ε > 0, it has a polynomial-time (depending on ε) (1 + ε)-approximation algorithm. However, such PTAS is of theoretical interest only and is quite infeasible practically. On the other hand, only with the uniform interference radii is a simple (greedy) constant-approximation algorithm known. For the arbitrary interference radii, fast constant-approximation algorithms are still missing. In this paper, we present a number of fast and simple approximation algorithms under the general protocol interference model. When applied to the plane geometric variants of the protocol interference model, these algorithms produce constant-approximate solutions efficiently.

Localization in mobile networks is of paramount importance to a variety of pervasive applications. Due to the limitations of GPS, such as high deployment cost, many researchers have devised a variety of different localization schemes based on the measurements of connectivity or distance between neighboring nodes. The existing schemes suffer seriously from either low localization precision or overlong computation time. In this paper, we present a novel localization scheme based on matrix completion, MALL, that utilizes the collected connectivity and distance information to achieve high-precision localization. Since MALL only involves convex optimization and low-complexity non-convex optimization, it can localize mobile nodes at a fast pace. Furthermore, MALL leads to low communication cost. Through intensive simulation and testbed experiments, we found that MALL outperforms the state-of-the-art localization schemes. An in-depth analysis of the time complexity and communication cost of MALL is also included in this paper.

A clustering and partition based Boolean satisfiability solving method is proposed. By partitioning a CNF formula into several clause groups, satisfiability solving problem can be divided into small ones, so the complexity of the problem can be reduced. On the other hand, the satisfiability of different clause groups can be solved in parallel, the decision procedure can be speeded up further. For the formula that cannot generate clause group partition directly, a clustering algorithm is given to clustering clauses into clusters. Then clause group partition can be generated by eliminating common variables among clusters. Further, a method based on minimum cut of undirected graph is given to make partition practical. Preliminary experiments shows that the common variables set among clusters is small for many SAT problems, and our approach can significantly increase the performance of SAT solving.

Localization is a fundamental operation in wireless networks. Location determination is normally accomplished using the Global Positioning System (GPS) for outdoor applications. For indoor localization, GPS does not work due to the lack of the line of sight to satellites. High-precision indoor localization is critical to many personal and business applications. WiFi-based indoor localization was proposed to be a practical method to locate WiFi-enabled devices due to the popularity of WiFi networks. However, it suffers from large localization errors. Our experimental results indicate that this scheme consistently leads to an average error around 3 meters. The existence of different locations with similar WiFi signal strength is the reason behind the large errors. To improve the localization precision, a hybrid indoor localization scheme, HILL, is proposed in this paper. Inspired by the fact that a large number of WiFi-enabled mobile devices have been deployed, HILL uses 3 phases to improve the precision of WiFi-based localization. First of all, it measures the distances between each pair of peer devices through acoustic ranging. Secondly, the Classical Metric Multidimensional Scaling (MDS) method is applied to the collected distances, which results in a graph consistent with the distances. Finally, the graph generated by MDS is embedded onto the graph corresponding to WiFi-based localization in order to achieve high localization precision. Our experimental results indicate that the average localization error of HILL is about 1 meter.

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.

For wireless link scheduling in multi-channel multi-radio wireless networks aiming at maximizing (concurrent) multi-flow, constant-approximation algorithms have recently been developed in [11]. However, the running time of those algorithms grows quickly with the number of radios per node (at least in the sixth order) and the number of channels (at least in the cubic order). Such poor scalability stems intrinsically from the exploding size of the fine-grained network representation upon which those algorithms are built. In this paper, we introduce a new structure, termed as concise conflict graph, on the node-level links directly. Such structure succinctly captures the essential advantage of multiple radios and multiple channels. By exploring and exploiting the rich structural properties of the concise conflict graphs, we are able to develop fast and scalable link scheduling algorithms for either minimizing the communication latency or maximizing the (concurrent) multi-flow. These algorithms have running time growing linearly in both the number of radios per node and the number of channels, while not sacrificing the approximation bounds.

Given a requested area, the Minimum Connected Sensor Cover problem is to find a minimum number of sensors such that their communication ranges induce a connected graph and their sensing ranges cover the requested area. Several polynomial-time approximation algorithms have been designed previously in the literature. Their best known performance ratio is O(r ln n) where r is the link radius of the sensor network and n is the number of sensors. In this paper, we will present two polynomial-time approximation algorithms. The first one is a random algorithm, with probability 1 - ε, producing an approximation solution with performance ratio O(log3n log log n), independent from r. The second one is a deterministic approximation with performance ratio O(r), independent from n.

Inspired by the backbone concept in wired networks, virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). Virtual backbone construction based on Connected Dominating Set (CDS) is a competitive approach among the existing methods used to establish virtual backbone in WSNs. Traditionally, CDS size was the only factor considered in the CDS-based approach. The motivation was that smaller CDS leads to simplified network maintenance. However, routing cost in terms of routing path length is also an important factor for virtual backbone construction. In our research, both of these two factors are taken into account. Specifically, we attempt to devise a polynomial-time constant-approximation algorithm that leads to a CDS with bounded CDS size and guaranteed routing cost. We prove that, under general graph model, there is no polynomial-time constant-approximation algorithm unless P = NP. Under Unit Disk Graph (UDG) model, we propose an innovative polynomial-time constant-approximation algorithm, GOC-MCDS-C, that produces a CDS D whose size I D is within a constant factor from that of the minimum CDS. In addition, for each node pair u and v, there exists a routing path with all intermediate nodes in D and path length at most 7 · d(u, v), where d(u, v) is the length of the shortest path between u and v. Our theoretical analysis and simulation results show that the distributed version of the proposed algorithm, GOC-MCDS-D, outperforms the existing approaches.

MAP is a connectivity-based routing protocol aimed at improving the load balance performance of traditional geographical routing methods. It attempts to find parallel routing paths by taking advantage of the concept of skeleton in the continuous domain. However, MAP suffers seriously from overloading the sensor nodes that are close to the skeleton. In this paper, we propose a contour-based routing protocol, CAR, that does not require geographical information, produces short routing paths, and achieves outstanding load balancing. Our experimental results show that CAR outperforms MAP in terms of both load balancing and routing path length.

The broadcast is a fundamental operation in computer and communication networks. We study broadcast in multiradio multichannel multi-hop wireless networks. Suppose through configuration, each node is already assigned with a transmission power level and a set of radio channels for receiving and forwarding data. Our problem is to select a forward scheme for broadcasting from a given source node and to minimize total energy consumption. This is a known NP-hard minimization problem. In this paper, we construct a polynomial-time (1.35 + ϵ)(1+ln(n-1))-approximation algorithm where n is the number of nodes in given network and ϵ is any positive constant. We also show that there is no polynomial-time (ρ ln n)-approximation for 0O(log log n)).

In this paper, we studied the minimum latency conflict-free many-to-one data aggregation scheduling problem in multi-channel multi-hop wireless sensor networks: Given locations of all sensors and a base station, some sensors which are called as sources, find a schedule such that data from all sources can be transmitted to the base station without any conflict and the latency is minimized. In this model, each sensor has three parameters which are transmission range r, interference range ar and carrier sensing range βr where α, and β are constant. There are λ ≥ 1 available channels for communications. We designed an approximation algorithm with ratio (⌈a/λ⌉ + 11 ⌈b/λ⌉) This work improves our previous work when λ = 1. Extensive simulations valuate the performance of the algorithm.

In wireless sensor networks, virtual backbone construction based on connected dominating set is a competitive issue for routing efficiency and topology control. Assume that a sensor networks is defined as a connected unit disk graph (UDG). The problem is to find a minimum connected dominating set of given UDG with minimum routing cost for each node pair. We present a constant approximation scheme which produces a connected dominating set D, whose size |D| is within a factor α from that of the minimum connected dominating set and each node pair exists a routing path with all intermediate nodes in D and with length at most 5 · d(u,v), where d(u,v) is the length of shortest path of this node pair. A distributed algorithm is also provided with analogical performance. Extensive simulation shows that our distributed algorithm achieves significantly than the latest solution in research direction.

There have been many reliable routing algorithms for wired networks. For routing in wireless sensor networks, the reliability aspect has not been paid as much attention. GEM (Graph EMbedding for sensor networks) is an innovative routing algorithm for wireless sensor networks that is based on the idea of graph embedding. However, it cannot survive edge failures well. In this paper, we propose GW-GEM (Greedy-Walk GEM), a GEM-based multi-path routing algorithm that preserves the advantages of GEM and improves its reliability performance significantly. Specifically, in the case where 1% of edges fail in a 900-node simulated network, GEM leads to a path error rate of 9.2% while GW-GEM only results in a path error rate of 1%.

Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. The problem Minimum-latency beaconing schedule (MLBS) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. In this paper, we first present a constant-approximation algorithm for MLBS under the protocol interference model with arbitrary interference radii. Then, we develop a constant-approximation algorithm for MLBS under the physical interference model. Both approximation algorithms have efficient implementations in a greedy first-fit manner.

Service-oriented wireless sensor networks have recently been proposed to provide an integrated platform, where new applications can be rapidly developed through flexible service composition. In wireless sensor networks, sensors are periodically switched into the sleep mode for energy saving. This, however, will cause the unavailability of nodes, which, in turn, incurs disruptions to the service compositions requested by the applications. Thus, it is desirable to maintain enough active sensors in the system to provide each required service at any time in order to achieve dependable service compositions for various applications. In this paper, we study the cross-layer sleep scheduling design, which aims to prolong the network lifetime while satisfying the service availability requirement at the application layer. We formally define the problem, prove that the problem is NP-hard, and develop two approximation algorithms based on the LP relaxation and one efficient reordering heuristic algorithm. The proposed work will enhance the dependability of the service composition in service-oriented wireless sensor networks.

We studied the minimum latency gossiping (all-to-all broadcast) problem in multihop radio networks defined as follows: Each node in the network is preloaded with a message and the objective is to distribute each node's message to the entire network with minimum latency. We studied this problem in the unit-size message model and the unit disk graph model. The unit-size model means different messages cannot be combined as one message, and the unit disk graph model means a link exists between two nodes if and only if their euclidean distance is less than 1. The minimum latency gossiping problem is known to be NP-hard in these two models. In this work, we designed a gossiping scheme that significantly improved all current gossiping algorithms in terms of the approximation ratio. Our work has approximation ratio 27, a great improvement of the current state-of-the-art algorithm (which has ratio 1,947). We also discussed the single point of failure problem and its impact on our approximation ratio. We designed an amended gossiping algorithm with ratio 27 in case of a nonsource node failure. We also designed an amended gossiping algorithm with ratio 29 in case of source failure.

We studied the minimum-latency gossiping (all-to-all broadcast) problem in multi-hop wireless networks defined as follows. Each node in the network is initially given a message and the objective is to design a minimum-latency schedule such that each node distributes its message to all other nodes. We considered the unit-size message model, in which different messages cannot be combined as one message, and the unit disk graph model, in which a link exists between two nodes if and only if their Euclidean distance is less than 1. This problem is known to be NP-hard in such models. In this work we designed a gossiping scheme that significantly improved all current gossiping algorithms in terms of approximation ratio. Our work has approximation ratio 27, a great improvement of the current state-of-the-art algorithm (which has ratio 1000+).

A wide range of applications for wireless ad hoc networks are time-critical and impose stringent requirement on the communication latency. This paper studies the problem Minimum-Latency Broadcast Scheduling (MLBS) in wireless ad hoc networks represented by unit-disk graphs. This problem is NP-hard. A trivial lower bound on the minimum broadcast latency is the radius R of the network with respect to the source of the broadcast, which is the maximum distance of all the nodes from the source of the broadcast. The previously best-known approximation algorithm for MLBS produces a broadcast schedule with latency at most 648 R. In this paper, we present three progressively improved approximation algorithms for MLBS. They produce broadcast schedules with latency at most 24 R -23, 16 R -15, and R + O (log R) respectively.

Abstract Recent research points out that the flooding mechanism for topology update or route request in existing ad hoc routing protocols greatly degrades the network capacity. If we restrict the broadcast of control packets within a small subset of hosts in the network, the protocol overhead can be substantially reduced. This motivates our research of constructing a virtual backbone by computing a connected dominating set (CDS) in unit‐disk graphs. In this paper, we propose two distributed algorithms to approximate a minimum CDS. These algorithms take linear time. Their performance is verified by a complete theoretical analysis. Copyright © 2006 John Wiley & Sons, Ltd.

This paper investigates the optimal replication of data objects at hierarchical and transparent Web proxies. By transparent, we mean the proxies are capable of intercepting users' requests and forwarding the requests to a higher level proxy if the requested data are not present in their local cache. Two cases of data replication at proxies are studied: 1) proxies having unlimited storage capacities and 2) proxies having limited storage capacities. For the former case, an efficient algorithm for computing the optimal result is proposed. For the latter case, we prove the problem is NP-hard, and propose two heuristic algorithms. Extensive simulations have been conducted and the simulation results have demonstrated significant performance gain by using the proposed data replication algorithms and also shown the proposed algorithms out-perform the standard Web caching algorithm (LRU threshold method).