Multiaccess edge computing (MEC) is extensively utilized within the Internet of Things (IoT), wherein end-users pay services to meet the latency demands of their respective tasks. The pricing is impacted not solely by the quantity of data offloaded by the user but also associated with the leased computing and communication resources. Nevertheless, prevailing pricing strategies seldom account for the personalized resource requisites during user offloading. In this article, we present an adaptive pricing-oriented approach for concomitant task offloading and resource allocation, considering hybrid resources, comprising two key components. First, we propose a differential pricing framework for communication and computation resources, where the unit price will be influenced by the proportion of resources rented by users. Subsequently, we design a two-stage Stackelberg game model: 1) employing convex optimization theory to mitigate problem intricacies and 2) employing gradient descent to ascertain the potentially optimal price, thus achieving a balance between minimizing user expenses and maximizing server profitability. Simulation outcomes demonstrate that our approach slashes user costs by 23.3% and enhances average server revenue by 65.6% compared to a flat pricing model with a high-user request rate (five user-initiated requests per 100 ms). This maintains server occupancy within 60% to 80%, thereby alleviating user queuing and refining user Quality of Experience (QoE).

Edge caching is a promising technique for effectively reducing backhaul pressure and content access latency in the Internet of Vehicles (IoV). The existing content caching solutions still face the following challenges: 1) contents cached on edge servers are outdated quickly as time and user preferences change; 2) the large amount of vehicle data causes huge communication overheads; and 3) limited storage resources of edge servers. Simultaneously considering these issues to reduce transmission latency is a large-scale 0–1 constraint problem, which is NP-hard, and boosting cache hit rates is a key entry point. In this work, we propose a context-aware proactive caching strategy (CPCS) based on asynchronous federated learning (AFL), which works as follows. To improve the accuracy of content popularity prediction, thus improving the cache hit rate, we combine contextual information between different contents and use long and short-term memory networks to analyze the dynamic preferences of vehicle users. After that, vehicles complete the model training and upload via an asynchronous federation learning to complete the popularity prediction. To explore the problem of local models being outdated in AFL, CPCS integrates model compression algorithms, enhancing system efficiency and prediction accuracy. With the prediction results, CPCS gives a content placement algorithm based on the prediction results to approximate the optimal caching scheme. Simulation results show that the CPCS can improve the cache hit rate by 17% at most compared to existing state-of-the-art caching strategies.

In vehicular edge computing (VEC), most tasks require high real-time and energy requirements, but the mobility of vehicles and the difficulty of intelligent computing make it hard to meet these requirements. Due to the fact that most VEC tasks can be decomposed into smaller granularity, based on the dependencies between small subtasks, the repetition of tasks can be reduced, thereby improving task completion rates. In this work, we explore the dependencies of subtasks in different applications and design a two-stage multihop clustering de-duplication offloading (MCDO) mechanism. First, MCDO gives a multihop two-layer clustering (MTLC) algorithm to divide clusters based on similarities between different tasks. Based on this, MCDO further designs a de-duplication logical hierarchical offloading (DLHO). DLHO forms a directed acyclic graph (DAG) of de-duplicated subtasks in each cluster and offloads these subtasks in a logical hierarchical manner. Simulation results show that, compared to existing approaches PC5-GO, FedEdge, and MD-TSDQN, MCDO can achieve a minimum improvement of 15.1% in terms of latency and 20.8% in terms of energy consumption.

The rise of multiaccess edge computing (MEC) speeds up mobile user services and resolves service delays caused by long-distance transmission to cloud servers. However, in task-intensive scenarios, edge server processing limitations lead to buffer congestion, increasing latency and reducing Quality of Service (QoS). Furthermore, the challenges of edge server task processing are increased by the varying deadline requirements of different tasks, the time variability of task arrivals, and the real-time fluctuations of the network. In this work, we propose an adaptive slicing-based task admission scheduling strategy (ASTA) to address these issues. ASTA consists of an adaptive time slice adjustment algorithm (ASTA-I) and a task admission scheduling algorithm (ASTA-II). ASTA-I dynamically adjusts time slices based on real-time network conditions and task flow. ASTA-II first adjusts task priorities dynamically by considering factors, such as data volume, deadlines, network conditions, and buffer locations. After that, ASTA-II formulates different scheduling strategies based on changes in task priorities. These strategies are formulated to improve the throughput efficiency of edge servers and enhance the average response speed of tasks. Simulation results show that compared with the existing O2A and OTDS in different scenarios, the proposed ASTA can reduce the average number of waiting requests in the edge server buffer by 19.53%–57.73% and 20.42%–50.26%, and accelerates the average response speed of tasks by about 39.76% and 32.41%.

The industrial Internet-of-things (IIoT) has attracted extensive attention due to its real-time and automation characteristics. Edge computing and blockchain technologies facilitate the IIoT in terms of low latency services and data security respectively. However, with the continuous expansion of industrial data and the growth of industrial nodes, traditional blockchain technology has some critical limitations on low transaction throughput and high data storage costs. Directed Acyclic Graph (DAG)-blockchain adopts a graph structure of a single transaction as the basic unit, and it has the characteristics of asynchronous consensus. Some existing studies use DAGblockchain to replace the traditional blockchain to alleviate its low throughput problems like IOTA. However, with the rapid data generation in the IIoT environment, the topology scale of DAG-blockchain will increase sharply, which will aggravate the data storage cost of blockchain nodes. In this article, to reduce the data storage cost of edge servers, we design a Graphpartition based storage strategy for DAG-Blockchain (GpDB), equipped with a graph partition algorithm based on transaction freshness, which can partition DAG-blockchain topology in edge servers into two parts, which will be retained and removed respectively. Simulation shows that, in terms of storage cost, GpDB outperforms LDV and Layerchain by 62% and 74% respectively, and with the increasing number of transactions, GpDB has good scalability in reducing the storage cost, and better transaction throughput than IOTA.

Multi-access Edge Computing (MEC) can find its wide applications in various resource-constrained scenario where the user needs to pay a price to the server for meeting the latency requirements of their own tasks. However, to the best of our knowledge, there is no effective pricing model in MEC taking into account the impact of the user’s own energy consumption on the server’s price scheme. In fact, the transmission energy consumption affects the users’ offloading task decisions, which in turn affects the revenue of the edge servers. To fill in this gap, a novel pricing mechanism for energy-sensitive users is proposed in this paper, specifically: 1) We propose a joint optimization problem of computation offloading decisions and resource pricing that considers user energy consumption. 2) By constructing a two-stage Stackelberg game model, the first stage simplifies the problem by constraint relaxation theory and finds an approximate optimal offloading strategy through the Fast Genetic Algorithm (FGA). The second stage uses the gradient descent method to find the potential optimal prices, thereby achieving a balance between the lowest user cost and the highest server profit. Experimental results show that, compared to traditional algorithms, our approach optimizes the average user cost and user task completion time by 24.65% and 12.37%, respectively.

Edge caching is a promising technique for effectively reducing backhaul pressure and content access latency in the Internet of Vehicles (IoV). However, the high mobility of vehicles and dynamic user requests often lead to outdated cached content. Expired cache wastes the limited storage space and transmission in vehicular edge computing. Improving the cache hit rate is an effective approach to address these issues. In this work, we propose a Cooperative Active Caching Strategy (CACS) which works as follows. First, user preferences are analyzed from the historical content data of vehicle users. After that, multiple vehicles cooperate to learn the global model under an asynchronous federated learning framework, and get the content popularity from user preferences and content features. To explore the problem of local models being outdated in asynchronous federated learning, CACS integrates model compression algorithms, enhancing system efficiency and prediction accuracy. Finally, a heuristic cooperative caching content placement algorithm is proposed based on a greedy policy to minimize average access latency. Simulation results show that the CACS can improve the cache hit rate by 15% at most compared to existing state-of-the-art caching strategies.

The increasing demand for in-vehicle applications has raised the complexity and computational load, while the in-vehicle tasks exhibit a sensitivity to latency. Previous research has proposed utilizing the idle computational resources of roadside vehicles to alleviate this contradiction. However, the high mobility of vehicles leads to communication interruptions, and the time-varying nature of vehicle density makes resource allocation challenging. In this work, we leverage the dependencies between vehicular computing tasks and design a deduplication offloading mechanism for stable reduction of latency. This mechanism consists of two stages, named the Multi-hop Clustering Deduplication Offloading (MCDO) mechanism. Firstly, a Multi-hop Two Layer Clustering (MTLC) algorithm is designed to divide vehicles based on task dependencies, speed, and position information. Then, a Deduplication Layered Offloading (DLO) algorithm is proposed to identify and remove duplicated tasks within each cluster while maintaining their inter-dependencies. Simulation results demonstrate that MCDO effectively divides vehicle clusters and offloads tasks efficiently under various road conditions. Compared to existing approaches, MCDO significantly enhances system performance, achieving a minimum improvement of 15.1% in terms of latency.

The rise of Multi-access Edge Computing (MEC) speeds up mobile user services and resolves service delays caused by long-distance transmission to cloud servers. However, in task-intensive scenarios, edge server processing limitations lead to buffer congestion, increasing latency and reducing Quality of Service (QoS). Furthermore, the challenges of edge server task processing are increased by the varying deadline requirements of different tasks, the time variability of task arrivals, and the real-time fluctuations of the network. In this paper, we propose an Adaptive Time Slice Admission Scheduling (ATSAS) strategy to solve these problems. Specifically, ATSAS proposes an Adaptive Time Slice Algorithm (ATSA) and a task Admission Scheduling Algorithm (ASA). ATSA dynamically adjusts the time slice based on real-time network conditions and task flow characteristics. ASA, assisted by ATSA, dynamically adjusts task priorities based on the remaining data amount, deadline requirements, real-time network conditions, and the location of the task buffer. After that, ASA makes different scheduling strategies for tasks. Through the coordination of ATSA and ASA, the proposed strategy ensures the high efficiency and fairness of processing tasks in different realistic scenarios. The simulation results show that, compared with the existing O2A and OTDS in different scenarios, the proposed ATSAS reduces the average number of waiting services in the edge server buffer by 38.63% and 35.34%, and accelerates the average response speed of tasks by about 39.76% and 32.41%.

The concept of Network Function Virtualization (NFV) enables the realization of services as a Service Function Chain (SFC) that is composed of multiple Virtual Network Functions (VNFs), allowing for flexible deployment across the network. For wireless networks comprised of diverse domains which means be managed by different network providers, each domain has different resource and transmission costs. Due to commercial confidentiality reasons, the internal information of these domains is not interconnected, which increases the difficulty of SFC deployment. How to deploy SFCs in multi-domains networks at the lowest cost is becoming a challenge. This paper proposes a novel strategy for the scenario that information of sub-domain is invisible. The strategy firstly splits the SFC based on the processing dependency of its VNFs to reduce intermediate data transmission. Then it utilizes a Graph Matching Network (GMN) to evaluate the matching degree between sub-domain and SFC fragment. This matching degree acts as a reference for optimizing SFC allocation, thereby avoiding the direct acquisition of internal sub-domain information. Simulation results demonstrate that the proposed strategy not only significantly reduces resource, but also maintains a higher request acceptance ratio.

Unmanned Aerial Vehicles (UAVs), due to their flexible deployment, are used as a three-dimensional space assistant tool for Vehicular Edge Computing (VEC) to cover moving vehicles. However, existing work generally assumes relatively uniform vehicle distribution while the actual road conditions vary over time. The time-varying location of vehicles and road congestion in peak hours pose challenges to vehicular edge computing. First, traffic congestion can lead to imbalanced UAVs load, that is UAVs covering congested areas are overloaded while others remain idle. Second, after the high-speed moving vehicle leaves the service range of the current UAV, it is unable to receive computing results of the original request task, which means task processing failure. In this work, we propose a framework of UAV Clusters Adaptive Deployment (UCAD) to address these issues. By clustering vehicles, UCAD gives a Density-Based Adaptive Region Determination algorithm (DBARD) to determine congested areas and dynamically update them to adapt to dynamic network environments. After that, UCAD presents a Particle Swarm Optimization-based Cluster deployment algorithm (PSOC), deploying UAV clusters within determined areas to provide continuous services for vehicles. Simulation results demonstrate that UCAD can adaptively deploy UAV clusters to assist vehicles based on traffic congestion conditions. Simulation results show that compared to existing works, CONEC, TU2V and IELTS, the proposed UCAD can increase the task success rate by 8.7%, 18.5%, and 23.5%, respectively. UCAD can achieve better performance on UAVs workload balance.

In multi-access edge computing, services are cached from cloud servers to the edge base station providing low-latency services. Horizontal Collaboration (HC) between Base Stations (BSs) can alleviate the problem of resource limitation in edge base stations. However, the initiative of cooperation between base stations and the interests of base stations themselves are not guaranteed. In this paper, we study the Joint Service Caching and Task Offloading decision Problem (JSCTOP). To solve this problem, we propose a Two-Stage Optimization Framework (TSOF) based on cooperative community idea to maximize the benefit of each base station. In the first stage, a Collaborative Community Mechanism (CCM) is designed based on the Dissimilarity of Service Types (DST) to enhance the collaborative capability of BSs. In the second stage, an algorithm for service caching and task decision to update and replace the Service Types (STs) of BSs. We also design an algorithm for service pricing to incentivize BSs. In this algorithm, BSs are able to profit from providing services to users and also profit from assisting other base stations. Extensive simulation results show that TSOF outperforms its counterparts in average delay, total energy, total benefit, and community.

Accurate traffic flow prediction is of great importance in Intelligent Transportation System (ITS) for improving traffic efficiency, reducing congestion and so on. However, due to the complex spatial and temporal dependencies, achieving the accurate prediction is challenging. Traditional attention-based networks for traffic flow prediction typically use sine and cosine functions to do position encoding, which fail to capture the spatial and temporal dependencies and do not contain the graph structure information. In this paper, we propose a novel model named Spatial-Temporal Graph ATtention networks (STGAT), which leverages structure-aware self-attention mechanism to predict future traffic flow. The model introduces temporal multi-head self-attention modules, and designs spatial multi-head graph self-attention modules with structure-aware graph filters to extract more temporal and spatial information. Besides, our model adopts temporal and spatial position embedding layers to capture the spatial-temporal dependencies in traffic flow data. Experimental results show that STGAT shows better prediction performance than the state-of-art models on three real-world datasets PEMS04, PEMS07 and PEMS08. For example, we observe up to 10.38% improvement in terms of Mean Absolute Percentage Error (MAPE) compared with the well-known model ASTGNN.

The three-dimensional deployment of Unmanned Aerial Vehicles (UAVs) has attracted extensive attention, especially for the Internet of Vehicles (IoV) in an emergency or to help the overloaded edge servers in traffic peaks. However, most existing works assume a two-dimensional road to simplify the design and modeling, while ignoring the interchange bridges scenario. In this scenario, UAVs deployment will face new challenges: the line-of-sight (LoS) transmission between the vehicles and UAVs is weakened due to the occlusion of the bridge body and vehicle movement. Meanwhile, energy consumption and the quantity of UAVs also need to be considered. In this paper, we propose an energy-aware 3D-deployment of UAVs, named 3D-UAV, to guarantee a high uplink rate with a minimized number of UAVs in IoV with Highway Interchange. First, considering the channel gain over bridges, 3D-UAV divides vehicles into several clusters. In each time slot, the number of clusters is iteratively optimized. Based on the clustering result, the flight altitude of the UAV is optimized in a stochastic gradient ascent (SGA) way aiming at maximizing the average uplink rate of transmission. Numerical results show that the proposed 3D-UAV can cover all vehicles on the highway interchange with the number of UAVs close to the theoretical lower bound. Meanwhile, it outperforms SOA, DRL, and HOLD methods in terms of the uplink rate and energy.

Mobile Edge Computing (MEC) has attracted attention for its short-range and low-latency computing services for the Internet of Vehicles (IoV). However, in the Vehicle-RSU-MEC environment, incomplete task migration is a problem when Vehicle Users(VUs) are moving at high speeds around the Road Side Units (RSUs). Additionally, during peak traffic periods or road congestion, completed tasks compete for MEC server computing resources, leading to load imbalance. Therefore, making reasonable migration and offloading decisions is an important challenge. To address this challenge, the paper proposes a Cooperative Offloading strategy to jointly optimize offloading Decisions and Allocation of computing resources (CODA) step by step. First, to solve the problem of incomplete task migration, CODA proposed a Greedy-Based Task Completion Migration (GBTCM) algorithm. The algorithm calculates the required RSU set for each task to achieve complete migration, and greedily searches for the optimal migration target in the corresponding set to reduce task transmission latency. Second, after completing the task migration, CODA proposed a Distance-Based Computing Resource Allocation (DBCRA) algorithm to achieve load balancing for MEC servers. The algorithm prioritizes distance and finds MEC servers with sufficient computing resources to achieve better load balancing performance. Experimental results have shown that CODA is a low-complexity algorithm applicable to IoV, which can make reasonable and rapid decisions for task migration and offloading. Compared to three other benchmarks, CODA exhibits higher effectiveness and superiority.

Low-latency data service is an increasingly critical challenge for data center applications. In modern distributed storage systems, proper data placement helps reduce the data movement delay, which can contribute to the service latency reduction tremendously. Existing data placement solutions have often assumed the prior distribution of data requests or discovered it via trace analysis. However, data placement is a difficult online decision-making problem faced with dynamic network conditions and time-varying user request patterns. The conventional static model-based solutions are less effective to handle the dynamic system. With an overall consideration of data movement and analytical latency, we develop a reinforcement learning-based framework DataBot+, automatically learning the optimal placement policies. DataBot+ adopts neural networks, trained with a variant of$Q$-learning, whose input is the real-time data flow measurements and whose output is a value function estimating the near-future latency. For instantaneous decision making, DataBot+ is decoupled into two asynchronous production and training components, ensuring that the training delay will not introduce extra overheads to handle the data flows. Evaluation results driven by real-world traces demonstrate the effectiveness of our design.

Security and forensics represent two key components for network management, especially to guarantee the trusted operation of massive access networks such as the Internet of Things (IoT). As a core technology to provide low latency and high communication for IoT, Mobile Edge Computing (MEC) pulls computing resources from remote cloud centers to devices. The process of MEC service involves three types of entities: devices, data generated by devices and digital evidence generated after the data interaction. These entities are fully distributed and difficult to protect through traditional, highly centralized security and authentication mechanisms. As a decentralized shared ledger and database, the emerging blockchain is considered to provide cooperative trust and collaborative action among multiple subjects while ensuring the integrity and confidentiality of data. Because of its anonymity, non-tampering and traceability, the blockchain arouses research on the combination of blockchain and edge computing for device security, data security and forensics in IoT. This survey analyzes the application of blockchain in MEC-IoT systems and mainly focuses on approaches and technologies to manage the security and forensics issues for IoT. Finally, we present open issues and prospects for future work and research directions.

For massive access to the Internet of Things, edge computing servers are installed on cellular ground base stations (GBSs) with fixed geographical locations, which easily suffer from traffic overload of the end user (EU) with high density and mobility. To provide reliable and flexible offloading service, unmanned aerial vehicles (UAV) are explored to assist edge computing, which relieves the computation offloading pressure of both EUs and GBS. However, most existing UAV researches focus on trajectory design to reduce offloading delay, which ignoring the variability of user distribution and the energy limitation of UAV. This article proposes a novel UAV-assisted edge computing framework, named as HOTSPOT, which locates the UAV in 3-D space according to the time-varying hot spot of user distribution and provides the corresponding edge computing offloading assistance. By formulating the UAV positioning problem into a maximum clique problem, a light-weighted deterministic algorithm is proposed based on stochastic gradient descent to search the optimal location of UAV. With the elaborate UAV position, HOTSPOT further gives an opportunistic offloading balanced scheme to reach low latency. Simulation results show that when the GBS load is 75%, HOTSPOT reduces the average offloading delay by 33%. When the GBS load reaches 90%, the average delay reduction is up to 80%.

Mobile-edge computing (MEC) is expected to provide reliable and low-latency computation offloading for massive Internet of Things (IoT) with the next generation networks, such as the sixth-generation (6G) network. However, the successful implementation of 6G depends on network densification, which brings new offloading challenges for edge computing, one of which is how to make offloading decisions facing densified servers considering both channel interference and queuing, which is an NP-hard problem. This article proposes a distributed-two-stage offloading (DTSO) strategy to give tradeoff solutions. In the first stage, by introducing the queuing theory and considering channel interference, a combinatorial optimization problem is formulated to calculate the offloading probability of each station. In the second stage, the original problem is converted to a nonlinear optimization problem, which is solved by a designed sequential quadratic programming (SQP) algorithm. To make an adjustable tradeoff between the latency and energy requirement among heterogeneous applications, an elasticity parameter is specially designed in DTSO. Simulation results show that compared to the latest works, DTSO can effectively reduce latency and energy consumption and achieve a balance between them based on application preferences.

Existing image annotation methods that employ convolutional features of deep learning methods from the Internet of Things (IoT) have a number of limitations, including complex training and high space/time expenses associated with the image annotation procedure. Accordingly, this paper proposes an innovative method in which the visual features of the image are presented by the intermediate layer features of deep learning, while semantic concepts are represented by mean vectors of positive samples. Firstly, the convolutional result is directly output in the form of low-level visual features through the mid-level of the pre-trained deep learning model, with the image being represented by sparse coding in the IoT. Secondly, the positive mean vector method is used to construct visual feature vectors for each text vocabulary item, so that a visual feature vector database is created. Finally, the visual feature vector similarity between the testing image and all text vocabulary is calculated, and the vocabulary with the largest similarity is taken from the IoT as the words used for annotation. Experiments on multiple datasets demonstrate the effectiveness of the proposed method; in terms of F1 score, the proposed method's performance on the Corel5k and IAPR TC-12 datasets is superior to that of MBRM, JEC-AF, JEC-DF, and 2PKNN with end-to-end deep features.

In modern integrated circuits, the clock power contributes a dominant part of the chip power. Clock power can be reduced effectively by utilizing multi-bit flip-flops. In this paper, a parameterized timing-aware flip-flop merging algorithm is proposed for clock power reduction. The single-bit flip-flops are merged into multi-bit flip-flops after placement & optimization and before clock network synthesis with consideration of function information, scan chain information, distance and timing constraints. The algorithm can be configured with different parameters, such as the bit-number of MBFF, the setup timing margin and the distance margin. Experimental results under an industrial design show that compared with the basic design without MBFF, the design with 2-bit, 4-bit, 6-bit, and 8-bit MBFFs can save 7.5%, 12%, 11.8% and 11.1% total power consumption respectively. Using MBFF4 to replace 1-bit FFs is the best choice for the design optimization, which achieves minimum area and total power consumption. We also compare the designs with MBFF4 replacement under five different setup timing margins and distance margins. Without violating any timing constraint, it is better to set the setup timing margin as small as possible to achieve best power optimization. The distance margin (I00μm, 30μm) is the best choice for this industry design to achieve minimum power consumption.

Low-latency data access is an important challenge for data center networks. Proper placement of the data items can reduce the data travel time in the distributed storage systems, which contributes significantly to the latency reduction. Most existing data placement approaches have often assumed the prior distribution of data requests or discovered so through trace analysis. However, the traditional static model-based solutions are less effective to handle the system uncertainties in a dynamic environment. We present DataBot, a reinforcement learning-based adaptive framework, to learn the optimal data placement policies faced with the dynamic network conditions and time-varying request patterns. DataBot utilizes a neural network, trained with a variant of Q-learning, whose input is the realtime data flow measurements and whose output is a value function estimating the near-future latency. For rapid decision making, DataBot is divided into two decoupled production and training components, ensuring that the convergence time of the training will not introduce more overheads to serve the read/write requests. Evaluation results demonstrate that the average write and read latency of the whole system can be lowered by about 35% and 40%, respectively.

In modern Multi-Processors System-on-Chip (MPSoC), it is highly desirable to provide hardware support for efficient multicast traffic. Recently, bufferless router has become a promising solution for NoC due to its simplicity and low overhead. However, existing multicast bufferless routers utilize the serialized switch allocator to allocate both unicast and multicast packets based on the packet priority one by one, which makes the router have a long critical path and lowers the frequency of the router. In this paper, we propose a low-overhead multicast bufferless router with a reconfigurable Banyan network (called Banyan_PR, PR is short for packets replication). The Banyan switch of the router can be configured as four modes (straight, exchange, U-multicast and L-multicast) according to the type of the incoming packets. For the U-multicast and L-multicast configurations, the multicast packet can be replicated adaptively to reduce the multicast latency. Using a 4 × 4 Banyan network instead of the serialized switch allocator, the Banyan_PR router has shorter critical path length and less area overhead. Synthesis results under a 28nm technology show that the Banyan_PR router can achieve the frequency of 1GHz and save 65% less area and 89% less power consumption than the existing deflection-routing-based multicast bufferless router (called DRM PR all) with the serialized switch allocator. Simulation results illustrate that the Banyan_PR router achieves 25%, 28% and 19% less latency on average than that of the router without packets replication (called Banyan_noPR) and 39%, 42% and 35% less latency on average than that of the DRM_PR_all router under three synthetic traffic patterns respectively.

Coverage of interest points and network connectivity are two main challenging and practically important issues of Wireless Sensor Networks (WSNs). Although many studies have exploited the mobility of sensors to improve the quality of coverage and connectivity, little attention has been paid to the minimization of sensors' movement, which often consumes the majority of the limited energy of sensors and thus shortens the network lifetime significantly. To fill in this gap, this paper addresses the challenges of the Mobile Sensor Deployment (MSD) problem and investigates how to deploy mobile sensors with minimum movement to form a WSN that provides both target coverage and network connectivity. To this end, the MSD problem is decomposed into two sub-problems: the Target COVerage (TCOV) problem and the Network CONnectivity (NCON) problem. We then solve TCOV and NCON one by one and combine their solutions to address the MSD problem. The NP-hardness of TCOV is proved. For a special case of TCOV where targets disperse from each other farther than double of the coverage radius, an exact algorithm based on the Hungarian method is proposed to find the optimal solution. For general cases of TCOV, two heuristic algorithms, i.e., the Basic algorithm based on clique partition and the TV-Greedy algorithm based on Voronoi partition of the deployment region, are proposed to reduce the total movement distance of sensors. For NCON, an efficient solution based on the Steiner minimum tree with constrained edge length is proposed. The combination of the solutions to TCOV and NCON, as demonstrated by extensive simulation experiments, offers a promising solution to the original MSD problem that balances the load of different sensors and prolongs the network lifetime consequently.

In WiMAX networks with fixed relay stations (FRSs), mobile users move in and out of the coverage area of FRS in different periods of a day. Frequent handover requests generated by population mobility lead to load imbalances among FRSs and low data rate. Mobile relay stations (MRSs), which can shift between FRSs, can share part of the users' requests, then reduce the burden of FRSs. In this paper, we define and study the Minimum Mobile Relay Path selection problem (MMRP), whose objective is to deploy minimum MRSs to patrol FRSs according to their busy durations. To reflect the FRSs' real situation, Markov chains are adopted to predict FRSs' busy durations which are then represented as a weighted graph. Based on this graph, the original problem is transformed into a Minimum Vertex-disjoint Path Cover problem. After analyzing properties of the weighted graph, we propose the algorithms based on the principles of graph searching, maximum matching and the maximum flow, respectively. Theoretical analysis and simulation results show that, compared with traditional search algorithms, solutions based on maximum matching and the maximum flow have lower complexity, yet better performance on the number of paths and system overhead, and the solution using predicted busy durations is superior to those in paths gains whose busy duration is presupposed.

In WiMAX mesh networks based on IEEE 802.16j, when transmission power of the base station (BS) and the number of radios and channels are settled, data rate at the subscriber (SS) is decided by the distance between the SS and its uplink relay station (RS). In this paper, we study the problem of deploying a minimum number of RSs to satisfy all SSs' distance requirements. Firstly, we translate it into a minimum clique partition problem, which is NP-complete. Based on SSs' neighbor information and location information, we then propose two heuristic algorithms based on clique partition, named as MAXDCP and GEOCP, respectively. Simulation results show that, compared with the state-of-the-art MIS and HS algorithms, MAXDCP uses 23.8% fewer relays than MIS with the same time complexity, and GEOCP uses 35% fewer relays than MIS in the same time and 18.5% fewer relays than HS in much less time.

Common deployment schemes in wireless sensor networks (WSNs) are built upon the assumption that the boundary effects can be ignored in the sensing field, which result in additional repair work to detect boundaries and redeem coverage holes along them. This repair not only breaks the uniformity of the deployed network, but also causes extra manual and material costs in practice. According to the geometry characteristics of a target area, we propose an innovative deployment scheme GRLD (Growth Rings Like Deployment), which can achieve coverage as well as connectivity without boundary effects. We also prove the full coverage and connectivity of this scheme and compare its efficiency with some popular regular deployment patterns, such as the square grid and the hexagon grid. Our work is the first to apply biological principles to the study and design of deployment schemes in WSNs, which avoids boundary effects efficiently and provides more adaptability.