This work examines the path planning problem for data collection by an unmanned aerial vehicle (UAV) over clusters of smart poles (or streetlights). The smart poles within each cluster are assumed to be interconnected via wired or wireless links and, thus, the UAV needs to collect data from only one pole in each cluster. A small subset of smart poles is equipped with charging facilities to replenish the UAV’s battery when visited. To minimize the UAV’s total flight distance in a data collection cycle, we first propose the energy-aware minimum distance (EA-MinDist) path planning algorithm based on the dynamic programming principle. The algorithm takes into consideration the UAV’s need to visit charging poles along the path to sustain its travel over these clusters and can be extended to accommodate an infinite number of data collection cycles while maintaining a constant memory requirement. The sequence of visited smart poles converges to a periodic cycle. Alternatively, to reduce the cost of charging, we also propose the energy-aware minimum charging (EA-MinCharge) algorithm, which aims to minimize the total number of charges needed to traverse these clusters. Simulation results demonstrate the efficacy of the proposed algorithms in comparison to several baseline algorithms.

This work examines the use of unmanned aerial vehicles (UAVs) as mobile anchors to determine the locations of ground users based on the received signal strength (RSS). This is motivated by the significance of user location information in search and rescue operations, post-disaster recovery, and wireless communication systems. By utilizing the Cramér-Rao lower bound (CRLB) as a measure of localization accuracy, we jointly optimize the UAV’s flight trajectory and the users’ transmission scheduling for localization. We propose an iterative solution in which the transmission scheduling and trajectory design subproblems are solved in turn until convergence. We utilize a successive convex approximation (SCA) approach to address the non-convexity of the transmission scheduling subproblem and adopt a gradient descent method to solve the UAV trajectory optimization subproblem. Extensive simulation results verify that our proposed solution outperforms various baselines.

Low Earth orbit (LEO) satellite networks have emerged as an efficient solution to offer communications services worldwide, especially to remote areas uncovered by current terrestrial networks. A network with sufficient satellites deployed can connect any two points on the ground. However, routing for multicast requests is more challenging due to the inherent mobility of LEO satellites. This paper aims to design the shortest routes for multicast requests while reducing the number of link handovers. The formulated problem appears to be an NP-hard problem. We first propose a low-complexity heuristic algorithm, the Minimum Handover Tree (MHT) algorithm, to find a suboptimal solution efficiently. We then further design a Multicast Tree Size Aware Handover (MTSAH) algorithm to improve the MHT algorithm in the tree size. The simulation results demonstrate that our proposed solutions outperform several baselines in the existing work.

The use of UAVs for logistics services has become a highly regarded application in recent years. This paper studies the package pickup and delivery problem with multi-commodity and multi-visits. Due to the limited load, the UAV has to operate within the load limit when performing package delivery services. In addition, we allow the UAV to visit a location multiple times during the mission. Our objective is to minimize the total flying distance of the UAV. Since the problem is NP-hard, we propose a two-phase heuristic algorithm to solve this problem. First, the trajectory of the UAV to pick up or deliver packages is constructed using a greedy algorithm. Second, we optimize the previously built trajectory to obtain a shorter flying distance for the UAV. The simulation results show that the proposed algorithm outperforms the baselines regarding total flight distance and execution time.

This work examines the trajectory design and energy charging strategy of a data-gathering unmanned aerial vehicle (UAV). The UAV utilizes laser charging from high-altitude platforms (HAPs) to replenish its battery, enabling sustained travel across multiple data-gathering points. The trajectory is determined by a sequence of hovering positions at which the UAV stays to perform both data collection and energy charging. The UAV's hovering positions affect both the sensors’ transmission rates and the laser-charging efficiency. To minimize the total task completion time, it is necessary to choose hovering positions that consider both data upload and energy charging times. In this work, we first propose the Minimum Completion Time Trajectory and Charging Optimization (MinTime-TCO) algorithm, where the hovering positions and charging energies are optimized in turn using a block coordinate descent approach. Given the UAV's hovering positions, we propose the Minimum Charge Rate Search (MCRS) algorithm to optimize the charging energies at these positions. We show that MCRS is optimal in terms of minimizing the total task completion time. Then, given the charging energies, we propose the Hovering Position Optimization (HPO) algorithm, employing successive convex approximation to address the non-convexity of the optimization problem. We also propose a low-complexity alternative based on dynamic programming to further reduce computational complexity. Simulation results demonstrate the effectiveness of the proposed algorithms against several baseline strategies.

New radio (NR) and non-orthogonal multiple access (NOMA) offer scalable and efficient resource allocation in Beyond 5G (B5G) networks. NR implements mixed numerology with flexible frame structures for future compatibility, whereas NOMA allows users with different channel states to share an identical Physical Resource Block (PRB). Multi-connectivity enables a user to connect to multiple networks for reliability, and multicast conveys data to users simultaneously that request the same content. However, resource allocation in the NOMA-based mixed numerology system with multi-connectivity for multicast remains unexplored. The problem is challenging due to 1) the different shapes of PRBs in NR and 2) the shared locations of PRBs in a frame with NOMA. In this paper, we formulate a new optimization problem, named Multicast, Multi-connectivity, and Multi-Dimensional Resource Allocation Problem (M3DRAP), and prove its NP-hardness and inapproximability. We propose an approximation algorithm for general M3DRAP with the ideas ofMulticast Inter-Numerology Relation,Layer Dissimilarity,Subgrouping Nonuniformity, andSegmentation Preference. To find the intrinsic properties of PRB allocation for multicast in NOMA-based networks, we consider a single B5G usage scenario (e.g., eMBB, URLLC, or mMTC) and propose another approximation algorithm. Simulations demonstrate our algorithms improve the weighted sum rate by over 50% and increase the user satisfaction ratio by 1.5x.

Recently, Federated Learning (FL) has realized Artificial Intelligence of Things (AIoT) applications to train a shared model while preserving user privacy collectively. However, the legacy FL framework performance is fundamentally threatened by scale limitation, non-independent and identically distributed (non-IID) data, and communication costs. Therefore, we propose VIrtual-targeted SequentIal Training with Hierarchical Federated Learning (VISIT), a novel framework to systematically distribute clients to suitable clusters for balancing data distributions among all FL subgroups. To the best of our knowledge, this work is the first attempt to introduce a Virtual Target concept along with a key metric, Virtual Target Similarity (VTS), to quantify the data harmonization in the whole HFL system. Based on our insightful Client Set arranging strategy, VISIT can wisely select each FL subgroup member to optimize diversity within each Client Set and similarity across different clusters while preserving user privacy. Numerical results demonstrate that VISIT improves accuracy by 41% and reduces total communication rounds by 82% compared to other state-of-the-art baselines with non-IID data on EMNIST and CIFAR-10 datasets.

With the emergence of new applications for holographic-type communication in healthcare, entertainment, and education, point cloud video transmission has become essen-tial. This paper aims to reduce the bandwidth cost by leveraging tile-based video transmission with point cloud registration in a wireless multicast network. A point cloud video is divided into multiple tiles, and each tile contains a portion of point cloud objects and can be registered by adjacent tiles with some similar objects under the registration rotation and registration overlap constraints. We formulate a new optimization problem and prove that it is NP-hard, and then we design an algorithm Multicast Multi-Tile Registration (MMTR) to select multicasting and registered tiles under consideration of socially related users' preferences with the idea of a tile registration graph. A more popular tile can be multicasted to more friends to minimize the bandwidth cost. Experimental results with real datasets show that MMTR can reduce bandwidth costs by more than 20% and achieve better video quality compared to state-of-the-art point cloud transmission algorithms.

In recent years, mobile edge computing (MEC) has become one of the most popular applications in the Internet of Things (IoT). With the help of satellite communications, MEC can be realized in remote areas. However, when transmitting directly to satellites, the energy consumption of IoT devices remains a challenge. This paper studies an unmanned aerial vehicle (UAV) assisted MEC system in which the UAV and satellite are both feasible MEC servers providing computation services. We aim to minimize the total energy consumption among all IoT devices by jointly determining the offloading decision and UAV's trajectory under the constraint of an energy budget. To tackle the problem, we utilize an existing heuristic algorithm for solving the classic Orienteering Problem and propose a dynamic programming algorithm to reduce the hovering cost of the UAV to serve more IoT devices. Simulation results show that the performance of the proposed algorithm is better than the baselines.

This paper studies how UAVs can efficiently deliver parcels with trucks in rural areas. Due to the limited payload of the UAVs, they can only serve the parcels under the pay-load limitation, and the other parcels are delivered by truck. Furthermore, the battery capacities of the UAVs are limited, and they cannot deliver all parcels at once. The UAV will take off from the truck to deliver parcels and then meet with the truck to load new parcels and change the new battery for the next trip. For UAV safety considerations, the truck must wait at the rendezvous node for the UAV to land. Our paper aims to deliver all the parcels as quickly as possible. Since the problem is NP-hard, we proposed a three-stage heuristic algorithm to solve this problem. The simulation results show that our proposed algorithm outperforms the candidate algorithms in minimizing task completion time.

This work examines the task assignment, transmission scheduling, and trajectory design of image-surveillance UAVs dispatched to serve on-demand image capture and delivery services to ground users, e.g., from drivers seeking images of traffic jams or security units requesting images of private homes. In each task, the UAVs are required to capture the image of a specified surveillance region and deliver the image to the requesting user before the deadline. The task assignment, transmission scheduling, and trajectory design are jointly determined to maximize the total surveillance area of the completed tasks. We first examine the single-UAV problem and propose an alternating optimization approach that adopts the exact penalty method to promote near-binary solutions and employ successive convex approximation to deal with the nonconvex trajectory optimization. Then, we extend to the multiple-UAV scenario where cross-UAV tasks may require images to be captured and delivered by different UAVs. To enable distributed implementation, we introduce auxiliary deadlines to limit the time available for local tasks and, thus, decouple the joint optimization problem into multiple single-UAV problems that can be solved in parallel following the procedure derived in the previous case. Numerical simulations are provided to demonstrate the effectiveness of the proposed solutions.

This paper investigates using multi-connectivity (MC) with mixed numerology to leverage the benefits of both techniques. The scenario we consider involves users connecting to multiple base stations simultaneously, with each user being served by the desired numerology set. The goal is to maximize the utility function, considering network throughput and satisfaction rate. To achieve this goal, we present an integer non-linear programming (INLP) problem and propose a multi-connectivity resource allocation (MCRA) heuristic algorithm. Moreover, a Speed-up MCRA (SMCRA) algorithm is proposed to reduce the time complexity of the MCRA algorithm while maintaining similar performance. Simulation results demonstrate that the proposed algorithms outperform existing methods in terms of both user satisfaction and network throughput.

This work examines the downlink channel assignment for integrated access and backhaul (IAB) networks employing multihop and multi-connectivity operations. Multi-connectivity allows user equipments (UEs) and base stations (BSs) to receive information from multiple upstream BSs and, thus, increases the flexibility of spectrum utilization. We formulate the channel assignment problem as a hierarchical multiple knapsack with discrete fractional assignments problem that aims to maximize the total accommodated data-rate demands of the UEs. We propose a multi-connectivity-aware hierarchical resource allocation (MuCH-RA) algorithm that consists of two stages: a sequential multiple knapsack assignment (SMKA) stage and a UE deselection (UED) stage. The SMKA stage assigns channels to UEs and BSs by solving a sequence of single knapsack problems at the BSs in a bottom-up tier-by-tier fashion, followed by the efficient removal of redundant assignments. The UED stage removes the UEs that could not be fully served and releases their channels for possible reassignment in the next iteration. The proposed MuCH-RA algorithm jointly considers the load and the channel quality of BSs and UEs and, thus, is able to serve larger overall data-rate demands than pure load-based and channel-based greedy algorithms. Numerical simulations are provided to demonstrate the effectiveness of the proposed algorithm.

Federated Learning (FL) allows Internet-of-Things (IoT) devices to train a global model collaboratively and keep their data locally to address privacy concerns. However, the current FL framework has three main drawbacks, high communication cost, single point of failure, and low accuracy on non-independent and identically distributed (non-IID) data. To this end, we propose a novel FL framework, IHC-FL, to 1) group devices into clusters based on communication cost and model distance, 2) distribute model aggregation over cluster heads, and 3) construct a topology to guide cluster heads to exchange model updates. To the best of our knowledge, this paper makes the first attempt to jointly optimize grouping user devices into clusters and exchanging model updates among cluster heads to enhance model performance. The numeric results show that IHC-FL can reduce 38%~89% of total communication cost over time than other heuristics with non-IID data on FMNIST and CIFAR-10 to achieve the target accuracy.

Recently, mobile edge computing (MEC) assisted unmanned aerial vehicles (UAVs) have brought a revolution to the existing precision agriculture (PA). The target UAVs can execute various PA tasks with different heterogeneous resource requirements on the farm. However, due to the stringent service deadline of PA tasks and the battery limitation of UAVs, one of the promising solutions is to offload those computation tasks to MEC servers jointly. This paper explores the MEC-assisted task offloading problem with multi-UAVs under different deadline constraints in uncertain real-world environments. The diverse requirements of PA tasks, the heterogeneous network status, and the dynamic loading of MEC edge servers make the offloading decision an NP-hard problem. Therefore, we propose a reinforcement learning (RL)-based task offloading approach, BANDIT-SCH, to minimize total MEC system costs to achieve online task dispatching and scheduling in uncertain environments without further global information. The experiment results show that the performance of BANDIT-SCH is approximate to the upper bound strategy, which can foresee all edge servers' detailed status.

In this work, we use unmanned aerial vehicles (UAVs) to collect data from IoT devices on the ground. Each device has an amount of data that can be sent to the UAV during a specific time window. Our objective is to maximize the total profit that the UAV can collect the data from the IoT devices. Since the problem is NP-hard, we propose a heuristic algorithm in three stages to solve the problem. We solve the traveling-salesman problem (TSP) in the first stage to find the UAV's flying trajectory. In the second stage, we propose an algorithm to change the visiting order or remove IoT devices from the flying trajectory if we cannot satisfy their time constraints. In the third stage, we improve the UAV's flying distance established in the second stage. The simulation results show that the proposed algorithms outperform some baselines in terms of total profit and execution time.

Promising vehicle-to-everything (V2X) communication technologies can increase road safety by periodically broad-casting Cooperative Awareness Messages (sCAMs) that contain vehicles' status and attribute information, such as time, location, velocity, motion state, and vehicle type, to all nearby vehicles. However, out-of-date information and prediction deviations may cause potential risks and severe vehicle safety problems. In this paper, we propose an efficient safety-aware CAM broadcast rate control algorithm termed DESBRAC for vehicles to consider more safety metrics and determine the CAM broadcast rates cooperatively. Furthermore, we introduce Over-the-Air Computation (AirComp) to help vehicles aggregate information from their nearby vehicles instantly for metric estimation and cooperative CAM broadcast rate determination. Finally, the simulation results based on a simple and a realistic scenarios of vehicular networks show that our algorithm can achieve an improvement of about 31% in driving safety compared to the state-of-the-art algorithms.

With the development of the Internet of Things (IoT), the demand for location-based services in indoor environments proliferates. Channel State Information (CSI) based fingerprint localization has become a research hot spot. However, a compelling method to address this issue does not appear because of the hardship of processing CSI data. Meanwhile, many fingerprint localization algorithms have a time-consuming offline training phase. Therefore, we propose an indoor CSI fingerprint localization system based on the broad learning system (BLS). First, we filter the outliers, generate delegates of CSI by the data nugget algorithm, and use tensor decomposition to reconstruct the CSI delegates. Moreover, we utilize Isometric mapping (Isomap) to extract CSI features to reduce BLS’s complexity. The experimental results show that our scheme outperforms several existing algorithms in two indoor environments.

This work examines a UAV-enabled surveillance mission over multiple restricted regions and aims to determine the optimal UAV trajectory that minimizes the mission completion time. The UAV is prohibited from entering the restricted regions due to government regulations or adversarial concerns. However, during the surveillance of a region, the UAV can move along the region's boundary to reduce its distance to the next region once the local task is completed. To exploit this advantage, we propose a minimum completion time (MinTime) algorithm that first determines the visiting order of the regions by employing an approximate solution of the traveling salesman problem (TSP) and then optimizes the UAV trajectory over the sequence of restricted regions using dynamic programming. In the presence of obstacles, we further propose an obstacle-aware MinTime (OA-MinTime) algorithm that treats each obstacle as an additional restricted region with zero surveillance duration, allowing the UAV to avoid the obstacles in a more efficient manner. A modified TSP solution is also proposed by taking into consideration the additional distance required to circumvent the obstacles on each inter-POI path. Simulation results show that the proposed MinTime and OA-MinTime algorithms can significantly reduce the total completion time compared to conventional minimum-distance approaches.

Satellite networks are a promising way to provide ubiquitous access to network service. However, due to the mobility of satellites, the traditional routing scheme cannot be adapted to the constellation directly. This paper studies the challenge of multicast routing on satellite networks. The mobility of satellites makes the serving satellites of ground users change with time. When performing a multicast on the constellation, the changing of serving satellites leads to many link handover control messages. To minimize the control message overhead is NP-hard. Therefore, a dynamic programming-based algorithm called Dynamic Multicast Tree Selection (DMTS) is proposed to find the sub-optimal result with polynomial time complexity. Besides, we proposed a tree generation algorithm called LMBBSP with DMTS to avoid link congestion in unbalanced network load. The simulation results show that our proposed schemes outperform the baselines with link handover and request rejection rate.

3GPP has defined Dual Connectivity (DC) to allow a user to access a 4G and a 5G base station (BS) simultaneously. However, the resource allocation for DC is challenging because of not only the co-channel interference between 4G and 5G BSs but also different shapes of Resource Blocks (RBs) for New Radio (NR) and the reuse of RBs for Non-Orthogonal Multiple Access (NOMA). In this paper, we formulate Dual Connectivity Multidimensional Resource Allocation Problem and prove that it is NP-hard. We design an approximation algorithm with the ideas of 1) Zone Shaping, 2) Occupancy Indicator and Overlap Degree of RBs, 3) DC Slicing, and 4) DC Inter-Numerology Relation, to maximize the total throughput of heterogeneous user demands in the coexisting 4G and 5G network with NR, NOMA, and DC. Simulation results manifest that our algorithm outperforms the state-of-the-arts regarding throughput and resource efficiency.

With the advances in Social Internet of Things (SIoT) and Federated learning (FL), smart devices are now able to cooperatively and locally perform learning tasks to protect sensitive data by Differential Privacy (DP). On the other hand, Hierarchical FL (HFL) clusters SIoTs into multiple local training groups to reduce communication overheads by local aggregation. In this paper, we explore SIoT Training Group Construction (STGC) for HFL to minimize the total SIoT computation, communication and hiring costs, and the privacy cost for exploiting DP. We prove that STGC is NP-hard and inapproximable within any factor unless P = NP. Then, we design an algorithm with the ideas of Coverage Efficiency Indicator, Data Balance-aware Dual Adjustment, and Privacy-Aware Rerouting to choose and cluster SIoTs and to determine the aggregator for local training and SIoT routing in each cluster. Simulation results manifest that the proposed algorithm outperforms state-of-the-arts regarding the total cost, model accuracy, and convergence time.

The WiFi-based localization approach has been widely used in the indoor environment. This paper proposes a MultIple Fingerprints-based Indoor localization system (MIFI). MIFI is based on the depthwise separable convolution neural network technique and utilizes Unmanned Aerial Vehicle (UAV) to help with transmitting fingerprint data. With the help of UAV, human effort can be decreased. In the training phase, we collect the Channel State Information (CSI) of the reference points. In the testing phase, CSI sent at the test locations are collected by Raspberry PI 4 as the input, then the system will output the predicted location. The experiment results show that MIFI can achieve a higher classification accuracy and mean localization distance error than the baseline work. Compared to the CSI data sent from UAV, only a minor performance is lost due to the drift problems of UAV.

This paper addresses the coexistence problem among multiple wireless body area networks (WBANs), where co-channel interference may occur among different WBANs if the channels are not allocated properly, leading to performance degradation in both energy efficiency and packet transmission reliability. We formulate the channel allocation problem as a graph coloring problem, and develop a solution to increase the co-channel reuse and the number of WBANs with assigned channels. We propose a distributed two-hop incomplete coloring (DTIC) algorithm that adopts a game-theoretic approach to solve the graph coloring problem. The DTIC algorithm exploits two-hop information to enable high channel reuse among two-hop neighbors and allows for incomplete coloring when the number of colors (or channels) is insufficient to color all vertices without conflict. A distributed message-passing protocol is also proposed to achieve collision-free message exchange, and to ensure that consistent coloring information is shared among WBANs. Simulation results show that our proposed algorithm achieves better co-channel reuse and higher throughput than existing methods.

This work examines the use of image surveillance UAVs for relay communication between ground users and a remote base station (BS). UAVs take aerial images of the surveillance region and forward them to the BS while serving the uplink transmission demands of ground users. We first consider the single-UAV scenario and jointly determine the UAV’s trajectory, task assignment, user association, and rate allocation by maximizing the sum-log-throughput of the users subject to constraints on the surveillance coverage, image transmission requirements, and relay capacity. The resulting mixed-integer nonlinear programming problem is solved by an inexact block coordinate descent (BCD) algorithm where we inherit ideas from the exact penalty method for mathematical programming with equilibrium constraints to relax the integer constraints and the successive convex approximation approach to address the non-convexity of the trajectory optimization problem. Then, we extend the proposed framework to the case with multiple UAVs that are dispatched to cover a wide surveillance region. The UAVs may complete both relay and surveillance tasks more efficiently through cooperation and proper task allocation for UAVs. A similar BCD algorithm is adopted to solve the problem. Numerical simulations are provided to demonstrate the effectiveness of the proposed scheme over several baseline methods.

Device-to-device (D2D) communication is one of the promising solutions to improve spectrum efficiency and alleviate the mobile traffic explosion. However, interference mitigation and resource allocation in the underlying cellular network is a challenging task. In this paper, we propose a distributed deep reinforcement learning (DRL) based scheme to solve the interference mitigation and resource allocation problem. According to the channel status, each cellular user (CU) and D2D transmitter (D2D TX) will determine the appropriate reused channel and transmit power to maximize the system throughput. We propose a distributed DRL scheme and integrate two hotbooting algorithms into the scheme to improve the system throughput at the early stage of training. Simulation results show that the proposed distributed DRL with hotbooting outperforms the baselines regarding running time, message overhead, and throughput.

Federated Learning (FL) allows Internet-of-Things (IoT) devices to train a global model collaboratively and circumvent the security issue. However, the current FL framework has three main drawbacks, the huge network overhead, single point of failure, and accuracy degradation in non-independent-and-identically-distributed (non-IID) data distribution. We propose a novel Deep Reinforcement Learning (DRL) based Decentralized Learning (DL) framework, DeepSelect, to 1) reduce the network overhead of conventional FL, 2) construct a good communication topology adaptively to mitigate the effect of non-IID data, and 3) accelerate the DL training by balancing the effects of hitting time (HT) and data bias. Moreover, DeepSelect with a subtly-designed DRL agent is reusable with different levels of non-IID data distributions. To the best of our knowledge, this paper is the first one to indicate that proper neighbor selection for exchanging parameters (not raw data) can counterbalance the data bias's effect and improve the DL convergence with non-IID data. The experiment results show that DeepSelect can reduce 18%-51% training rounds than the other heuristics on FashionMNIST and CIFAR-10 with non-IID data distributions.

Social Internet of Things (SIoT) has become an emerging network paradigm, where IoT devices with Artificial Intelligence (AI) and social relations can automatically establish a collaborative group to identify events locally. On the other hand, mobile users can act as ubiquitous and versatile sensors to improve the accuracy of SIoT event detection. In this paper, we explore the SIoT Collaboration with Crowdsourcing (SCC) problem to jointly select SIoT devices and hire users to monitor events and locations with accuracy requirements, while minimizing the total SIoT communication and computation costs and the user hiring cost. We prove that SCC is NP-hard and cannot be approximated by any factor unless P = NP. Then, we propose a new algorithm, Accuracy- and Social-aware SIoT and User Selection (ASSUS), with the idea of Collaborative Tree (CT) and Accuracy Profit (AP), where CT exploits users’ social relations to properly choose intermediate SIoTs. Simulation results manifest that ASSUS can effectively reduce more than 50% of the total cost compared with state-of-the-art algorithms.

Deep Neural Networks (DNNs) are widely used to analyze the abundance of data collected by massive Internet-of-Thing (IoT) devices. The traditional approaches usually send the data to the cloud and process the DNN inference on the powerful cloud servers but suffer from long network latency. Therefore, edge computing has emerged to reduce network latency by offloading the computation from the cloud to the edge. However, a single resource-constrained edge device is unable to process real-time DNN inference. Thus, we devise a collaborative edge computing system CoopAI to distribute DNN inference over several edge devices with a novel model partition technique to allow the edge devices to prefetch the required data in advance to compute the inference cooperatively in parallel without exchanging data. Subsequently, we present a new optimization problem to minimize the completion time of distributed DNN inference. An innovative algorithm is then proposed to intelligently partition the model into the proper number and sizes of blocks, deploy them on a suitable number of edge devices, and run them in different rounds. The numerical results manifest that our algorithm outperforms the traditional approach by 20%−30% on the completion time.

In recent years, the Ultra-wideband (UWB) system has been investigated for indoor localization and navigation by academia and industry. However, the UWB localization accuracy deteriorates when the signal propagates under severe non-line-of-sight (NLoS) conditions. We use two deep learning network models, the long short-term memory (LSTM) network and deep neural network (DNN), to analyze five different UWB signal features. The five features are received signal strength indication (RSSI), time of arrival (ToA), time difference of arrival (TDoA), first path (FP) amplitude from channel impulse response (CIR), and metric Mc (the ratio of the first path amplitude to peak amplitude). Then, we combine the five features into six different datasets for our deep learning models. Based on the prediction accuracy of the deep learning models for each combined feature, we propose a weighted indoor positioning (WIP) algorithm. The experiment results show that the WIP algorithm has better positioning accuracy than baseline works.

A traditional 4G handover algorithm that performs well in a macro-cell-only network could not be employed in the 5G network with the random distribution of small base stations due to the irregular change of the signal-to-interference-plus-noise ratio (SINR) of a moving user equipment (UE). Besides, the fuzzy logic is a well-known method to translate the domain knowledge of a human expert into a set of basic rules and to formalize the uncertainty judged by the human expert. In this paper, based on the fuzzy logic, we make the first attempt to propose a handover algorithm for a UE in 5G networks. Simulations show that our algorithm has a good performance in terms of the radio link failure (RLF) rate and the ping-pong rate in a 5G network, as compared with the state-of-the-art methods.

In the literature, there are several well-known periodic channel hopping (CH) sequences that can achieve maximum rendezvous diversity in a cognitive radio network (CRN). For a CRN with N channels, it is known that the period of such a CH sequence is at least N2. The asymptotic approximation ratio, defined as the ratio of the period of a CH sequence to the lower bound N2when N → ∞, is still 2.5 for the best known CH sequence in the literature. An open question in the multichannel rendezvous problem is whether it is possible to construct a periodic CH sequence that has the asymptotic approximation ratio of 1. In this paper, we tighten the theoretical gap by proposing CH sequences, called IDEAL-CH, that have the asymptotic approximation ratio of 2. For a weaker requirement that only needs the two users to rendezvous on one commonly available channel in a period, we propose channel hopping sequences, called ORTHO-CH, with period (2 p+1) p, where p is the smallest prime not less than N.

With the population of mobile phones, the telecom company has a user's cellular phone signals and its movement trajectory. So, the company can learn about the user's activity habits and predict where the user may go next to meet the need of network resource and service management. In this paper, we propose a mobility prediction framework with Many-to-one Recurrent Neural Network (RNN). First, we extract the place that the user frequently visits (i.e., Points of Interest (POI)) from the user's mobility data through our proposed POI mining method, i.e., acceleration clustering. Then, we propose an adaptive mapping method to map the user's trajectory to a series of POI. Afterward, we use the RNN with Long Short-Term Memory to learn the user's POI series. Finally, we evaluate the prediction performance of the proposed scheme on two different real datasets. The performance shows that the prediction accuracy of our scheme outperforms previous works.

This work examines the deployment of multiple fixed-wing unmanned aerial vehicles (UAVs) for data-gathering from ground IoT devices, and the corresponding device association policy. Each UAV is assumed to hover above its associated devices following a circular trajectory. The device association and the UAVs' trajectory centers and radii are jointly optimized to maximize the energy-savings relative to a constant transmission power scheme. Given the trajectory centers and radii, the device association problem is modeled as a multiple 0-1 knapsack problem, taking into consideration the load demands of different devices as well as UAVs' service capacities. A two-stage maximum energy-saving device association policy is proposed, where each UAV first solves a single knapsack problem based on all connectable devices, and then resolves conflict with others by a maximum profit assignment. Moreover, given the device association, the UAVs' trajectory centers and radii are optimized by an iterative load-balancing algorithm, where the trajectory centers are chosen as a load-dependent weighted sum of the associated devices' locations. The device association and the UAV deployment are optimized in turn until convergence. Simulation results show that our proposed schemes outperform candidate algorithms in terms of the total energy-savings of IoT devices.

New radio (NR) and non-orthogonal multiple access (NOMA) have emerged for more scalable and efficient resource utilization in 5G. NR implements mixed numerology with a flexible radio frame structure to ensure forward compatibility for future services, whereas NOMA allows multiple users with different channel states to share identical radio resources. However, the resource allocation in the NOMA-based mixed numerology system is challenging due to the naturally different shapes of Physical Resource Block (PRB) for NR and the reused locations of PRBs in a radio frame for NOMA. In this paper, we formulate a new optimization problem Multi-Dimensional Resource Allocation Problem (MDRAP) and prove that MDRAP is NP-hard. To solve the problem, we propose an approximation algorithm to maximize the weighted sum rate under the heterogeneity of users. The algorithm includes Zone Displacement to displace the locations of allocated PRBs in different layers of the radio frame, and Zone Allocation to change the location of the bounded rectangles (i.e., zones) for the allocation in each layer. We design Layer Dissimilarity to examine the location and shape of PRBs for avoiding inter-numerology interference between different layers. Simulation results show that the proposed algorithm outperforms state-of-the-art algorithms regarding throughput and fairness.

Inference acceleration has drawn much attention to cope with the real-time requirement of artificial intelligence (AI) applications. To this end, model partition for Deep Neural Networks (DNN) has been proposed to utilize the parallel and distributed computing units. However, the previous works focus on the load balancing among servers but may overlook the interplay between the computing and communication. This issue makes the existing approaches less efficient especially in mobile edge networks at which smart devices usually with limited computing capacity have to offload the tasks via limited bandwidth capacity to nearby servers. In this paper, therefore, we innovate a new system and formulate a new optimization problem, CONVENE, to minimize the completion time of inference for the smart devices with one or more antennas. To explore the intrinsic properties, we first study CONVENE with Single Antenna and derive an algorithm termed THREAD-SA to foster the optimum solution. Then, an extension, THREAD, is proposed to subtly utilize multiple antennas to further reduce completion time. Simulation results manifest that our algorithm outperforms others by 100%.

Recently, the notions of partitioning the Deep Neural Network (DNN) model over the multi-level computing units and making a fast inference with the early- inference technique have been proposed to shorten the inference time. Such computing units form a hierarchical mobile network to provide locality-aware computation, and the early-inference technique allows the prediction results to early exit the model with a probability. However, an inadequate model partition and misapply early inference may prolong response time. Previous studies focus on the classifier design for early inference, and thus, the optimal model partition with classifier deployment has not been explored. In this paper, we study DEMAND-OPE to consider response time and throughput. We first design the COLT for the simplified DEMAND-OPE without Optional Exit Points (DEMAND) to carefully balance the computing time and data transfer time. Then, an extension termed COLT- OPE is developed to achieve the lower response time. Simulation results show that our algorithms (COLT- OPE) outperform previous methods by 200%.

This work proposes power-efficient trajectory adjustment and temporal routing algorithms for a network of unmanned aerial vehicles (UAV) that are deployed to monitor or gather data from underlying sensors in the field. Here, we consider fixed-wing UAVs that are assumed to follow circular trajectories whose radius can be adjusted to reduce power consumption while maintaining coverage over its responsible service area. Given the multihop transmission paths from the UAVs to the data-gathering node, power-efficient flight-radius adjustment strategies are proposed based on the total power minimization and lifetime maximization criteria while maintaining the existence of the paths. Then, by establishing the relationship between routing in UAV networks and that in general temporal graphs, we propose a power-efficient (PE) temporal path algorithm based on the minimization of the accumulated square of the minimum achievable powers of all UAVs on the path. Computer simulations are provided to demonstrate the effectiveness of the radius adjustment strategies in terms of both total power minimization and lifetime maximization, and the power-savings provided by the PE temporal path algorithm.

Incentivizing the device-to-device (D2D) users can promote co-operative communication between them. In this work, we consider a scenario, where a content provider who wish to propagate his message, seeks base station's (eNB) assistance to advertise. The eNB will incentivize D2D users (DUs) to relay the message among its neighbors that have subscribed the messages. Consequently, the content provider will pay revenue to the eNB when the messages reach the subscribed DU. In this context, our objective is to maximize the revenue of the eNB, considering that the revenue collected by each message has a limited budget. We propose two algorithms to solve the problem. The experimental results show that the proposed algorithms perform well in terms of collected profit while comparing to the candidate algorithms.

The massive usage of Internet-of-Things devices in various smart applications enables spectrum scarcity issues. In order to enhance the dynamic spectrum capability, cognitive radio network (CRN) is considered as a key technology to address the spectrum scarcity problem. However, the establishment of a common communication channel in CRN by considering the unlicensed heterogeneous devices in an asynchronous environment is a challenging problem. In this paper, a novel asymmetric asynchronous channel hopping mechanism is designed, where secondary users have different sets of available channels and can enter into the network without any global clock synchronization. The proposed algorithms can guarantee the rendezvous within a small interval of time with minimum inter rendezvous intervals. Simulation results show that the designed protocol outperforms over the existing channel hopping algorithms in terms of the degree of rendezvous, average time to rendezvous and throughput.

In this paper, we propose a fast rendezvous algorithm for a heterogeneous cognitive radio network (CRN), where each user might have more than one radio. One of the wellknown problems for most multi-radio rendezvous algorithms in the literature is that they are not backward compatible to users with only one radio. To tackle this backward compatibility problem, our approach is a hierarchical construction that groups several time slots into an interval and proposes a novel algorithm to emulate two radios with a single radio in an interval. By doing so, at the interval level, each user behaves as if it had (at least) two radios. For the two-user rendezvous problem in a CRN with commonly labelled channels, the interval length is chosen to be 2M time slots, where = 2 ⌈log2(⌈log2N⌉)⌉ + 10. We show that the maximum time-to-rendezvous (MTTR) of our algorithm is bounded above by 18M⌈n1/m1⌉ . ⌈n2/m2⌉ time slots, where 1 (resp. 2) is the number of available channels to user 1 (resp. 2), and 1 (resp. 2) is the number of radios for user 1 (resp. 2). For the setting that each user is equipped with only one radio and two available channels, our MTTR bound is only and that improves the state-of-the-art bound 16(⌈log2log2N⌉ + 1) in the literature. By conducting extensive simulations, we show that the expected time-to-rendezvous (ETTR) of our algorithm is also better than the two commonly used multi-radio algorithms, JS/Independent and JS/Parallel, in most parameter settings.

Irregular spectrum usage and spectrum scarcity in emergency situations is a common problem in industrial wireless networks. To enhance the dynamic spectrum usage, cognitive radio network (CRN) is introduced in various automotive industrial wireless applications named as industrial cognitive radio network (ICRN). However, establishing the control channel by using channel hopping mechanism in ICRN is a challenging problem. In order to achieve reliable performance in ICRN, efficient channel hopping protocols need to be designed. In this paper, two channel hopping protocols are designed for the ICRN with or without the global clock synchronization to maximize the degree of rendezvous within the shortest time, minimize the inter rendezvous intervals and to reduce the maximum time to rendezvous by two secondary users. Performance evaluation of our protocols outperform in terms of throughput, percentage of rendezvous and average time to rendezvous over existing CRN protocols.

In cognitive radio networks (CRNs), secondary users can utilize the temporary unused spectrum opportunistically without affecting the quality of services of the licensed users, also called primary users. It is a fundamental operation for a user to rendezvous with another user on the same channel and establish a communication link. Traditional rendezvous algorithms assume homogeneous CRNs and each user equipped with a single radio. In recent years, the cost of wireless transceivers has fallen dramatically. It is more feasible for users to apply multi-radio to reduce the time to rendezvous significantly. In this paper, we propose a Chinese Remainder Theorem (CRT) based multi-radio rendezvous (CMR) algorithm for oblivious rendezvous problem in heterogeneous CRNs, where 1) there is no universal labelling of the channels; 2) users' clock are not synchronized; and 3) users have heterogeneous spectrumsensing capabilities. Our CMR scheme applies CRT to achieve fast rendezvous. Simulation results show that CMR has better performance than the previous works.

In software-defined networking (SDN), network rules are installed in ternary content-addressable memory (TCAM). TCAM is a scarce and expensive resource which is a bottleneck for scaling SDN. Rule distribution is a strategy to solve the TCAM shortage problem, which decomposes a large table stored at network ingress into a number of smaller sub-tables and distributes them across network switches. Rule distribution includes two sub-problems, sub-table allocation, and table decomposition. Sub-table allocation is to guarantee that each flow path passes all the partitioned sub-tables and maximize the number of partitioned sub-tables (for reducing the size of sub-tables). Table decomposition problem is to partition a large rule table into a number of balanced sub-tables and reduce the rules overhead. In this paper, we propose a sub-table allocation algorithm and size-balancing sub-table partition algorithm. Simulation results show that the performance of both algorithms is better than previous works in terms of reducing the TCAM entries used in each switch.

In this paper, we study a new problem called probabilistic k-weighted coverage placement, which is a generalization of the Q-coverage placement. Q-coverage placement assumes that the monitored area has uniform coverage requirement: events within the monitored area should be detected with probability Q × 100% (i.e., detected by Q sensors), while probabilistic k-weighted coverage placement assumes that the monitored area has k-degrees of coverage requirement (i.e., k kinds of detection probability): events within distinct region of the monitored area are detected with distinct detection ability, i.e., one of the k kinds of detection probability. Besides, Q-coverage placement requires that the coverage requirement is integer multiple of 100% detection probability, while probabilistic k-weighted coverage placement allows coverage requirement to be non-integer multiple of 100% detection probability. We derive a lower bound on the number of sensors needed to satisfy the coverage requirement of a probabilistic k-weighted monitored area, and introduce a greedy algorithm to solve the problem.

Software-Defined Networking (SDN) is an emerging architecture and offers advantages over traditional network architecture, while there exist some scalability challenges. In this paper, we propose a multicast routing algorithm for SDN with segment routing to serve the bandwidth requirement of a multicast routing request. Our algorithm considers the balance of traffic load for network resource of link bandwidth and node flow entries both. Simulation results show that the performance of our algorithm is better than previous works in terms of average network throughput and average rejection rate of routing requests. Besides, the results also show that our multicast architecture improve scalability problem of original SDN model in terms of number of flow entries used.

In cognitive radio networks, unlicensed users [secondary users (SU)] need to rendezvous on licensed channels before establishing communication links. Dedicated common control channel is the simplest way to achieve rendezvous. However, due to the absolute priority of licensed users [primary users (PU)] on accessing licensed channels, a dedicated common control channel may cause the PU long-time blocking problem, and the control channel saturation problem in a high SU density environment. Channel hopping schemes have been proposed to avoid the problems mentioned above. In this paper, we introduce two quorum-based channel hopping schemes. Our schemes outperform in terms of the four metrics: maximum time to rendezvous, channel loading, degree of rendezvous, and maximum conditional time to rendezvous.

In software-defined networking, flow tables of OpenFlow switches are implemented by ternary content addressable memory (TCAM). Although TCAM can process input packets in high speed, it is a scarce and expensive resource providing only a few thousands of rule entries on a network switch. Rules caching is a technique to solve the TCAM capacity problem. However, the rule dependency problem is a challenging issue for wildcard rules caching where packets can mismatch rules. In this paper, we use a cover-set approach to solve the rule dependency problem and cache important rules to TCAM. We also propose a rule cache replacement algorithm considering the temporal and spatial traffic localities. Simulation results show that our algorithms have better cache hit ratio than previous works.

In Wireless Sensor Networks (WSNs), the presence of congestion can increase the ratio of packet loss, energy consumption and reduce of the network throughput. Especially, this situation will be more complex in Internet of Things (IoT) environments, which is composed of thousands of heterogeneous nodes. In this paper, we address the congestion problem between child and parent nodes in RPL-enabled networks, which typically consist of low power and resource constraint devices. We use game theory strategy to design a parent-change procedure which decides how nodes changing their next hop node toward sink to mitigate the effect of network congestion. Comparing to the Contiki RPL implementation, the simulation results show that our protocol can achieve more than twofold improvement in packet loss rate and throughput with similar average hop count.

Software-Defined Networking (SDN) is a new approach to design, build and manage computer networks. Multicast is used to transmit the same video file to different users. In this paper, we propose two multicast algorithms to solve the multicast problem in SDN environment. Both algorithms consider the balance of bandwidth utilization and communication delay between the source and clients. Simulation results show that our algorithms can improve the network bandwidth utilization and successful rate of the multicast requests than the previous works.

It is a great honor to extend our personal greeting to each and every one of you who are attending the 20th IEEE International Conference on Parallel and Distributed Systems (IEEE ICPADS 2014) in the wonderful city of Hsinchu. Since established in 1992, this is the fourth time we have this conference in Hisnchu, Taiwan. ICPADS has been a major international forum to bring together scientists, engineers, and users from all over the world to discuss and exchange the advancement in of parallel and distributed systems technology.

In cognitive radio networks, the Secondary Users (SUs) are allowed to utilize unused portions of the licensed spectrum to enhance the performance and efficiency of the channel resource in networks. However, with the increasing number of wireless devices and users competence for the limited channel resource, the channel allocation problem has become an important issue in the cognitive radio networks. Moreover, the interference in communication has become an important factor that affects the efficiency of transmission in cognitive radio networks. In this paper, we proposed an algorithm with game theoretic approach to solve the problem of channel allocations in cognitive radio networks, based on interference aware information between communication pairs. By game theory, the channel allocations of SUs are proposed by their perceived utilities associated with possible actions of neighboring users. The effectiveness of the communication links is determined by the bandwidth of the available channels to the SUs and the heterogeneous interference range between the communication links. Our proposed algorithm can achieve Nash Equilibrium convergence in the game theory.

Recently, cognitive radio (CR) has become a key technology for addressing spectrum scarcity. In CR networks, spectrum access should not interfere the colocate incumbent networks. Due to the requirement above, common control channel approaches, which are widely used in traditional multichannel environments, may face serious CR long-time blocking problem and control channel saturation problem. Although channel-hopping-based approaches can avoid these two problems, existing works still have significant drawbacks including long time-to-rendezvous, unbalance channel loading, and low channel utilization. In this paper, we introduce three channel-hopping approaches, RCCH, ARCH, and SARCH for synchronous and asynchronous environments, respectively. Compared with previous works, our schemes outperform the state of the art in terms of these metrics.

Cooperative communications among nodes is an efficient method to decrease signal fading and interference in MAC layer of wireless Ad hoc networks. However, the previous cooperative MAC protocols are designed for IEEE 802.11b, but not for later standard IEEE 802.11g or 802.11n. To increase performance, improve reliability and reduce energy consumption in communications, we propose a cooperative MAC protocol for IEEE 802.11g and being extended to 802.11n. By partitioning the relays with similar transmission rates into same groups, we can reduce efficiently the time for selecting better relays to help data transmission. Furthermore, we propose a novel retransmission scheme to reduce the retransmission time, while once data transmission is fail, only the relays which have received the data frame will help for retransmission instead of repeating all retransmission cycle. Simulation results show that our proposed protocol outperforms previous work by increasing the throughput and reducing the average delay time in transmission.

Recently, Orthogonal Frequency Division Multiple Access (OFDMA) transmission technique is applied widely in wireless networks because of its high transmission capacity. The IEEE 802.16 standard has also adopted the OFDMA as its access technique. However, the problem of bandwidth resource allocation in time and frequency is essential for efficient utilization of OFDMA system. In this paper, we proposed an approximation resource allocation scheme to improve the downlink bandwidth utilization. In the resource allocation scheme, we sort the requests of users and allocate bandwidth based on dynamic programming strategy which can save the calculation result of subproblems to reduce the executive time of algorithm. In simulations, it is shown that our scheme outperforms the greedy algorithm in bandwidth utilization. Also, we compare our scheme with optimal allocation method, which is implemented by brute force with branch and bound algorithm. The results show that our method outperforms optimal allocation method by bandwidth utilization, stability, and execution time.

This paper proposes the first resource allocation scheme in the literature to support scalable-video multicast for WiMAX relay networks. We prove that when the available bandwidth is limited, the bandwidth allocation problems of 1) maximizing network throughput and 2) maximizing the number of satisfied users are NP-hard. To find the near-optimal solutions to this type of maximization problem in polynomial time, this study first proposes a greedy weighted algorithm, GWA, for bandwidth allocation. By incorporating table-consulting mechanisms, the proposed GWA can intelligently avoid redundant bandwidth allocation and thus accomplish high network performance (such as high network throughput or large number of satisfied users). To maintain the high performance gained by GWA and simultaneously improve its worst case performance, this study extends GWA to a bounded version, BGWA, which guarantees that its performance gains are lower bounded. This study shows that the computational complexity of BGWA is also in polynomial time and proves that BGWA can provide at least 1/ρ times the performance of the optimal solution, where \rho is a finite value no less than one. Finally, simulation results show that the proposed BGWA bandwidth allocation scheme can effectively achieve different performance objectives with different parameter settings.

Asynchronous wakeup schemes have been proposed for ad hoc networks to increase the energy efficiency of wireless communication. The basic idea is to allow a node to sleep when it is idle, and wakeup periodically to check if there are pending transmissions. In this paper, we examine the applicability of asynchronous wakeup schemes to the Mobile Ad Hoc NETworks (MANETs). We discover that, although it is desirable to have nodes with lower mobility to sleep more in reaction to the less-changing link states, in practice this is prohibited due to an unwanted tradeoff between the energy saving and in-time link discovery. All nodes in a network must stay awake frequently based on their highest possible moving speed to avoid network partition. To address this problem, we propose a new wakeup scheme, named Unilateral- (Uni-) scheme, for MANETs that allows nodes with slower moving speed to sleep more without losing the network connectivity. The Uni-scheme supports both the entity mobility and group mobility of nodes, thus has broad applicability. Theoretical analysis and simulation are conducted and show that the Uni-scheme can render significant energy saving as compared with the previous arts.

The problem of coverage is a fundamental issue in wireless sensor networks. In this article, we consider two subproblems: k -coverage contour evaluation and k -coverage rate deployment. The former aims to evaluate, up to k , the coverage level of any location inside a monitored area, while the latter aims to determine the locations of a given set of sensors to guarantee the maximum increment of k -coverage rate when they are deployed into the area. For the k -coverage contour evaluation problem, a nonuniform-grid-based approach is proposed. We prove that the computation cost of our approach is at most the square root of existing solutions. Based on our k -coverage contour evaluation scheme, a greedy k -coverage rate deployment scheme ( k -CRD) is proposed, which is shown to be an order faster than existing studies for k -coverage rate deployment. The k -CRD can incorporate two different heuristics to further reduce its running time. Simulation results show that k -CRD with these heuristics can be significantly more time efficient without causing much degradation in the coverage rate of final deployment.

Cognitive radio (CR) technology enables the opportunistic use of the vacant licensed frequency bands, thereby improving the spectrum utilization. Therefore, considering end-to-end throughput in CR ad-hoc networks is an important research issue because the availability of local spectrum resources may change frequently with the time and locations. In this paper, we propose a cooperative routing protocol in CR ad-hoc networks. An on-demand routing protocol is used to find an end-to-end minimum cost path between a pair of source and destination. The simulation results show that our proposed cooperative routing protocol not only obtains higher end-to-end throughput, but also reduces the end-to-end delay and the amount of control messages compared to previous work.

Abstract In emerging wireless networks, cooperative retransmission is employed to replace packet retransmission between a pair of sender and receiver with poor channel condition. A cooperative MAC protocol which utilizes such benefit is proposed in this paper to improve the network performance in mobile ad hoc networks. In the proposed protocol, relay nodes between sender and receiver are used if the sender cannot communicate with the receiver reliably. Furthermore, the receiver may also stop forwarding the received data frame if the frame is received by the next‐hop receiver on the route to the final destination node. Simulation results show that the proposed protocol outperforms previous works in terms of increased transmission reliability and reduced delay time. Copyright © 2010 John Wiley & Sons, Ltd.

Vehicular Ad Hoc Networks (VANETs) have received considerable attention in recent years. VANETs provide many services and applications such as Internet access Voice over Internet Protocol (VoIP) and information dissemination. Due to dynamic changes in the network topologies, various routing protocols have been studied in the vehicular environments. However, the communications between source and destination vehicles involve many intermediate vehicles, and due to the high mobility of vehicles, these communication links become disconnected. In this paper, we propose a distributed routing protocol in VANETs with the help of roadside units (RSUs). The proposed scheme includes vehicle registration, finding the location of destination vehicle and the handover maintenance. The simulation results show that our proposed protocol is suitable for vehicles communications in VANETs.

Asynchronous wakeup schemes have been proposed for ad hoc networks to increase the energy efficiency of wireless communication. The basic idea is to allow a node to sleep when it is idle, and wakeup periodically to check if there are pending transmissions. In this paper we examine the applicability of asynchronous wakeup schemes to the Mobile Ad Hoc Networks (MANETs). We discover that, although it is desirable to have nodes with lower mobility to sleep more in reaction to the less-changing link states, in practice this is prohibited due to an unwanted tradeoff between the energy saving and in-time link discovery. All nodes in a network must stay awake frequently based on their highest possible moving speed in order to avoid network partition. To address this problem, we propose a new wakeup scheme, named Unilateral- (Uni-) scheme, for MANETs that allows nodes with slower moving speed to sleep more without losing the network connectivity. Theoretical analysis shows that the Uni-scheme can render up to 24\% improvement in energy saving as compared with the previous arts.

In this paper, we propose a zoom-based approach for parking space availability. The main idea of our scheme lies on the fact that drivers near the queried locations are interested in detail (zoomed-in) parking space information, while drivers in a distant place are interested in rough (zoomed-out) information about free parking spaces. Our zooming technique is based on discrete cosine transform. Besides, a winner-take-all scheme is also proposed to further reduce communication overhead in packet loss environment. As compared to previous work, simulation results show that our scheme reduces 40% to 50% communication overhead.

In this paper, a distributed taxi hailing protocol in vehicular ad-hoc networks (VANET) is suggested. Our protocol consists of two parts: taxi booking and taxi de- blocking. Taxi booking part ensures that a vacant taxi with shortest driving distance to passenger under real traffic regulations is booked. Taxi de-blocking part aims to de-block blocked vacant taxis as soon as possible. Simulation results show that compared with previous results, at least 40% of booking time, 50% of waiting time of passengers and 50% of driving distance from booked taxi to passenger, is reduced in our protocol.

Most of routing protocols in VANETs are position-based due to their well scalability. The forwarding decisions of such protocols are simply based on the location information of forwarders' neighborhood and the destination node. Due to high mobility of vehicles, location-service protocols are required to provide the destination location. Location services protocols can be categorized as flooding-based and quorum-based. They are unrealistic for VANETs. In the former approaches, global network flooding require extreme high cost, while in the latter approaches, quorums' hand-off is impossible because of high volume of exchange data. In this paper, we present a routing by utilizing locality of vehicles' traces (i.e., left location information). Besides, by the aid of high mobility of vehicles and news exchange (new information about vehicles' location), vehicles' location information can be spread to improve the possibility of meeting a vehicle which has the location information of the destination. Our protocol is realistic and practical because neither global network flooding nor quorums are required. The simulation results show that our protocol works efficiently for VANETs in city environments and has higher successful query rate and lower cost.

In this paper, we propose a realistic resource sharing protocol for VANET. The main idea of our protocol comes from typhoons. Typhoons move according to their eyes' mobility, i.e., quorums which are responsible for a given resource holder/requester "moves" according to the resource holder's/ requester's mobility. Our protocol exploits spatial locality between requesters and resource holders. When resource requesters get their desired resources, they are able to be new resource holders. For hot-resources, requesters are so numerous that the spatial locality is much enhanced over time. Besides, lots of applications (e.g., available parking slot information) in VANET are location-aware which have spatial locality between requesters and resource holders. By the aid of the spatial locality, resource holders/requesters share/query sources in their vicinity in our protocol. Simulation results show that our protocol has lower search latency and well scalability comparing to the previous work. Besides, due to that the spatial locality is enhanced over time, successful rate increases over time.

Localization is an essential and important research issue in wireless sensor networks (WSNs). Most localization schemes focus on static sensor networks. However, mobile sensors are required in some applications such that the sensed area can be enlarged. As such, a localization scheme designed for mobile sensor networks is necessary. In this paper, we propose a localization scheme to improve the localization accuracy of previous work. In this proposed scheme, the normal nodes without location information can estimate their own locations by gathering the positions of location-aware nodes (anchor nodes) and the one-hop normal nodes whose locations are estimated from the anchor nodes. In addition, we propose a scheme that predicts the moving direction of sensor nodes to increase localization accuracy. Simulation results show that the localization error in our proposed scheme is lower than the previous schemes in various mobility models and moving speeds.

Abstract Wireless sensor networks (WSNs) are characterized by their low bandwidth, limited energy, and largely distributed deployment. To reduce the flooding overhead raised by transmitting query and data information, several data‐centric storage (DCS) mechanisms are proposed. However, the locations of these data‐centric nodes significantly impact the power consumption and efficiency for information queries and storage capabilities, especially in a multi‐sink environment. This paper proposes a novel dissemination approach, which is namely the dynamic data‐centric routing and storage mechanism (DDCRS), to dynamically determine locations of data‐centric nodes according to sink nodes' location and data collecting rate and automatically construct shared paths from data‐centric nodes to multiple sinks. To save the power consumption, the data‐centric node is changed when new sink nodes participate when the WSNs or some queries change their frequencies. The simulation results reveal that the proposed protocol outperforms existing protocols in terms of power conservation and power balancing. Copyright © 2009 John Wiley & Sons, Ltd.

Following the trend of miniature intelligent sensing, wearing small, integrated wireless sensor nodes, such as one with accelerometers and compasses, to capture human body motions may have many applications in medical care and computer animation. In this paper, we demonstrate the use of intelligent sensors to capture human motions for home rehabilitation. We design a game to help a patient to conduct his/her rehabilitation program. For each exercise, the patient is instructed to wear sensors on specified movable body parts. The system will then estimate the quality of the movements and give scores as if it is advised by a therapist. In this way, patients will no longer feel painful and boring as that in traditional rehabilitation, which is typically done in hospitals.

Coverage holes may exist in wireless sensor networks (WSNs) due to presence of obstacles or invalid sensor nodes in the sensing field. Normally, the holes make the data routing failure when the nodes transmit their data back to the sink. In this paper, distributed protocols are developed to identify the boundary nodes surrounding the holes of the sensing filed in WSNs without using any location information. Experimental results demonstrate that our algorithm can precisely and correctly identify the boundary nodes even in sparsely sensors deployed regions. Besides, our algorithm can give better performance in terms of control packet overhead and simulation time as compared to previous work.

How to route packets efficiently and reliably is an important issue in Vehicular Ad hoc Networks (VANETs). Due to the high mobility of vehicles, the communication topology of vehicles in VANET changes rapidly. In this paper, a Virtual Landmarks-based approach is suggested. Under the assistant of Virtual Landmarks, an efficient path is guaranteed even if the roads topology is complex. Our approach is applicable to routing packets between a vehicle and static destination. Simulation results shows that in comparison with previous work, our approach has much lowest communication cost and guarantees a reliable path.

This paper proposes a robot-deployment algorithm that overcomes unpredicted obstacles and employs full-coverage deployment with a minimal number of sensor nodes. Without the location information, node placement and spiral movement policies are proposed for the robot to deploy sensors efficiently to achieve power conservation and full coverage, while an obstacle surrounding movement policy is proposed to reduce the impacts of an obstacle upon deployment. Simulation results reveal that the proposed robot-deployment algorithm outperforms most existing robot-deployment mechanisms in power conservation and obstacle resistance and therefore achieves a better deployment performance.

Abstract Using geographic routing, like GPSR, is efficient for ad hoc and wireless sensor networks, but it requires that nodes be aware of their physical positions. However, if there are holes in the network, routing across them using GPSR will lead to a lot of overloaded nodes on their boundaries. In this paper, we propose a distributed protocol, named hexagonal virtual coordinate (HVC), for constructing a virtual coordinate system. After the HVC is constructed, the nodes in the network will be aware of the relative coordinates among the landmarks through the HVC chart. Based on the HVC chart, a source node can find an auxiliary routing path (ARP) to indicate the direction of the journey from the source to the destination. Simulation results show that our protocol can support geographic routing efficiently, and the landmarks found by our protocol are uniformly located in the network even if some holes exist within it. In addition, our protocol is resilient to various network shapes and can find a load balancing routing path to the destination even if this path comes across holes in the network. Copyright © 2008 John Wiley & Sons, Ltd.

In this paper, we propose an asynchronous duty cycle adjustment MAC protocol, called ADCA, for the wireless sensor network (WSN). ADCA is a sleep/wakeup schedule-based protocol to reduce power consumption without lowering network throughput or lengthening transmission delay. It is asynchronous; it allows each node in the WSN to set its own sleep/wakeup schedule independently. The media access is thus staggered and collisions are reduced. According to the statuses of previous transmissions, ADCA adjusts the duty cycle length for shortening transmission delay and increasing throughput. Simulation results show that ADCA outperforms related ones in terms of energy saving, network throughput and transmission delay.

Coverage problem is a fundamental issue in wireless sensor networks. In this paper, we consider two sub-problems: k-coverage rate evaluation and k-coverage rate deployment. The former aims to evaluate the ratio of k-covered area relative to the monitored area, while the latter aims to determine the minimum number of sensors required and their locations to guarantee that k-coverage rate of the monitored area meets application requirements. For k-coverage rate evaluation problem, a non-uniform-grid- based approach for random deployments is proposed. For k-coverage rate deployment problem, a greedy-based approach is suggested to meet the requirement of k-coverage rate. Simulation results show that both our schemes are more time efficient than previous work.

How to secure data communication is an important problem in wireless sensor networks (WSNs). General solutions to the problem are to encrypt the packet payload with symmetric keys. But those solutions only prevent the packet content from being snooped or tampered. Adversaries still can learn network topology by the traffic analysis attack. In this paper, we propose an anonymous path routing (APR) protocol for WSNs. In APR, data are encrypted by pair-wise keys and transmitted with anonyms between neighboring sensor nodes and anonyms between the source and destination nodes of a multi-hop communication path. The encryption prevents adversaries from disclosing the data, and the anonymous communication prevents adversaries from observing the relation of the packets for further attacks. We implement APR on the MICAz platform to evaluate its overheads for demonstrating its applicability in practical WSNs.

In wireless sensor networks, congestion occurs when every sensor node will send the event it has sensed to a sink node. This operation makes the sensors closer to the sink, resulting in congestion. Congestion may cause packets loss, lower network throughput and sensor energy waste. In this paper, we propose a hybrid congestion control protocol that considers not only the packets delivery rate but also retains the buffer size of each node. The proposed protocol may avoid packets drop due to traffic congestion and improve the network throughput. The simulation results show that the performance of the proposed protocol is better than the previous works.

Localization is a fundamental and essential issue for wireless sensor networks (WSNs). Existing localization algorithms can be categorized as either range-based or range-free schemes. Range-based schemes are not suitable for WSNs because of their irregularity of radio propagation and their cost of additional devices. In contrast, range-free schemes do not need to use received signal strength to estimate distances and only need simple and cheap hardware, and are thus more suitable for WSNs. However, existing range-free schemes are too costly and not accurate enough or are not scalable. To improve previous work, we present a fully distributed range-free localization scheme for WSNs. We assume that only a few sensor nodes, called anchors, know their locations, and the remaining (normal) nodes need to estimate their own locations by gathering nearby neighboring information. We propose an improved grid-scan algorithm to find the estimated locations of the normal nodes. Furthermore, we derive a vector-based refinement scheme to improve the accuracy of the estimated locations. Analysis, simulation, and experiment results show that our scheme outperforms the other range-free schemes even when the communication radius is irregular.

Abstract A contention‐based wireless ad hoc medium access control (MAC) protocol, such as carrier sense multiple access with collision avoidance (CSMA/CA), has excellent efficiency when the system is light loaded. The main drawback of such protocols is their inefficiency and unbounded delay when the system load is heavy. On the other hand, a contention‐free MAC protocol, such as token passing, has a better and fair throughput when the system is heavy loaded. The main drawback of such protocols is their inefficiency when only a small amount of users want to transmit. In this paper, we propose a new load awareness single‐hop wireless ad hoc MAC protocol (which is called theLAprotocol) that exploits the benefits of both contention‐based and contention‐free protocols. A contention‐based MAC protocol is used when the system is light loaded and a contention‐free one is used otherwise. OurLAprotocol, which operates in a distributed fashion and is fully compatible with the IEEE 802.11 wireless local area network (WLAN) standard, can switch smoothly between the contention‐based protocol and the contention‐free one. Simulation results show that our protocol indeed extracts the better part of two kinds of protocols. Copyright © 2006 John Wiley & Sons, Ltd.

When we exploit multiple channels in MAC protocol, we can achieve a higher network throughput than using one single channel due to that multiple transmissions can take place simultaneously. In this paper, we proposed a novel group-based multichannel MAC protocol which cannot only utilize multiple channels to transmit data packets but allow using multiple channels to propagate control packets. The protocol we presented is simple and suitable for wireless ad hoc networks with multiple available channels. The simulation results show that our protocol has the superior performances in network throughput to previous work.

Using geographic routing, like GPSR, is efficient for ad hoc and wireless sensor networks, but it requires that nodes be aware of their physical positions. However, if there are holes in the network, routing across holes in GPSR will lead to a lot of overloaded nodes in the boundaries of the holes. In this paper, we propose a distributed protocol, named the hexagonal virtual coordinate (HVC), for constructing a virtual coordinate system. After the HVC is constructed, the nodes in the network will be aware of relative coordinates among the landmarks through the HVC chart. Based on the HVC chart, a source node can find an auxiliary routing path to indicate the direction of the journey from the source to the destination. Simulation results show that our protocol can support geographic routing efficiently.

In this paper, we propose a k-coverage preserving protocol to achieve energy efficiency while ensuring the required coverage. In our protocol, we try to select a minimal active set of sensor nodes to reach energy conservation and maintain a complete area k-coverage. We model this problem as a minimum set cover problem and solve it by using a heuristic greedy algorithm. Based on the k-coverage preserving protocol, we then propose a protocol to deal with the probabilistic k-coverage requirement, in which each sensor could be assumed to be able to detect a nearby event with a certain probability. In the probabilistic k-coverage protocol, any point in the monitoring region can be sensed by at least k sensor nodes no lower than a confidence probability. Finally, we evaluate the performance of our protocols with simulations.

Topology control not only achieves the objective of power saving but also increases the system throughput by increasing the spatial reuse of communication channels. However, there exists a hidden terminal problem due to asymmetric transmission radii among nodes after topology control. In this paper, we propose a distributed protocol that deals with topology control at network layer and hidden terminal problem at MAC layer. Each node in the networks determines its power for data transmission and control packets transmission according to the received beacon messages from its neighbors. The proposed protocol works without location information and uses little control packet overhead to prevent the potential collisions due to the hidden terminals. Simulations show that our protocol significantly decreases total power consumption in the networks and has a better network throughput compared to previous work.

The lifetime of a mobile ad hoc network (MANET) depends on the durability of the mobile hosts' battery resources. In the IEEE 802.11 Power Saving Mode, a host must wake up at every beacon interval, to check if it should remain awake. Such a scheme fails to adjust a host's sleep duration according to its traffic, thereby reducing its power efficiency. This paper presents new MAC protocols for power saving in a single hop MANET. The essence of these protocols is a quorum-based sleep/wake-up mechanism, which conserves energy by allowing the host to sleep for more than one beacon interval, if few transmissions are involved. The proposed protocols are simple and energy-efficiency. Simulation results showed that our protocols conserved more energy and extended the lifetime of a MANET.

Bluetooth is a low cost, low power, short-range radio technology used for wireless personal area networks (PANS). Bluetooth scatternet is a set of piconets interconnected via bridge devices. Good interpiconet schedulings are necessary for bridge devices to switch among piconets they participate in. This paper proposes an interpiconet scheduling algorithm named "Traffic-Aware Scatternet Scheduling" (TASS), for bridges in Bluetooth scatternets. According to masters' traffic information, TASS can adaptively switch the bridge to high traffic load masters, and increase the usage of the bridge. In addition, TASS can reduce the number of failed "unsniffs" and the overhead of "bridge switch wastes" to further increase overall system performance. Simulation results show that TASS outperforms existing interpiconet scheduling in both network throughput and adaptability for various traffic loads.

Abstract The wireless sensor network (WSN) has attracted lots of attention recently. Broadcast is a fundamental operation for all kinds of networks and it has not been addressed seriously in the WSN. Therefore, we propose two types of power and time efficient broadcasting protocols, namely one‐to‐all and all‐to‐all broadcasting protocols, for five different WSN topologies. Our one‐to‐all broadcasting protocols conserve power and time by choosing as few relay nodes as possible to scatter packets to the whole network. Besides, collisions are carefully handled such that our one‐to‐all broadcasting protocols can achieve 100% reachability. By assigning each node a proper channel, our all‐to‐all broadcasting protocols are collision free and efficient. Numerical evaluation results compare the performance of the five topologies and show that our broadcasting protocols are power and time efficient. Copyright © 2005 John Wiley & Sons, Ltd.

In this paper, we propose two interest-based bandwidth-efficient lookup protocols, simple lookup protocol and advanced lookup protocol, for mobile environments. A peer willing to search files broadcasts a query message with keywords relevant to its interests to its neighbors in the transmission range, and only those neighbors also interested in the query forward. Simulation results show that our protocols have higher success rate and raise the scalability and bandwidth efficiency comparing to the previous work. Besides, our protocols can avoid selfish behaviors, since the behavior of forwarding queries benefits not only the source node but also the forwarding node.

A distributed algorithm for the multihop wireless sensor networks is proposed to construct a novel energy efficient tree topology. The topology is constructed, without taking location information of the sensor nodes and energy conservation of the network is accomplished by controlling the transmission power levels. Experimental results of our protocol show that, total energy consumption of the network is very less as compared to the energy consumption of the network without any power control. Our protocol, being a distributed one, attains the energy conservation up to an optimum level and extends the network lifetime better than the centralized algorithms that we have considered.

The paper proposes an efficient distributed protocol to find a subset of connected sensor nodes to cover the queried region. Each node determines whether to be a sensing node to sense the queried region according to its priority, which is represented by the remaining power or sensing area within the queried region. The proposed protocol can efficiently construct a subset of connected sensing nodes and respond the query request to the sink node. Simulation results show that the proposed protocol is more efficient and has a lower communication overhead than the existing protocol.

Most wireless sensor networks consist of a large number of static, low-power, short-lived, and unreliable sensors. In this paper, we considered sensor networks consisting of both static and mobile nodes. Integrating both types of devices enables new applications, such as nodes replacement, hole and partition recovery, and autonomous deployment and redeployment. We designed a smart mobile robot and implemented an application of nodes replacement to demonstrate its use, via our nodes replacement algorithm. In this algorithm, the mobile robots can navigate towards low-energy sensor nodes and replace them automatically, with new sensor nodes, having no location information. The navigation algorithm is based on received signal strength between the mobile robot and the communicating node. The experimental results confirm that the mobile robots successfully achieved their assigned tasks.

In multihop wireless ad hoc networks, it is important that all mobile hosts are synchronized. Synchronization is necessary for power management and for frequency hopping spread spectrum (FHSS) operations. IEEE 802.11 standards specify a clock synchronization protocol but this protocol suffers from the scalability problem due to its inefficiency contention mechanism. We propose an automatic self-time-correcting procedure (ASP) to achieve clock synchronization in a multihop environment. Our ASP has two features. Firstly, a faster host has higher priority to send its timing information out than a slower one. Secondly, after collecting enough timing information, a slower host can synchronize to the faster one by self-correcting its timer periodically (which makes it becoming a faster host). Simulation results show that our ASP decreases 60% the average maximum clock drift as compared to the IEEE 802.11 and reduces 99% the number of asynchronism in a large-scale multihop wireless ad hoc networks.

In the literature, many broadcasting-based schemes have been proposed to efficiently support near-VOD services. However, none of these schemes allows the server to dynamically and seamlessly change the number of channels allocated to a video. Naively allocating a new set of channels for the transition could increase server's load, waste communication bandwidth, and even drain the channels of the system. In Tseng et al. (2000), it is shown how to enhance the Fast Broadcasting (FB) scheme for seamless channel transition. The problem remains open whether other broadcasting-based schemes can sustain seamless channel transition. In this paper, we show how to enhance the Staircase Broadcasting (SB) scheme so that a server can seamlessly increase or decrease the channels allocated to a video. The SB scheme has been proved to require significantly less buffering space than FB, while sustaining the same startup latency as FB. Detailed performance comparisons are presented to demonstrate the advantages of the proposed scheme.

A contention-based wireless ad hoc medium access control (MAC) protocol, such as carrier sense multiple access with collision avoidance (CSMA/CA), has the excellence of simple and efficient when the system is light-loaded. The main drawback of such protocols is their inefficiency and unbounded delay when system load is heavy. On the other hand, a contention-free MAC protocol, such as token passing, has better and fair throughput when the system is heavy-loaded. The main drawback of such protocols is their inefficiency when only a small amount of users want to transmit. In this paper, we propose a new load awareness wireless ad hoc MAC protocol (which is called the LA protocol) that exploits the benefits of both contention-based and contention-free protocols. A contention-based MAC protocol is used when system is light-loaded and a contention-free one is used otherwise. Our LA protocol, which operates distributed and is fully compatible with IEEE 802.11 wireless local area network (WLAN) standard, can switch smoothly between the contention-based protocol and the contention-free one. Simulation results show that our protocol indeed extracts the better part of two kinds of protocols and performs well in all systems loads.

In existing parallel computing structures, hypercubes have several distinct advantages; they support parallel computing, provide disjoint path and tolerate faults. If devices with computing capabilities can be linked as a hypercube by taking advantage of Bluetooth radio's features, then a high performance computing and efficient communication environment can be established by applying currently used algorithms. This is a pilot study of applying Bluetooth wireless technology to construct a parallel computation and communication environment. A three-stage distributed construction protocol is presented for automatically constructing a hypercube computing environment from Bluetooth devices. The proposed protocol tackles the link construction, role assignment, scatternet formation and network management problems, to construct efficiently a hypercube structure. The proposed protocol enables Bluetooth devices easily to construct a routing path, tolerate faults and create disjoint paths. Parallel and distributed computing will be realized in a Bluetooth wireless environment. Experimental results show the proposed protocol will be able to set up a scatternet that is appropriate for parallel computing and communications.

The lifetime of a mobile ad hoc network (MANET) depends on the durability of the battery resource of the mobile hosts. Earlier research has proposed several routing protocols specifically on MANET, but most studies have not focused on the limitations of battery resource. We propose a new energy-aware routing protocol, which can increase the durability of the energy resource and, therefore, the lifetime of the mobile hosts and the MANET. The proposed protocol can conserve energy by shortening the idle period of the mobile hosts without increasing the probability of packet loss or reducing routing fidelity. Simulation results indicate that this new energy-conserving protocol can extend the lifetime of a MANET.

The wireless sensor network (WSN) has attracted lots of attention recently. Since the sensor nodes usually have no plug-in power, we have to conserve power so that each sensor node can operate for a longer period of time. Here, we propose power and time efficient broadcasting protocols for four different WSN topologies. Our broadcasting protocols conserve power and time by choosing as few relay nodes as possible to scatter messages to the whole network. Besides, collisions are carefully handled such that our one-to-all broadcast protocols can achieve 100% reachability. Numerical evaluation results compare the performances of the four topologies and show that our broadcasting protocols are power and time efficient.

Abstract Leader election and initialization are two fundamental problems in mobile ad hoc networks (MANETs). The leader can serve as a coordinator in the MANETs and the initialization protocol can assign each host a sequential, unique, and short ID. As we know, no research on initialization for IEEE 802.11‐based MANETs has been done. Here, we propose two contention‐based leader election and initialization protocols for IEEE 802.11‐based single‐hop MANETs. We also provide an efficient approach to evaluate the performance of the proposed protocols, such that the performance can be evaluated in polynomial time. The evaluation results provide a guideline to set the size of the contention window and thus improve the performance of the proposed leader election and initialization protocols. The results can also be used as a guideline to set the size of the contention window for any contention‐based protocol. Simulation results justify that the evaluation results provide a good guideline to set the size of the contention window. Copyright © 2003 John Wiley & Sons, Ltd.

We present a new energy-efficient directed diffusion protocol by using the proposed diagonal-based hexagonal-mesh scheme for a wireless sensor network. The wireless sensor network is more reasonable to build a fixed-topological wireless network environment than the conventional MANET due to the low mobility. Therefore, all sensor nodes are arranged into a fixed-topological wireless network structure, namely the hexagonal-mesh, while the MAC protocol is adopted using the periodic active-and-sleep model. The wireless sensor networks use battery-operated computing and sensing devices. The directed diffusion is mainly operated on the diagonal-paths of the hexagonal-mesh under the energy-efficient consideration. To achieve the energy-efficient purpose, our diagonal-based directed diffusion scheme has the following main contributions: (1) a periodic active-and-sleep MAC protocol on TDMA channel model is designed; (2) a periodic backbone-path-exchange scheme is periodically performed on the diagonal-mesh to consider the per-node fairness problem; and (3) a directed diffusion communication application is developed based on the diagonal-based scheme. Finally, the performance analysis result is demonstrated to illustrate the energy-efficient achievement of our proposed scheme.

Leader election and initialization are two fundamental problems in mobile ad hoc networks (MANETs). The leader can serve as a coordinator in the MANETs and the initialization protocol can assign each host a unique and short id. We know that none of the research on initialization for IEEE 802.11-based MANETs has been done. Here, we propose two contention-based leader election and initialization protocols for IEEE 802.11-based single-hop MANETs. Simulation results show that our protocols are efficient.

In a mobile ad hoc network (MANET), one essential issue is Medium Access Control (MAC), which addresses how to utilize the radio spectrum efficiently and to resolve potential contention and collision among mobile hosts on using the medium. Existing works have been dedicated to using multiple channels and power control to improve the performance of MANET. In this paper, we investigate the possibility of bringing the concepts of power control and multi-channel medium access together in the MAC design problem in a MANET. Existing protocols only address one of these issues independently. The proposed protocol is characterized by the following features: (i) it follows an ‘on-demand’ style to assign channels to mobile hosts, (ii) the number of channels required is independent of the network topology and degree, (iii) it flexibly adapts to host mobility, (iv) no form of clock synchronization is required and (v) power control is used to exploit frequency reuse. Power control may also extend battery life and reduce signal interference, both of which are important in wireless communication. Through simulations, we demonstrate the advantage of our new protocol.

The packet radio network (PRN) is an attractive architecture to support mobile and wireless communication. Although the code assignment problem has been studied extensively on PRN, we observe that the power control problem has been ignored by most works, but may have significant impact on performance. By power control, we mean that the transmission ranges of stations are tunable. We show, given a PRN in which each host already received a code, how to adjust the powers of stations to control/improve the topology of the PRN without violating the original code assignment. Several schemes are proposed. Through simulations, we demonstrate that although the code assignment problem is NP-complete and thus computationally very expensive, using our power adjustment schemes can easily improve the network performance by about 20% with polynomial costs.

This paper proposes two efficient single-node broadcasting schemes for a network of workstations (NOW) based on a network-partitioning concept. To broadcast a message, the scheme works in three phases. First, we partition the network into two sub-networks (data-distributed networks, DDN). The broadcast message is evenly divided into two sub-messages, each being sent to one representative node in each subnetwork. Second, each sub-message is distributed in its subnetwork independently. Finally, through a sub-message combination step, each node obtains the whole broadcast message. Two network-partitioning schemes, namely 0-1 partitioning and odd-even partitioning, are proposed. Through simulations on irregular and regular networks, we confirm the average latency of these schemes achieve performance improvement compared with the optimal broadcast scheme.

This paper considers the location tracking problem in PCS networks. How a solution to this problem performs in fact highly, depends on the mobility patterns of users. In this paper we propose a new traveling salesman mobility (TSM) model, in the hope of catching the mobility patterns of a large group of users. The TSM model is characterized by features of "stop-or-move", "infrequent transition" "memory of roaming direction", and "oblivious in different moves". Then a location tracking strategy based on this TSM model is developed. The scheme only needs to keep very little information for each user. Analyses and simulations are provided, which show that the strategy is very prospective.

This paper considers the multi-node multicast problem in a wormhole-routed 2-D torus/mesh, where an arbitrary number of source nodes each intends to multicast a message to an arbitrary set of destinations. To resolve the contention and the congestion problems, we propose to partition the network into subnetworks to distribute, and thus balance, the traffic load among all network links. Several ways to partition the network are explored. The network-partitioning idea was used in earlier works for single-node broadcast and single-node multicast. This paper contributes in extending its applicability to multi-node multicast and demonstrating its capability to balance load on torus/mesh. Simulation results show significant improvement over existing results for torus and mesh networks.

One way to broadcast a popular video is to use a number of dedicated channels, each responsible for broadcasting some portion of the video periodically in a predefined way. The stress on the channels can be alleviated, and new viewers do not have to wait long to start their playback. Many approaches falling in this category have been proposed. One such scheme that interests us is the fast broadcasting (FB) scheme, which can broadcast a video using k channels by incurring at most O(D/2/sup k/) waiting time on new-coming viewers, where D is the length of the video. We consider a set of videos, each being broadcast by the FB scheme. Since the demand levels on these videos may change with time, it is sometimes inevitable to change the numbers of channels assigned to some videos. We propose a novel seamless channel transition enhancement on top of the FB scheme to dynamically change the number of channels assigned to a video on-the-fly. Clients currently viewing this video will not experience any disruption because of the transition. A channel allocation scheme is also proposed based on the arrival rates of videos to minimize the average waiting experienced by all viewers. From the system manager's point of view, the enhancement will make the FB scheme more attractive.

The objective of this paper is to propose an image authentication scheme, which is able to detect malicious tampering of images even they have also been incidentally distorted. By modeling incidental and malicious distortions as Gaussian distributions with small and large variances, respectively, we propose to embed a watermark in the wavelet domain by a mean quantization technique. Due to the various probabilities of tamper response at each scale, these responses are integrated to make a decision on the tampered areas. Statistical analysis is conducted and experimental results are given to demonstrate that our watermarking scheme is able to detect malicious attacks while tolerating incidental distortions.

The paper presents an algorithm to reduce cache conflicts and improve cache localities. The proposed algorithm analyzes unique locality reference space for each reference pattern, partitions the multi-level cache into several parts with different size, and then maps array data onto the scheduled cache positions such that cache conflicts can be eliminated. To reduce the memory overhead for mapping array variables onto partitioned cache, a greedy method for rearranging array variables in declared statement is also developed. In addition, we combine loop tiling and the proposed schemes for exploiting both temporal and spatial reuse opportunities. To demonstrate that our approach is effective at reducing the number of cache conflicts and exploiting cache localities, we use Atom as a tool to develop a simulator for simulation of the behavior of direct-mapping cache. Experimental results show that applying our cache partitioning scheme can largely reduce the cache conflicts and thus save program execution time in both one-level cache and multi-level cache hierarchies.

One way to broadcast a popular video is to let multiple users share fewer channels. The stress on channel demand can be alleviated without sacrificing viewers' waiting time. One such scheme that interests us is the fast broadcasting (FB) scheme (Juhn et al., 1997, 1998), which can broadcast a popular video using k channels without keeping newcoming viewers waiting for more than O(D/2/sup k/) time, where D is the length of the video. In this paper, we propose two enhancements to the FB scheme. First, since the level of demand on a video may change by time, we show how to dynamically change the number of channels assigned to the video and seamlessly perform this transition. Clients currently viewing this video will not experience any disruption during the transition. Second, given a set of channels and a set of popular videos, we propose a scheme to assign these channels to the videos such that the average viewers' waiting time is minimal. From the system manager's point of view, these enhancements will make the FB scheme more attractive.

This paper considers the multi-node multicast problem in a wormhole-routed 20 torus/mesh, where an arbitrary number of source nodes each intending to multicast a message to an arbitrary, set of destinations. To resolve the contention and the congestion problems, we propose to partition the network into subnetworks to distribute, and thus balance, the traffic load among all network links. Several ways to partition the network are explored. Simulation results show significant improvement over existing results for torus and mesh networks.

In mobile ad hoc networks (MANETs), one essential issue is how to increase channel utilization while avoiding the hidden-terminal and the exposed-terminal problems. Several MAC protocols, such as RTS/CTS-based and busy-tone-based schemes, have been proposed to alleviate these problems. In this paper, we explore the possibility of combining the concept of power control with the RTS/CTS-based and busy-tone-based protocols to further increase channel utilization. A sender will use an appropriate power level to transmit its packets so as to increase the possibility of channel reuse. The possibility of using discrete, instead of continuous, power levels is also discussed. Through analyses and simulations, we demonstrate the advantage of our new MAC protocol. This, together with the extra benefits such as saving battery energy and reducing cochannel interference, does show a promising direction to enhance the performance of MANETs.

In a mobile ad-hoc networks (MANETs), one essential issue is how to increase channel utilization while avoiding the hidden-terminal and the exposed-terminal problems. Several MAC protocols, such as RTS (request to send)/CTS (clear to send) based and busy tone-based schemes, have been proposed to alleviate these problems. In this paper, we explore the possibility of combining the concept of power control with the RTS/CTS-based and busy tone-based protocols to further increase channel utilization. A sender will use an appropriate power level to transmit its packets so as to increase the possibility of channel reuse. The possibility of using discrete, instead of continuous, power levels is also discussed. Through analyses and simulations, we demonstrate the advantage of our new MAC protocol. This, together with the extra benefits such as saving battery energy and reducing co-channel interference, does show a promising direction to enhance the performance of MANETs.

Broadcasting is a common operation in a network to resolve many issues.In a mobile ad hoc network (MANET) in particular, due to host mobility, such operations are expected to be executed more frequently (such as finding a route to a particular host, paging a particular host, and sending an alarm signal).Because radio signals are likely to overlap with others in a geographical area, a straightforward broadcasting by flooding is usually very costly and will result in serious redundancy, contention, and collision, to which we refer as the broadcast storm problem.In this paper, we identify this problem by showing how serious it is through analyses and simulations.We propose several schemes to reduce redundant rebroadcasts and differentiate timing of rebroadcasts to alleviate this problem.Simulation results are presented, which show different levels of improvement over the basic flooding approach.

In this paper, we propose new routing schemes to perform all-to-all personalized communication (or known as complete exchange) in wormhole-routed, one-port tori. On tori of equal size along each dimension, our algorithms use both asymptotically optimal startup and transmission time. The results are characterized by several interesting features: (1) the use of gather-scatter tree to achieve optimality in startup time, (2) enforcement of shortest paths in routing messages to achieve optimality in transmission time, (3) application of network-partitioning techniques to reduce the constant associated with the transmission time, and (4) the dimension-by-dimension and gather-scatter-tree approach to make possible applying the results to nonsquare, any-size tori. In the literature, some algorithms are optimal in only one of startup and transmission costs, while some, although asymptotically optimal in both costs, will incur much larger constants associated with the costs. Numerical analysis and experiment both show that significant improvement can be obtained by our scheme on total communication latency over existing results.

This paper presents an efficient compilation technique to generate the local memory access sequences for block-cyclically distributed array references with affine subscripts in data-parallel programs. For the memory accesses of an array reference with affine subscript within a two-nested loop, there exist repetitive patterns both at the outer and inner loops. We use tables to record the memory accesses of repetitive patterns. According to these tables, a new start-computation algorithm is proposed to compute the starting elements on a processor for each outer loop iteration. The complexities of the table constructions are O(k+s/sub 2/), where k is the distribution block size and s/sub 2/ is the access stride for the inner loop. After tables are constructed, generating each starting element for each outer loop iteration can run in O(1) time. Moreover, we also show that the repetitive iterations for outer loop are Pk/gcd(Pk,s/sub 1/), where P is the number of processors and s/sub 1/ is the access stride for the outer loop. Therefore, the total complexity to generate the local memory access sequences for a block-cyclically distributed array with affine subscript in a two-nested loop is O(Pk/gcd/(Pk,s/sub 1/)+k+s/sub 2/).

In a multicomputer network, sending a packet typically incurs two costs: start-up time and transmission time. This work is motivated by the observation that most broadcast algorithms in the literature for the star graph networks only try to minimize one of the costs. Thus, many algorithms, though claimed to be optimal, are only so when one of the costs is negligible. In this paper, we try to optimize both costs simultaneously for four types of broadcast problems: one-to-all or all-to-all broadcasting in an n-star network with either one-port or all-port communication capability. As opposed to earlier solutions, the main technique used in this paper is to construct from a source node multiple spanning trees, along each of which one partition of the broadcast message is transmitted.

The star graph interconnection network has been recognized as an attractive alternative to the hypercube network. Previously, the star graph has been shown to contain a Hamiltonian cycle. In this paper, we consider an injured star graph with some faulty links and nodes. We show that even with f/sub e//spl les/n-3 faulty links, a Hamiltonian cycle still can be found in an n-star, and that with f/sub v//spl les/n-3 faulty nodes, a ring containing at most 4f/sub v/ nodes less than that in a Hamiltonian cycle can be found (i.e. the ring contains at least n!-4f/sub v/ nodes). In general, in an n-star with f/sub e/ faulty links and f/sub v/ faulty nodes, where f/sub e/+f/sub v//spl les/n-3, our embedding is able to establish a ring containing at least n!-4f/sub v/ nodes.

In this paper, we propose and analyze a new interconnection network called bubblesort star graph, which is the merger of the bubblesort graph and the star graph. We present the deadlock-free wormhole routing algorithm for the proposed network. We also develop the method to embed a mesh into a bubblesort star graph with dilation two and expansion one. Besides, we use the recursive scheme to embed the multiple disjoint copies of the hypercube into a bubblesort star graph with all faults recovery capacity as well as constant expansion and dilation one or two. This reflects the fact that the embeddability of the bubblesort star graph is much better than that of the star graph.

Efficiently solving the personalized broadcast problem in an interconnection network typically relies on finding an appropriate spanning tree in the network. In this paper, we show how to construct in a complete star graph an asymptotically balanced spanning tree, and in an incomplete star graph a near-balanced spanning tree. In both cases, the tree is shown to have the minimum height. In the literature, this problem has only been considered for the complete star graph, and the constructed tree is about 4/3 times taller than the one proposed in this paper.

Abstract A large class of loop programs applied in solving differential equations, Fourier transforms, image processing and neural processing can be translated or rewritten into a vector execution form with a π‐block dependence graph. In the paper we propose a multithreading strategy to partition such vectorized loops into multithread execution form. Each partitioned thread consists of instances of statements with localities in vector registers. The multithreading scheme gives a novel combination of loop unrolling, statement instances reordering, index shifting, vector register reuse exploiting and multithreading. For some cases of loop program with π‐block dependence graph, experimental results show that our scheme assists vector compilers of the Convex C38 series to reduce the number of memory accesses and synchronizations among CPUs.

Based on the V.E. Mendia and D. Sarkar's algorithm (1992), we propose an optimal and nonredundant distributed broadcasting algorithm in star graphs. For an n-dimensional star graph, our algorithm takes O(n log/sub 2/ n) time and guarantees that all nodes in the star graph receive the message exactly once. Moreover, broadcasting m packets in a pipeline fashion takes O(m log/sub 2/ n+n log/sub 2/ n) time due to the nonredundant property of our broadcasting algorithm.>

In this paper, we propose a source-to-source compilation strategy to partition vectorized loop programs into multithread execution form. Each partitioned thread consists of instances of statements with localities in vector registers. The multi-threading scheme gives a novel combination of loop unrolling, statement instances reordering, index shifting, vector register reuse exploiting, and multi-threading. Experimental results show that our multithreading scheme assists vector compiler of Convex C38 series to reduce the number of memory accesses and the number of synchronizations among CPUs and usually obtains a better performance.

In distributed memory multicomputers, local memory accesses are much faster than those involving interprocessor communication. For the sake of reducing or even eliminating the interprocessor communication, the array elements in programs must be carefully distributed to local memory of processors for parallel execution. We devote our efforts to the techniques of allocating array elements of nested loops onto multicomputers in a communication-free fashion for parallelizing compilers. We first analyze the pattern of references among all arrays referenced by a nested loop, and then partition the iteration space into blocks without interblock communication. The arrays can be partitioned under the communication-free criteria with nonduplicate or duplicate data. Finally, a heuristic method for mapping the partitioned array elements and iterations onto the fixed-size multicomputers under the consideration of load balancing is proposed. Based on these methods, the nested loops can execute without any communication overhead on the distributed memory multicomputers. Moreover, the performance of the strategies with nonduplicate and duplicate data for matrix multiplication is studied.>

In this paper, we devote our efforts to the techniques of allocatiing array elements of nested loops onto multicomputers in a communication-free fashion for parallelizing compilers. The arrays can be partitioned under the communication free criteria with non-duplicate or duplicate data. In addition, the performance of the strategies with non-duplicate and dupli cate array data is compared.

Abstract We introduce a new model for replication in distributed systems. The primary motivation for replication lies in fault tolerance. Although there are different kinds of replication approaches, our model combines the advantages ofmodular redundancyandprimary‐stand‐byapproaches to give more flexibility with respect to system configuration. To implement such a model, we select the IBM PC‐net with MS‐DOS environment as our base.Transparencyas well asfault‐tolerance file accessare the highlights of our system design. To fulfil these requirements, we incorporate the idea ofdirectory‐oriented replicationandextended prefix tablesin the system design. The implementation consists of a command shell, a DOS manager, and a recovery manager. Through this design, we can simulate a UNIX‐like distributed file system whose function is compatible with MS‐DOS.

The authors study the performance of multiprocessor systems employing multiple buses as the interconnection networks under a nonuniform requesting model, called the hierarchical requesting model. The effective memory bandwidth is chosen as the performance measure. The networks investigated include multiple bus networks with full bus-memory connection, multiple bus networks with single bus-memory connection, and multiple bus networks with partial bus-memory connection. The authors also propose a type of multiple bus network with partial bus-memory connection, called partial bus networks with K classes. The N costs and fault-tolerant capabilities of the multiple bus networks are also evaluated and compared to one another. It is shown that the partial bus networks with K classes are useful in applications requiring high performance and degree of fault tolerance with moderate cost.>

FOR-loops are the main source of parallelism in programs. A nonlinear transformation algorithm for parallelizing the execution of FOR-loop models is proposed. It is shown that by the mapping of nonlinear transformation, iterations of FOR-loops can be executed in a parallel form. The algorithm is useful in exploiting the parallelism of FOR-loops with one or more partitions on the innermost loop. Algorithms to partition and map the nested FOR-loops onto fixed size systolic arrays are discussed. Based on the time and space mapping schemes, all the iterations of FOR-loops can be correctly executed on the array processors in a parallel form.>

A method for executing nested loops with constant loop-carried dependencies in parallel on message-passing multiprocessor systems to reduce communication overhead is presented. In the partitioning phase, the nested loop is divided into blocks that reduce the interblock communication, without regard to the machine topology. The execution ordering of the iterations is defined by a given time function based on L. Lamport's (1974) hyperplane method. The iterations are then partitioned into blocks so that the execution ordering is not disturbed, and the amount of interblock communication is minimized. In the mapping phase, the partitioned blocks are mapped onto a fixed-size multiprocessor system in such a manner that the blocks that have to exchange data frequently are allocated to the same processor or neighboring processors. A heuristic mapping algorithm for hypercube machines is proposed.>

Semigroup and prefix computations on two-dimensional mesh-connected computers with multiple broadcasting (2-MCCMBs) are studied. Previously, only square 2-MCCMBs with N processing elements were considered for semigroup computations of N data items, and O(N/sup 1/6/) time was required. It is found that square machines are not the best form for semigroup computations, and an O(N/sup 1/8/)-time algorithm is derived on an N/sup 5/8/*N/sup 3/8/ rectangular 2-MCCMB. This time complexity can be further reduced to O(N/sup 1/9/) if fewer processing elements are used. Parallel algorithms for prefix computations with the same time complexities are derived.>

The performance of multiple-bus networks with full bus-memory connection, single bus-memory connection, and partial bus-memory connection are presented. A type of multiple-bus network, called a partial bus network with K classes, is proposed. Under a nonuniform requesting model called a hierarchical requesting model, the performance of the above multiple-bus networks is analyzed. The costs and fault-tolerant capabilities of each are evaluated and compared with one another. It is shown that the proposed networks are useful in applications requiring high performance and degree of fault tolerance with moderate cost.>

Analyzes the performance of the multistage interconnection networks (MINs) for interconnecting N processors or N processors to N commonly shared memory modules in a multiprocessor system. A general model, called hierarchical requesting model, has been proposed. The performance of the MINs with respect to their memory bandwidth is analyzed and is compared to that of a crossbar under the proposed model. Based on the analytical results, the authors present a task allocation strategy to increase the memory bandwidth of the MINs.>