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.

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.

By integrating the data from sensors and cameras, Digital Twin (DT) creates a virtual representation of real-world road traffic and road users (RUs) to enhance understanding and decision-making for traffic applications. However, modern traffic environments require sensors on RUs to create a virtual representation. Without these sensors, it is difficult to create virtual representations for RUs in the DT, limiting the system’s effectiveness. In this paper, we first design a DT-based system for pairing and updating the information of RUs in road traffic environments to support for RUs with and without sensors. Our system includes two modules for updating the information: 1) Localization module for updating the location of the RU itself, and 2) Road User detection module to detect the other RUs for updating. Then, we formulate a new optimization problem to minimize the Age of Incorrect Information (AoII) metric and propose an algorithm, named AoII minimization by Update Selection in Digital Twin (AoII-USDT), to determine the updating policy of each RU. Simulation results show that AoII-USDT outperforms state-of-the-art algorithms regarding total AoII, freshness improvement, and accuracy.

Reconfigurable intelligent surface (RIS) is a revolutionary passive radio technique to facilitate capacity enhancement beyond the current massive multiple-input multiple-output (MIMO) transmission. However, the potential hardware impairment (HWI) of the RIS usually causes inevitable performance degradation and the amplification of imperfect CSI. These impacts still lack full investigation in the RIS-assisted wireless network. This paper developed a robust joint RIS and transceiver design algorithm to minimize the worst-case mean square error (MSE) of the received signal under the HWI effect and imperfect channel state information (CSI) in the RIS-assisted multi-user MIMO (MU-MIMO) wireless network. Specifically, since the proposed robust joint RIS and transceiver design problem yields non-convex characteristics under severe HWI, an iterative three-step convex algorithm is developed to approach the optimality by relaxation and convex transformation. Compared with the state-of-the-art baselines that ignore the HWI, the proposed robust algorithm inhibits the destruction of HWI while raising the worst-case MSE effectively in several numerical simulations. Moreover, due to the properties of the HWI, the performance loss is notable under the magnification of the number of reflected elements in the RIS-assisted MU-MIMO wireless network.

Wireless power transfer (WPT) has emerged to enhance the robustness of the energy harvesting Internet of Things (EH-IoT), whereas beamforming has been leveraged to significantly boost the efficiency of far-field WPT. Nevertheless, potential negative impacts due to high electromagnetic fields (EMF) exposure for radiation-susceptible users have not been thoroughly considered in the design of WPT for EH-IoT with IoT application-level requirements (e.g., coverage). In this article, we explore the health-aware beamforming and IoT selection problem under the EH and human safety constraints. First, we formulate a new optimization problem Health-Aware Beamforming and IoT Selection (HABIS) and prove the NP-hardness. Second, we design an approximation algorithm, named Minimum Radiation Exposure and Maximum IoT Coverage (MREMIC), to exploit the EH-health dependency (EHHD) graph for properly addressing the trade-off between EH efficiency and potential EMF radiation exposure to human bodies. We also discover the optimal health-aware beamforming to minimize the total radiation energy absorption of humans. Simulation results show that MREMIC can effectively charge IoT devices and significantly outperforms existing EH approaches by more than 200% regarding human safety.

Multi-view videos (MVV) have emerged to provide users with immersively interactive experiences with 3D multimedia content. Compared with traditional 2D videos, MVV offers multiple view angles to avoid generating occluded regions from a single viewpoint and allows users to receive different view angles, which consume much higher bandwidth. In this paper, we leverage multicast and view synthesis to effectively reduce the number of transmitted views and total bandwidth consumption in software-defined content delivery networks (SD-CDN). By exploiting the SDN architecture, SD-CDN can optimize traffic engineering and the selection of multi-view sources to serve users. We formulate a new optimization problem, (), prove the NP-hardness, and design an online algorithm with the ideas of View Popularity Cost Ratio, View Watching Possibility, and synthesis tree, to achieve the tightest competitive ratio. The experiment on real networks and implementation in an experimental SDN manifest that the proposed algorithm outperforms state-of-the-art algorithms regarding the total cost, bandwidth consumption, synthesis quality, and link and node utilization.

The emergence of AI has shifted the focus of wireless communications towards deep semantic-level fidelity (i.e., semantic communication networks), emphasizing the significance and effectiveness of transmitted data. However, semantic feature selection considering multicast users with social relations for feature sharing has not been explored. In this paper, we formulate a new optimization problem to minimize the total communication, forwarding, and computation costs, with the proof of NP-hardness and inapproximability. We propose a new algorithm, Multicast Semantic Feature Selection (MSFS), with the notions of Cross Task Semantic Indicator, Substituted Subgraph, and Socially Feature Selection Indicator, to select features on different mobile edge computing servers and cluster the users to receive features via multicast. Simulations with real datasets manifest that MSFS can reduce the total cost by more than 50% compared with state-of-the-art algorithms.

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.

The localization of Road Users (RUs) is an important issue in adverse event prevention due to the unreliable nature of GPS and the high cost of high-precision location acquisition sensors. In addition, previous research on adverse event prevention on roads has not taken into account RUs in blind spots at the same time. To address these issues, we investigate a collaboration system for heterogeneous RUs and Mobile Edge Computing (MEC) servers, called Collaborative Adverse Event Prevention system (CAEP) to efficiently alert RUs to potential adverse events and perceive the blind spot of the RUs. CAEP includes two AI-based functional modules, a localization module and a blind spot detection module, and an adverse event prevention algorithm. The localization module localizes each RU and the blind spot detection module detects the other RUs in the blind spot. The adverse event prevention algorithm jointly considers general road collision events and the event of a difference in radius between the inner wheels of a vehicle to completely include adverse events on the road. We implement CAEP in a real-world traffic environment with Jetson AGX Xavier devices and cameras to evaluate the performance. Our evaluation shows that CAEP provides RUs with sufficient preparation time to prevent adverse events and correctly detects the RUs in blind spots.

Mobile live video streaming is expected to become mainstream in the fifth generation (5G) mobile networks. To boost the Quality of Experience (QoE) of streaming services, the integration of Scalable Video Coding (SVC) with Mobile Edge Computing (MEC) becomes a natural candidate due to its scalability and the reliable transmission supports for real-time interactions. However, it still takes efforts to integrate MEC into video streaming services to exploit its full potentials. We find that the efficiency of the MEC-enabled cellular system can be significantly improved when the requests of users can be redirected to proper MEC servers through optimal user associations. In light of this observation, we jointly address the caching placement, video quality decision, and user association problem in the live video streaming service. Since the proposed nonlinear integer optimization problem is NP-hard, we first develop a two-step approach from a Lagrangian optimization under the dual pricing specification. Further, to have a computation-efficient solution and less performance loss, we provide a one-step Lagrangian dual pricing algorithm by the convex transformation of non-convex constraints. The simulations show that the service quality of live video streaming can be remarkably enhanced by the proposed algorithms in the MEC-enabled cellular system.

Previous research on SDN multicast traffic engineering mainly focused on intra-domain optimization. However, the main traffic on the Internet is inter-domain, and the selection of border nodes and sharing of network information between domains are usually distributed but ignored in previous works. In this article, we explore multi-domain online distributed multicast traffic engineering (MODMTE). To effectively solve MODMTE, we first prove that MODMTE is inapproximable within$|D_{\max }|$, which indicates that it is impossible to find any algorithm with a ratio better than$|D_{\max }|$for MODMTE, and$|D_{\max }|$is the maximum number of destinations for a multicast tree. Then, we design a$|D_{\max }|$-competitive distributed algorithm with the ideas of Domain Tree, Dual Candidate Forest Construction, and Forest Rerouting to achieve the tightest performance bound for MODMTE. Experiments on a real SDN with YouTube traffic manifest that the proposed distributed algorithm can reduce more than 30% of the total cost of bandwidth consumption and rule updates for multicast tree rerouting compared with the state-of-the-art algorithms.

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.

Flow consolidation has been proposed for merging multiple flows from different services into an aggregate flow to remedy the state explosion problem in software-defined networks (SDN). However, we observe that the Quality of Service (QoS) requirements are no longer sustained in aggregate flows since the bandwidth decided by TCP is usually different from the desired rate of each service. Therefore, this article explores an idea to control the rates of only a few service flows so that the rates of all uncontrolled flows allocated by TCP will meet their QoS requirements. We design a new architecture, called Scalable Per-Flow Rate Allocation (SPFRA), and formulate a new optimization problem, termed Scalable Rate Allocation for Aggregate Flows (SRAF), to find a minimum number of controlled flows to increase the scalability of SDN with diverse service requirements. We prove the NP-hardness and inapproximability of SRAF. To solve the problem, we design an algorithm, named Aggregate Flow Selection and Flow Release (AFSFR), to achieve the tightest bound and extend it to support distributed computation and dynamic traffic for instant services. Simulations and implementation on an SDN testbed manifest that AFSFR performs nearly optimally in real networks, and the number of controlled flows can be effectively reduced by 50 percent.

Mobile Edge Computing (MEC) is a promising technique in the 5G Era to improve the Quality of Experience (QoE) for online video streaming due to its ability to reduce the backhaul transmission by caching certain content. However, it still takes effort to address the user association and video quality selection problem under the limited resource of MEC to fully support the low-latency demand for live video streaming. We found the optimization problem to be a non-linear integer programming, which is impossible to obtain a globally optimal solution under polynomial time. In this paper, we formulate the problem and derive the closed-form solution in the form of Lagrangian multipliers; the searching of the optimal variables is formulated as a Multi-Arm Bandit (MAB) and we propose a Deep Deterministic Policy Gradient (DDPG) based algorithm exploiting the supply-demand interpretation of the Lagrange dual problem. Simulation results show that our proposed approach achieves significant QoE improvement, especially in the low wireless resource and high user number scenario compared to other baselines.

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.

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.

Mobile Edge Computing (MEC) is a promising technique in the 5G Era to improve the Quality of Experience (QoE) for online video streaming due to its ability to reduce the backhaul transmission by caching certain content. However, it still takes effort to address the user association and video quality selection problem under the limited resource of MEC to fully support the low-latency demand for live video streaming. We found the optimization problem to be a non-linear integer programming, which is impossible to obtain a globally optimal solution under polynomial time. In this paper, we first reformulate this problem as a Markov Decision Process (MDP) and develop a Deep Deterministic Policy Gradient (DDPG) based algorithm exploiting the supply-demand interpretation of the Lagrange dual problem. Simulation results show that our proposed approach achieves significant QoE improvement especially in the low wireless resource and high user number scenario compared to other baselines.

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%.

Previous research on Segment Routing (SR) mostly focused on unicast, whereas online SDN multicast with segment trees supporting IETF dynamic group membership has not been explored. Compared with unicast SR, online SDN multicast with segment trees is more challenging since finding an appropriate size, shape, and location for each segment tree is crucial to deploy it in more multicast trees. In this paper, we explore Multi-tree Multicast Segment Routing (MMSR) to jointly minimize the bandwidth consumption and forwarding rule updates over time by leveraging segment trees. We prove MMSR is NP-hard and design an online competitive algorithm, named Segment Tree Routing and Update Scheduling (STRUS) to achieve the tightest bound. STRUS includes Segment Tree Merging and Segment Tree Pruning to merge smaller overlapping subtrees into segment trees, and then tailor them to serve more multicast trees. We design Stability Indicator and Reusage Indicator to carefully construct segment trees at the backbone of multicast trees and reroute multicast trees to span more segment trees. Simulation and implementation on real SDNs with YouTube traffic manifest that STRUS outperforms state-of-the-art algorithms regarding the total cost and TCAM usage. Moreover, STRUS is practical for SDN since its running time is about 1 second, even for massive networks with thousands of nodes.

Artificial intelligence (AI) on chips has recently driven the expansion of the Social Internet of Things (SIoT), where a group of SIoT devices with social relations can collaboratively identify and handle local events without the help of remote servers. On the other hand, mobile-edge computing (MEC) is a favorable way to locally process SIoT data for reducing data transmission and computation among SIoT devices and backhaul networks. Nevertheless, the load sharing among SIoT devices, MEC, and remote servers brings about new challenges for the communication and computation tradeoff, cross-layer design in SIoT, and forwarding and aggregation tradeoff. To tackle these issues, we formulate a new optimization problem, namely, SIoT collaborative group and device selection problem (SCGDSP), and prove the NP-hardness. We first explore the intrinsic properties of a fundamental SCGDSP case by finding the optimal collaborative group for each user request. Then, we design an approximation algorithm for the general SCGDSP that first evaluates candidate collaborative groups under different social relations, and then selects the collaborative groups and SIoT devices properly. For scalability, the proposed algorithm also supports dynamic user requests and can be distributionally deployed in massive networks enabling collaborative MEC. Moreover, it also sustains local SIoT services, where the computation only involves SIoT devices and MEC servers. Simulation results demonstrate that effective SIoT and collaborative group selection (ESCGS) can reduce by more than 50% of the total communication and computation costs compared with baseline schemes in the real networks from topology zoo. Moreover, the distributed ESCGS reduces by 87% of the running time with total 16.5-MB message overhead, requiring no more than 0.05-ms transmission delay in a 100-Gb/s backbone network with eight MEC servers, 1000 SIoTs, and 800 monitored locations.

Due to the fact that the higher density of mobile devices is expected, the fifth generation (5G) mobile networks introduce small cell networks (SCNs) to prevent exhausting radio resources. SCNs improve radio spectrum utilization by deploying more base stations (BSs) in the networks. Even though authenticated key exchange (AKE) is still essential to ensure entity authentication and confidentiality in mobile communications. Besides, user anonymity is required to guarantee the footprints of mobile communications being concealed. However, AKE with user anonymity may increase the latency of communications dramatically in total due to several times more frequency in SCNs. The increase of latency will be more serious when an AKE protocol supports user anonymity, where traceability and revocability to users are necessary. Thus, this paper presents a secure region-based handover scheme (ReHand) with user anonymity and fast revocation for SCNs. ReHand greatly reduces the communication latency when user equipments (UEs) roam between small cells within the region of a macro BS, i.e., eNB, and the computation costs due to the employment of symmetry-based cryptographic operations. Compared to the three related prior arts, ReHand dramatically reduces the latency from 82.92% to 99.99% by region-based secure handover. Nevertheless, this paper demonstrates the security of ReHand by theoretically formal proofs.

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%.

Online social networks have become the medium for efficient viral marketing exploiting social influence in information diffusion. However, the emerging application Social Coupon (SC) incorporating social referral into coupons cannot be efficiently solved by previous researches which do not take into account the effect of SC allocation. The number of allocated SCs restricts the number of influenced friends for each user. In the paper, we investigate not only the seed selection problem but also the effect of SC allocation for optimizing the redemption rate which represents the efficiency of SC allocation. Accordingly, we formulate a problem named Seed Selection and SC allocation for Redemption Maximization (S3CRM) and prove the hardness of S3CRM. We design an effective algorithm with a performance guarantee, called Seed Selection and Social Coupon allocation algorithm. For S3CRM, we introduce the notion of marginal redemption to evaluate the efficiency of investment in seeds and SCs. Moreover, for a balanced investment, we develop a new graph structure called guaranteed path, to explore the opportunity to optimize the redemption rate. Finally, we perform a comprehensive evaluation on our proposed algorithm with various baselines. The results validate our ideas and show the effectiveness of the proposed algorithm over baselines.

Traffic engineering (TE) and efficient network updating have been considered as separate problems in previous SDN research. Traffic engineering mostly focuses on static traffic and does not consider the rerouting overheads to support dynamic traffic. Efficient network updating assumes the new routing is provided by TE and focuses on minimizing only the rerouting overheads, and therefore, the improved new routing with bandwidth consumption similar to the new routing from TE but much lower rerouting overheads has not been explored. In this paper, we explore Multi-tree Low-overhead Multicast Rerouting (MLMR) to jointly solve both problems for SDN multicast. We prove that MLMR is NP-hard and design a new approximation algorithm, named Multicast Rerouting and Update Scheduling Algorithm (MRUSA). Equipped with the notions of deterioration indicator, motivator, and inhibitor, MRUSA provides incremental tree updating and multi-tree update scheduling to address the trade-off between the bandwidth consumption and rerouting overheads. Frequent rerouting due to tiny changes of multicast users can be effectively avoided, because rerouting time for each group can be correctly identified. Simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 35% compared with SPT and ST, and the computation time is small for massive SDN.

Internet of Things (IoT) has been regarded as one of the most significant network paradigms in the future. For IoT, it is crucial to ensure the correctness of detection which includes the factors of accuracy and precision. On the other hand, Mobile Edge Computing (MEC) has emerged as a promising way to process big IoT data at the network edge so as to reduce the computation and transmission energy in the networks. In this paper, we explore the energy minimization problem in MEC networks by considering both the accuracy and precision requirements of IoT. Specifically, given 1) a set of IoT devices, 2) a set of observed targets, 3) an MEC network, 4) the energy consumption model, and 5) the accuracy and precision requirements, we formulate a new optimization problem, named Accuracy and Precision-Aware IoT Device Selection (APAIDS), to minimize the overall energy consumption in MEC networks. We prove the NP-hardness of APAIDS and then propose a new algorithm, named Energy Efficient Device and MEC Server Selection (EDMS), to minimize energy consumption by jointly selecting IoT devices, configuring MEC association, and selecting processing servers for dealing with the data of each target. Finally, we evaluate EDMS on two real networks. In comparison with the baseline schemes, the results manifest that the overall energy consumption can be reduced by more than 60%.

Traditional IEEE 802.11 network is designed for the use of small scale local wireless networks. However, the emergence of the Internet of Things (IoT) has changed the scene of wireless communications. Thus, recently, the IEEE task group ah (TGah) has been dedicated to the standardization of a new protocol, called IEEE 802.11ah, which is customized for this type of large-scale networks. IEEE 802.11ah adopts a grouping-based MAC protocol to reduce the contention overhead for each group of devices. However, most existing designs simply randomly partition devices into groups, and less attention has been paid to the problem of forming efficient groups. Therefore, in this paper, we argue that the performance of grouping is closely related to heterogeneity in traffic demands of devices, and propose a traffic-aware grouping algorithm to improve channel utilization. Since channel utilization of a group closely depends on the collision probability, we further derive a regression-based analytical model to estimate the contention success probability with consideration of sensors' heterogeneous traffic demands. The evaluation via NS-3 simulations shows that the proposed regression-based model is quite accurate even when clients have diverse traffic demands, and our traffic-aware grouping outperforms other baseline approaches, especially when the network is nearly saturated.

This paper proposes a dynamic precoding and power allocation policy for mutually cooperative device-to-device (D2D) transmitter-receiver pairs that underlay a cellular system in the uplink. The cooperative transmission consists of two phases: a data-sharing phase (i.e., phase 1) and a joint transmission phase (i.e., phase 2). Multicast precoders are used in phase 1 and coordinated block-diagonalization precoders are considered in phase 2. The precoders are jointly designed to maximize the long-term utility of the D2D users subject to long-term individual power and rate-gain constraints and an instantaneous interference constraint at the base-station. The long-term objective and constraints allow cooperating users to adapt their resources more flexibly over time, but increase the complexity of the design. By adopting the Lyapunov optimization framework and by constructing virtual queues to record the temporal evolution of the system states, the long-term utility maximization problem can be decoupled into a series of short-term weighted-rate-minus-energy-penalty (WRMEP) optimization problems that can be solved efficiently. A low-complexity algorithm is further proposed for solving the WRMEP problem when multicasting in the data-sharing phase is performed by a spatially white input. Theoretical performance guarantees and a bound on the virtual queue backlogs are also derived.

This paper proposes a robust joint transceiver and power splitting (PS) design according to a minimax mean-squar-error (MSE) scheme for multiuser multi- input multi-output (MU-MIMO)simultaneous wireless information and power transfer (SWIPT) system. The proposed scheme considers channel uncertainty as a bound on the spectral matrix norm of each estimated error. Since the proposed robust minimax MSE design problem jointly optimizes the precoder, the equalizers and the PS factors, the proposed design problem is non-convex and non-deterministic polynomial-time hard (NP-hard). Thus, we transform the original optimization problem into an iteratively linear matrix inequalities (LMIs)- constrained optimization problem, which can be solved efficiently by the convex optimization toolbox. According to the simulation results of the MU-MIMO PS SWIPT wireless system with the benchmark of robust precoder, the proposed method can validate the theoretical analysis to achieve robust transceiver design effectively.

Live video streaming applications are expected to proliferate very rapidly in the next generation network, i.e., 5G networks. To efficiently serve all users watching the same live video in 5G networks, the multicast technique plays an important role in providing scalable and high-performance services. Software-Defined Networking (SDN), contained in 5G networks, further facilitates the development of multicast techniques due to its flexibility of updating routing rules. However, few of conventional multicast mechanisms in SDN take into account the rule update overhead resulting from handovers of mobile users, which leads to tremendous network overhead. In this paper, we adopt Segment Routing (SR) as the first step to alleviate the rule update overhead, and then consider the rule update cost while maintaining the multicast tree to deal with user handovers. Thus, we first formulate Handover-aware Multicast Tree (HMT) problem and then show that HMT is NP-hard and does not admit any approximation algorithm. We then propose a heuristic algorithm called Mobility Aware Multicast Tree Algorithm (MAMTA). MAMTA takes advantage of user movement prediction to assign a base station that could provide longer service to a user, which leads to infrequent rule updates. Simulation results show that MAMTA significantly outperforms the shortest path tree and Steiner tree algorithms.

With the emergence of multi-view 3D videos, network operators now face a new challenge to resolve the dramatic increase of the network bandwidth required to support all subscribed views (typically 16 or 32) of a video. Recently, Depth-Image-Based Rendering (DIBR) in Computer Vision has been demonstrated as a promising way for efficient multi-view 3D video multicast, because many views can be synthesized in mobile devices and no longer need to be transmitted. Nevertheless, DIBR is computationally intensive and incurs additional power consumption in mobile devices, and unsubscribed views need to be transmitted to mobile users for DIBR. In this paper, therefore, we aim to leverage Mobile Edge Computing (MEC) for DIBR to foster effective and efficient multi-view video multicast. We formulate a new problem, named Multi-view Multicast Synthesis and Delivery (MMSD) and prove the NP-Hardness. We design an approximation algorithm, named Merge Search Forest Algorithm (MSFA), to choose the view to be synthesized and build a multicast topology including a low-cost forest for supporting each subscribed view. Simulation results manifest that MSFA outperforms the existing approaches by 30% to 50% of the total communication and computation cost.

This work examines joint beamforming and power allocation schemes as well as trajectory learning and clustering mechanisms for dynamically connectable unmanned aerial vehicle (UAV) base- stations (BSs). Here, UAV-BSs are allowed to join together dynamically and form physically-connected collocated antenna arrays that enable joint transmission and cooperative energy sharing among the connected UAVs. A joint design of the transmit powers and beamformers in each time slot is first proposed based on the maximization of the sum signal-to-leakage-plus-noise-ratio (SLNR) of all users. The solution is obtained via alternating optimization where the transmit powers and beamformers are optimized in turn until convergence. Then, based on the per-time-slot design, a dynamic UAV moving and clustering policy is proposed where the expected sum rate of the system is maximized while adapting to changes in the users' locations and environment. Here, UAV locations are adjusted gradually in each time slot according to the stochastic gradient of the expected system sum rate. The UAV clusters are updated every T time slots by combining the two clusters that yield the maximum increase in the expected system sum rate. Simulations are provided to demonstrate the effectiveness of the proposed schemes.

Mobile Edge Computing (MEC) has recently emerged as a primary candidate for big data processing to reduce the latency and jitter. On the other hand, Software-Defined Internet of Things (SD-IoT) has been proposed to effectively and flexibly collect and process big IoT data. Nevertheless, minimizing the energy consumption in SD-IoT with big data processing (e.g., data aggregation and reconstruction) has not been explored before. In this paper, therefore, we explore the sensor data selection and routing problem in SD-IoT with big data processing. Specifically, given 1) a set of sensors, 2) a set of observed locations, 3) the network topology, and 4) the energy consumption model of big data processing and forwarding, we formulate a new optimization problem, named Sensor Data Selection, Processing, and Routing Problem (SDSPRP), to minimize the total energy consumption in SD-IoT. We prove that the emphasized problem is NP-hard and inapproximable within O(log|K|). To solve the problem, we propose an αlog|K|- approximation algorithm, called Energy Efficient Sensor Selection and Routing (ESR), to minimize the energy consumption by jointly considering the sensor selection and the energy consumption in traffic engineering and data processing. The proposed algorithm is evaluated on two real networks, and the results manifest that the energy consumption in SD- IoT can be reduced by more than 56%.

Previous research on SDN traffic engineering mostly focuses on static traffic, whereas dynamic traffic, though more practical, has drawn much less attention. Especially, online SDN multicast that supports IETF dynamic group membership (i.e., any user can join or leave at any time) has not been explored. Different from traditional shortest-path trees (SPT) and graph theoretical Steiner trees (ST), which concentrate on routing one tree at any instant, online SDN multicast traffic engineering is more challenging because it needs to support dynamic group membership and optimize a sequence of correlated trees without the knowledge of future join and leave, whereas the scalability of SDN due to limited TCAM is also crucial. In this paper, therefore, we formulate a new optimization problem, named Online Branch-aware Steiner Tree (OBST), to jointly consider the bandwidth consumption, SDN multicast scalability, and rerouting overhead. We prove that OBST is NP-hard and does not have a |Dmax|1-ε-competitive algorithm for any , where |Dmax| is the largest group size at any time. We design a |Dmax|-competitive algorithm equipped with the notion of the budget, the deposit, and Reference Tree to achieve the tightest bound. The simulations and implementation on real SDNs with YouTube traffic manifest that the total cost can be reduced by at least 25% compared with SPT and ST, and the computation time is small for massive SDN.

This paper describes EcoMicro, a miniature, self-powered, wireless inertial-sensing node in the volume of 8 x 13 x 9.5 mm3, including energy storage and solar cells. It is smaller than existing systems with similar functionality while retaining rich functionality and efficiency. It is capable of measuring motion using a inertial measurement unit (IMU) and communication over Bluetooth Low Energy (BLE) protocol. It is self-powered by miniature solar cells and can perform maximum power point tracking (MPPT). Its integrated energy-storage device combines the longevity and power density of supercapacitors with the relatively flat discharge curve of batteries. Our power-ground gating circuit minimizes leakage current during sleep mode and is used in conjunction with the real-time-clock for duty cycling. Experimental results show EcoMicro to be operational and efficient for a class of wireless sensing applications.

Interference mitigation among body area networks (BANs) has been a critical challenge due to their mobility and fully distributed nature. When two or more nearby BANs transmit simultaneously, collisions may occur and body sensors therefore consume more energy for re-transmission. Each BAN thus spends more channel time, which lowers the total network capacity. To reduce energy consumption and better the network capacity, in this paper, we propose a CSMA/CA-based Load Adaptive MAC Protocol for inter-BAN, called LAMP. Based on Markov chain analysis, LAMP can dynamically choose a proper contention window size according to the load in the operating channel and automatically switch to another channel when the current channel is near congested. Simulation results show that LAMP outperforms traditional CSMA/CA protocols in terms of throughput and energy consumption. Meanwhile, it keeps high fairness.

Most existing or currently developing Internet of Things (IoT) communication standards are based on the assumption that the IoT services only require low data rate transmission and therefore can be supported by limited resources such as narrow-band channels. This assumption rules out those IoT services with burst traffic, critical missions, and low latency requirements. In this paper, we propose to utilize the idle devices in mission-critical IoT networks to boost the transmission data rate for critical tasks through multiple concurrent transmissions. This approach virtually expands the existing narrow-band IoT protocols to break the bandwidth limitation in order to provide low latency services for critical tasks. In this approach, we propose the task-balance method and the first-link descending order to determine the relay order and data partition in a given relay set. We theoretically prove that the optimal relay configuration that minimizes the uploading latency in single source scenario can be derived by the proposed algorithms in polynomial time when we have sufficient number of available channels. We also propose a greedy algorithm to approximate the optimal solution within a 1/2 performance lower bound in general scenarios. The simulation results shows that the proposed approach can reduce the latency of critical tasks up to 76% comparing with traditional approaches.

Local user access is important to machine-to-machine (M2M) communication because it possesses unique advantages over remote access in that it offers instant services, provides reliable connection, and offloads the traffic of M2M access networks. Local access control is also essential for authorized users to access M2M devices. In this paper, we propose a local authentication and access control scheme (LACS), which allows M2M devices to locally verify the access rights and access privileges of the users. In particular, the property of device heterogeneity is considered in our LACS. The resource-constrained M2M devices can securely outsource heavy computation to user equipment with or without the help of a gateway for energy saving. Our LACS satisfies the security criteria of: 1) user anonymity; 2) mutual authentication; 3) secure key agreement; and 4) securely outsourcing computation. All of these criteria are theoretically proved using a formal model. Experimental data also demonstrates the efficiency of the proposed LACS and the effectiveness of the design with regard to computation offloading.

Most scheduling algorithms in the literature for cellular networks are concerned with throughput, fairness, or cost optimization. Recently, however, wireless surveillance in cellular networks has become increasingly important, and more and more institutions and companies have adopted commercial cellular surveillance cameras due to their low installation cost and the wide network coverage. In this paper, therefore, we first explore the resource allocation problem for a multi-camera surveillance system in cellular networks. We minimize the number of allocated resource blocks (RBs) while simultaneously ensuring the coverage requirement for the surveillance system in cellular networks. Specifically, we first describe our system model and then formulate the Camera Set Resource Allocation Problem (CSRAP). Next, we prove that the problem is NP-hard and inapproximable within ln n, where n is the number of surveillance targets. To solve the problem, we propose an approximation algorithm for the general case of CSRAP and then we find the optimal solutions of three deployments of cameras in the Manhattan Street Network to find the intrinsic characteristics of camera selections. The simulation results, based on two real surveillance maps and synthetic datasets, show that the number of allocated RBs can be effectively reduced compared to the existing approach for cellular networks.

Multi-user multiple input multiple output (MU-MIMO) enables a multi-antenna access point to serve multiple users simultaneously, and has been adopted as the IEEE 802.11ac standard. While several PHY-MAC designs have recently been proposed to improve the throughput performance of a MU-MIMO WLAN, they, however, usually assume that all the concurrent streams are of roughly equal length. In reality, users usually have frames with heterogeneous lengths even after aggregation, leading to different lengths of a transmission time. Hence, the concurrent transmission opportunities might not always be fully utilized when some streams finish earlier than the others in a transmission opportunity. To resolve this inefficiency, this paper presents full degree-of-freedom (FDoF), a PHY-MAC design that exploits a novel power allocation scheme to reduce the idle channel time and further leverages frame padding to better utilize the spatial multiplexing gain. Unlike traditional MIMO power allocation, which aims at maximizing the theoretical sum-rate, FDoF's power allocation explicitly considers heterogeneous frame lengths and minimizes the channel time required to finish concurrent frames, as a result improving the effective throughput. FDoF's padding protocol then identifies proper users to reuse the remaining idle channel time, while preventing this padding from harming all the ongoing streams. Our evaluation via large-scale trace-driven simulations demonstrates that FDoF's improves the throughput by up to 2.83×, or by 1.36× on average, as compared to the conventional 802.11ac. By combining FDoF's power allocation with frame padding, the average throughput gain can be further increased to 1.75×.

This work proposes a multiuser hybrid beamforming scheme for non-orthogonal multiple access (NOMA) systems using the minimum mean square error (MMSE) approach to weighted sum rate maximization. While NOMA may be effective in terms of enhancing user fairness, hybrid beamforming is necessary to reduce the transceiver cost as the system moves towards higher frequency. The design is divided into two stages. In the first stage, a fully digital multiuser beamformer is derived by maximizing the weighted sum rate of all users under no constraint on the number of RF chains. This problem is then transformed into a weighted sum MSE minimization problem, which facilitates the use of alternating optimization to obtain an efficient local solution. In the second stage, the previously obtained multiuser beamformer is then split into RF and baseband beamformers by using orthogonal matching pursuit (OMP). A user role selection algorithm is then proposed to determine the role of strong and weak users. Simulation results are provided to demonstrate the effectiveness of the proposed schemes.

Most existing or developing IoT communication standards are based on the assumption that IoT services only require low data rate transmission and therefore can be supported by limited resources such as narrow-band channels. This assumption rules out those IoT services with burst traffic, critical tasks, and low latency requirements. In this paper, we propose to utilize idle devices in IoT networks to boost the transmission data rate for critical tasks through multiple concurrent transmissions. This approach virtually expands the existing narrow-band IoT protocols to support channel aggregation in order to realize low latency services for critical tasks in IoT networks. We propose task-balance method (TBM) and first-link descending order (FDO) to determine the relay order and data partition in a given relay set. We theoretically prove that the optimal relay configuration that minimizes the uploading latency can be derived in polynomial time. We then show that relay selection problem is NP-hard and propose a greedy algorithm to approximate the optimal solution within a 1/2 performance lower bound. The simulation results shows that the proposed approach can reduce the latency of critical tasks up to 76% comparing with traditional approaches.

Software-Defined Networking and Network Function Virtualisation (SDN/NFV) can provide flexible resource allocation to support innovative security solutions in a central manner. To mitigate HTTP DDoS attacks, shuffling-based moving target defense has been regarded as one of the most effective ways by redirecting user traffic among a group of virtualized service functions. However, previous work did not notice that frequent changes of user traffic will significantly intensify the control overhead of SDN. In this paper, therefore, we first model the effectiveness and cost for shuffling in SDN/NFV networking with Multi-Objective Markov Decision Processes to find the optimal tradeoff between the effectiveness and cost. We then propose a cost-effective approximation algorithm with a guarantee performance bound to solve the problem. Simulation and implementation on an experimental SDN/NFV network manifest that, given 100 attackers among 1000 users and 50 virtualized functions of a web service, our algorithm achieves the approximation ratio of 0.68 and imposes only 2.4s rule modification latency for each shuffle.

Network Function Virtualization (NFV) on Software-Defined Networks (SDN) can effectively optimize the allocation of Virtual Network Functions (VNFs) and the routing of network flows simultaneously. Nevertheless, most previous studies on NFV focus on unicast service chains and thereby are not scalable to support a large number of destinations in multicast. On the other hand, the allocation of VNFs has not been supported in the current SDN multicast routing algorithms. In this paper, therefore, we make the first attempt to tackle a new challenging problem for finding a service forest with multiple service trees, where each tree contains multiple VNFs required by each destination. Specifically, we formulate a new optimization, named Service Overlay Forest (SOF), to minimize the total cost of all allocated VNFs and all multicast trees in the forest. We design a new 3ρST-approximation algorithm to solve the problem, where ρSTdenotes the best approximation ratio of the Steiner Tree problem, and the distributed implementation of the algorithm is also presented. Simulation results on real networks for data centers manifest that the proposed algorithm outperforms the existing ones by over 25%. Moreover, the implementation of an experimental SDN with HP OpenFlow switches indicates that SOF can significantly improve the QoE of the Youtube service.

With software-defined network (SDN) and network function virtualization (NFV) techniques, we can embed the service chain consisting of a sequence of virtualized network functions (VNFs), i.e., we can determine the flow path and deploy the VNFs contained in the service chain at any place on the path. In the literature, the methods of service chain embedding bound the number of VNFs at a node, whereas the link capacities are disregarded and the amount of flows is not considered, which could cause serious congestion. In addition, according to our experiment, the process overhead on a computation node is linear to the total amount of flows processed. In this paper, we propose a method of service chain embedding to maximize the total amount of flows while bounding the process overhead of the flows on a node by its computation capability and the total amount of flows on an link by its bandwidth capacity. To our knowledge, our method is the first approximation algorithm of service chain embedding with considering flow in the literature. Simulations show our algorithm has good performance in terms of the total amount of flows.

Multi-User Multiple Input Multiple Output (MU-MIMO) enables a multi-antenna access point (AP) to serve multiple users simultaneously, and has been adopted as the IEEE 802.11ac standard. While several PHY-MAC designs have recently been proposed to improve the throughput performance of a MU-MIMO WLAN, they, however, usually assume that all the concurrent streams are of roughly equal length. In reality, users usually have frames with heterogeneous lengths even after aggregation, leading to different lengths of transmission time. Hence, the concurrent transmission opportunities might not always be fully utilized when some streams finish earlier than the others in a transmission opportunity (TXOP). To resolve this inefficiency, this paper presents acPad, a PHY-MAC design that adds additional frames to fill up the idle channel time and better utilize the spatial multiplexing gain. Our acPad identifies proper users as the padding so as to improve the padding gain, while preventing this padding from harming all the ongoing streams. Our evaluation via large-scale trace-driven simulations demonstrates that acPad improves the throughput by up to 2.83×, or by 1.36× on average, as compared to the conventional 802.11ac.

Cognitive radios (CRs) are proposed to alleviate the huge need for radio spectrum. There are two known steps for a pair of CRs to start communication: the rendezvous and data-channel negotiation. Despite that the rendezvous can be achieved by some well-studied techniques such as the channel hopping, the strategies for data-channel negotiation receive much less attention and their impact on data transmission performance remains unclear. In this paper, we study existing data-channel negotiation schemes for channel-hopping CRs and observe that 1) for short data transmission, they incur a huge overhead, called notification delay, that severely limits the throughput; and 2) for long data transmission, they lead to large overhead, called interruption delay, in handling the PU interruption, which makes performance unstable. By carefully re-examining the steps toward low-overhead and stable data transmission, we argue that a key step, called self-channel selection, is missing and should precede the rendezvous and data channel selection steps. In this step, each CR selects, in a distributed manner, only a small amount of the most stable channels to be used in the later steps. To realize the self-channel selection, we introduce a Randomly-Started Stability-Descent (RSSD) selection algorithm. Expensive simulations are conducted and the results demonstrate the effectiveness of RSSD in reducing 1) the notification delay; 2) the chance of PU interruption; and 3) the interruption delay if PU interruption occurs, which overall improve the performance and quality of data transmission.

Most prior algorithms for influence maximization focused are designed for Online Social Networks (OSNs) and require centralized computation. Directly deploying the above algorithms in distributed Mobile Social Networks (MSNs) will overwhelm the networks due to an enormous number of messages required for seed selection. In this paper, therefore, we design a new cross-layer strategy to jointly examine MSN and mobile ad hoc networks (MANETs) to facilitate efficient seed selection, by extracting a subset of nodes as agents to represent nearby friends during the distributed computation. Specifically, we formulate a new optimization problem, named Agent Selection Problem (ASP), to minimize the message overhead transmitted in MANET. We prove that ASP is NP-Hard and design an effectively distributed algorithm. Simulation results in real and synthetic datasets manifest that the message overhead can be significantly reduced compared with the existing approaches.

Deep packet filtering (DPF) has been demonstrated as an essential technique for effective fine-grained access controls, but it is commonly recognized that the technique may invade the individual privacy of the users. Secure computation can address the tradeoff between privacy and DPF functionality, but the current solutions limit the scalability of the network due to the intensive computation overheads and large connection setup delay, especially for the latest network paradigm, network function virtualisation (NFV) and software-defined network (SDN). In this paper, therefore, we propose a privacy-preserving deep packet filtering protocol, named DPF-ET, that can efficiently perform filtering function over encrypted traffic while diminishing the communication overhead and setup delay for the controller in SDN. DPF-ET guarantees the data privacy for users and remains rule privacy for the network owner. The implementation results on an experimental HP SDN/NFV platform demonstrate that the proposed DPF-ET outperforms the current approaches by reducing 250 times in the communications overhead and 32 times in the setup delay.

This work examines the user-pair selection problem for distributed-input distributed-output (DIDO) wireless systems. A DIDO system refers to a network of densely deployed transmitter and receiver pairs, where the transmitters are connected to and coordinated by a DIDO server. The system sum rate is known to grow without bound as the number of transmitter-receiver pairs increases. However, when zero-forcing (ZF) beamforming is adopted across the transmitters (as assumed in most existing works on DIDO), the effect of power amplification due to ill-conditioned channel matrices may significantly reduce the system sum rate. In this work, a decremental user-pair selection (DUPS) algorithm is proposed to determine the set of transmitter-receiver pairs that should be simultaneously active in order to reduce the impact of power amplification and increase the system sum rate. A low-complexity variant of DUPS is also proposed and an asymptotic lower bound of its sum rate is derived using extreme value theory. Moreover, inspired by the semi-orthogonal user selection (SUS) algorithm, often adopted in the conventional multiple-input multiple-output (MIMO) literature, a semi-orthogonal DUPS algorithm is also proposed by taking into consideration the orthogonality of the users' channel vectors in the selection process. Simulations are provided to demonstrate the effectiveness of the proposed schemes.

Although Software-Defined Networking (SDN) enables flexible network resource allocations for traffic engineering, current literature mostly focuses on unicast communications. Compared to traffic engineering for multiple unicast flows, multicast traffic engineering for multiple trees is very challenging not only because minimizing the bandwidth consumption of a single multicast tree by solving the Steiner tree problem is already NP-Hard, but the Steiner tree problem does not consider the link capacity constraint for multicast flows and node capacity constraint to store the forwarding entries in Group Table of OpenFlow. In this paper, therefore, we first study the hardness results of scalable multicast traffic engineering in SDN. We prove that scalable multicast traffic engineering with only the node capacity constraint is NP-Hard and not approximable within δ, which is the number of destinations in the largest multicast group. We then prove that scalable multicast traffic engineering with both the node and link capacity constraints is NP-Hard and not approximable within any ratio. To solve the problem, we design a δ-approximation algorithm, named Multi-Tree Routing and State Assignment Algorithm (MTRSA), for the first case and extend it to the general multicast traffic engineering problem. The simulation and implementation results demonstrate that the solutions obtained by the proposed algorithm outperform the shortest-path trees and Steiner trees. Most importantly, MTRSA is computation-efficient and can be deployed in SDN since it can generate the solution with numerous trees in a short time.

We implement a collision prevention system, called pSafety, which instantaneously informs pedestrians and drivers of the potential threatening accidents. Unlike other systems, pSafety alerts pedestrians of threatening vehicles coming from not only the line-of-sight, but also non-line-of-sight due to obstructions of the wall corner or other vehicles. pSafety collects GPS information from smartphones of pedestrians and vehicle drivers through mobile networks. The main challenge of pSafety is that current smartphones demonstrate larger distance errors on the order of a few meters due to its intrinsic low-cost GPS receivers. To address the impact of large-error positioning to pSafety, we regard each participant on the map as a sector that indicates a predicted location. We subsequently design the Sector Overlap Detection Algorithm, called SODA, to detect whether two sectors are overlapping in time O(1). To avoid warning fatigue, we additionally provide a threat ranking method to evaluate the degree of risk for each potential collision event. Through our designed App, pedestrians and drivers both could receive a clear view of potential risks and then take proper actions to avoid accidents. In our implementation, we show that pSafety rapidly informs participants (i.e., pedestrians and drivers) and provides each participant a sufficient response time to avoid collision.

Carrier aggregation is introduced in LTE-Advanced to aggregate multiple bands of spectrum into a virtual carrier. User equipment (UE) with carrier aggregation capability can increase peak data rates by transmitting through an aggregated virtual carrier that provides greater transmission bandwidth. Nevertheless, further study is needed to determine how carrier aggregation should best be implemented and configured to effectively address the range of UE carrier quality and their heterogeneous quality of service (QoS) requirements. In addition, most existing resource allocation methods rely on the assumption that UE always reports information truthfully, which may be unrealistic when UEs act rationally from a game-theory perspective. To address these concerns, we provide a strategy-proof auction approach to carrier aggregation design in an LTE-Advanced system. We first formulate the resource allocation problem in carrier aggregation as a non-linear optimization problem, which is proved to be NP-hard. We then propose a strategy-proof auction with a greedy resource allocation algorithm to 1) find an efficient carrier activation and resource allocation solution under the QoS requirements of UEs, and 2) guarantee that all rational UEs truthfully report their QoS requirements. Finally, we conduct extensive simulations to evaluate system performance for the proposed auction design.

The traditional IEEE 802.11 network is designed for the use of small scale local wireless networks such as home or campus WLANs, where one access point serves a reasonably few number of devices like smartphones, laptops, tablets, and so on. However, the emergence of the Internet of Things (IoT) have changed the scene of wireless communications, while the number of devices rapidly increases and becomes far larger than before. Thus, recently, the IEEE task group ah (TGah) is dedicated to the standardization of a new protocol, called IEEE 802.11ah, which is customized for this type of large-scale networks. IEEE 802.11ah adopts the grouping-based MAC protocol to reduce the contention overhead of each group of devices. However, most existing designs simply randomly assign devices to groups, and less attention has been paid to the problem of forming efficient groups. Therefore, in this paper, we argue that the performance of grouping is closely related to the heterogeneous traffic demands of devices, and propose a load-balanced grouping algorithm to improve channel utilization of each group. Our evaluation shows that the proposed load-balanced grouping outperforms simple random grouping, especially when the network is almost saturated.

With the ubiquity of social networks and mobile devices, various new mobile applications for impromptu group formation and communications have emerged recently, such as Meetup, Plancast, Yahoo! Upcoming, Eventbrite and Epinions. Among those important applications, finding a dense subgraph in a social network plays a crucial role, but the current algorithms are only designed for online social networks. Different from online social networks, no central repository is available in mobile social networks (MSNs). Finding a dense subgraph in a distributed manner without compromising the individual privacy is very challenging, because a dense subgraph usually includes abundant friendship information. To address this important need for MSNs, we propose a privacy-preserving k-core discovery protocol, named PKcore. We show that the solution group returned by our protocol is optimal. In addition, we guarantee that the MSN users in our protocol do not reveal any social links to both the initiator and the other contacts. We also prove that the privacy properties based on Canetti's model always hold. Finally, we analyze the computation and communication overheads and show that our protocol is feasible for current mobile devices.

Wireless surveillance in cellular networks has become increasingly important, while commercial LTE surveillance cameras are also available nowadays. Nevertheless, most scheduling algorithms in the literature are throughput, fairness, or profit-based approaches, which are not suitable for wireless surveillance. In this paper, therefore, we explore the resource allocation problem for a multi-camera surveillance system in 3GPP Long Term Evolution (LTE) uplink (UL) networks. We minimize the number of allocated resource blocks (RBs) while ensuring the coverage requirement for surveillance systems in LTE UL networks. Specifically, we formulate the Camera Set Resource Allocation Problem (CSRAP) and prove that the problem is NP-Hard. We then propose an Integer Linear Programming formulation for general cases to find the optimal solution. Moreover, we present a baseline algorithm and devise an approximation algorithm to solve the problem. Simulation results based on a real surveillance map and synthetic datasets manifest that the number of allocated RBs can be effectively reduced compared to the existing approach for LTE networks.

In a Wireless Local Area Network (WLAN), clients typically associate with the AP that offers the maximal signal strength. Later works on client-AP association then further take load balancing and fairness into consideration. Those schemes however are not directly applicable in a multiuser MIMO (MU-MIMO) WLAN since different combinations of clients result in different throughput of each individual client. Therefore, in this paper, we present a client-AP association algorithm customized for MU-MIMO WLANs. The proposed algorithm jointly solves the problems of client-AP association and MU-MIMO client grouping with consideration of channel correlation among clients. It hence allows a good group of clients, i.e., those with low channel correlation, to together associate with the same proper AP and achieve a high sum-rate. The simulation results show that our MU-MIMO AP association algorithm improves the aggregate throughput by about 11%-28% and 26%-45%, as compared to two common association approaches, i.e., RSSI-based and load-based schemes, respectively.

In conventional LTE networks, user equipments (UEs) access the network via a four-step random access procedure. When small amount of data is transmitted, such as in the scenarios of machine-type communications (MTC), signaling overhead resulted from the random access procedure becomes a critical issue. To enable an efficient small data transmission, a direct access scheme utilizing code division multiplexing (CDM) is proposed in this paper. Instead of transmitting on the resource blocks indicated by eNB, UEs randomly select resource blocks for direct data transmission without signaling eNB, with CDM used to resolve the collision problem. Under the proposed architecture, however, the data transmission is inherently non-orthogonal and the eNB has to detect the data without any information from UEs, making the receiver too complex to implement. To ease the burden of the receiver, we design a pseudo-random resource selection scheme such that the search space of the data detection is reduced. The analysis and simulation results show the advantage of using the proposed direct access scheme to improve the efficiency of small data transmission in cellular networks.

Current traffic engineering in SDN mostly focuses on unicast. By contrast, compared with individual unicast, multicast can effectively reduce network resources consumption to serve multiple clients jointly. Since many important applications require reliable transmissions, it is envisaged that reliable multicast plays a crucial role when an SDN operator plans to provide multicast services. However, the shortest-path tree (SPT) adopted in current Internet is not bandwidth-efficient, while the Steiner tree (ST) in Graph Theory is not designed to support reliable transmissions since the selection of recovery nodes is not examined. In this paper, therefore, we propose a new reliable multicast tree for SDN, named Recover-aware Steiner Tree (RST). The goal of RST is to minimize both tree and recovery costs, while finding an RST is very challenging. We prove that the RST problem is NP-Hard and inapproximable within k, which is the number of destination nodes. Thus, we design an approximate algorithm, called Recover Aware Edge Reduction Algorithm (RAERA), to solve the problem. The simulation results on real networks and large synthetic networks, together with the experiment on our SDN testbed with real YouTube traffic, all manifest that RST outperforms both SPT and ST. Also, the implementation of RAERA in SDN controllers shows that an RST can be returned within a few seconds and thereby is practical for SDN networks.

This paper proposes an energy-efficient private matching for secure two-party computation, called SafeMatch, in mobile social networks (MSNs). The proposed SafeMatch utilizes locality sensitive hashing (LSH) to sample the social data and protects social samples with cryptographic hash functions and one-time padding. Given acceptable tolerance rate and error rate, our proposed SafeMatch provides lightweight computation cost regardless the size of social data set. To guarantee the soundness of the proposed SafeMatch, we define its privacy and prove its security. Empirical experiment results on smart phones show that SafeMatch achieves orders of magnitude improvement in energy consumption compared to the homomorphic encryption based protocol.

Fountain codes are linear codes with low complexities. LT (Luby Transform) codes, which are a special class of Fountain codes, are widely used in Wireless Sensor Networks (WSNs) to increase the robustness of data storage and efficiency of data retrieval. In this paper, we propose a novel LT codes based Distributed Coding (LTDC) scheme for efficient distributed storage in WSNs. In the proposed LTDC scheme, we use random walks to disseminate sensed data from a source sensor node to a random subset of sensor nodes by multicast. As long as a data packet stops at an ending sensor node of a random walk, the ending sensor node encodes this data packet in a main packet (an encoded data packet) with a certain probability. By adjusting the main packet with the un-encoded data packets, the number of data packets encoded in the main packet follows the distribution of LT codes. The data collector is able to decode the original data by querying any subset of sensor nodes. The theoretical analysis and simulation results have demonstrated that the proposed LTDC scheme has lower data dissemination cost and lower storage overhead, while maintains the same level of fault tolerance as the original LT codes.

Since uplink (UL) and downlink (DL) traffic loads are time-variant in femtocells, it is essential to adopt dynamic time-division duplexing (TDD) to effectively adjust the uplink and downlink transmission resources. However, the cross-link interference between dynamic TDD femtocells decreases the throughput gain of dynamic TDD. In this paper, we propose an evolutionary game-based distributed approach to choose the UL-DL configuration in order to minimize interference and maximize the system throughput in a large-scale femtocell network. A multiple populations evolutionary game is formulated to model femtocells with different traffic loads. We prove that the evolutionarily stable strategy (ESS) of the considered multiple populations evolutionary game is the optimal configuration which maximizes the system throughput. Simulation results confirm the effectiveness of the proposed evolutionary game-based approach for system throughput optimization in femtocells employing dynamic TDD.

Due to the proliferation of applications for the Internet of Things, an increasing number of machine to machine (M2M) devices are being deployed. In particular, one of the M2M applications, video surveillance, has been widely discussed. Long Term Evolution (LTE), which can provide a high rate of data transmission and wide range of coverage, is a promising standard to serve as an M2M video surveillance system. In this paper, we study a performance maximization problem in an LTE video surveillance system. Given a set of objects and a set of cameras, each camera has its own performance grade and its own coverage. The goal is to maximize the performance of the system by allocating limited resources to cameras while all objects should be monitored by the selected cameras. We propose a heuristic method to select the cameras and allocate resources to them to solve the problem. Moreover, to reduce the load of the LTE system, a dynamic adjustment method is also proposed.

Cognitive radio ad hoc network (CRAHN) is considered as a key technology to enhance the spectrum efficiency for diverse applications. However, due to the opportunistic links, the intrinsic randomness of the CRAHN makes the traditional precise control of the end-to-end transmission unscalable and generally infeasible. The recently-proposed virtual multiple-input multiple-output (MIMO) framework exploits the multipath routing to create the diversity at the network layer. With only local information and no feedback control channel, the path-time code (PTC) of the virtual MIMO system is able to efficiently provide the error resilient end-to-end transmission. In particular, while the transmission latency should be minimized, more attempts for accessing the opportunistic links can be made if a larger latency is allowed, which improves the error rate performance of the end-to-end transmission. By theoretically analyzing the error rate performance and erasure statistics, we propose a design guideline to determine the waiting period as the limit of the transmission latency. This designed waiting period not only preserves the diversity gained by the PTC but also provides a low transmission latency, resulting in a good balance of the reliability-latency trade-off of the end-to-end PTC transmission in CRAHNs.

A heterogeneous network (HetNet), which consists of macro cells and small cells, is an effective tool to improve the system spectral efficiency by exploiting the benefit of spatial reuse. However, the benefit of HetNet is limited by the asymmetry of transmit power between macro base stations (BSs) and pico BSs. Traditional solutions lead to a tradeoff between received signal strength (RSS) and load balancing. To tackle this problem, we propose a novel mechanism with joint macro BS transmit power control and load-aware user association. As such, we can realize traffic offloading from the macro cell to pico cells in a two-tier HetNet and mitigate inter-cell interference (ICI) in the network. We formulate this problem as a nonlinear integer programming problem, and prove that it is NP-hard. We then propose a polynomial-time heuristic. The simulation results show that our algorithm is indeed an efficient mechanism with better network performance in terms of average throughput and fairness.

This paper investigates the issue of interference mitigation in wireless body area networks (BANs). Although several approaches have been proposed in BAN standard IEEE 802.15.6, they increase transmission latency or energy cost, and do not mitigate interference effectively. In order to avoid both intra- and inter-BAN interference, we present a MAC protocol with two-layer interference mitigation (2L-MAC) for BANs. Considering the QoS requirements of BANs, the proposed protocol not only avoids packet collisions but also reduces transmission delay and energy consumption in sensors. Moreover, channel switching is triggered whenever a BAN needs to acquire more bandwidth. Simulation results show that our protocol outperforms other protocols in terms of delivery rate, latency and energy saving.

The privacy issue of online social networks (OSNs) has been getting attention from the public, especially when data privacy has caused the disagreement between users and OSN providers. While the providers utilize users' data as a commercial usage to make profit; on the other hand, users feel their privacy has been violated by such behavior. In this paper, we propose a privacy preserving protocol for users' data sharing in OSNs, where the OSN provider cannot retrieve the users' social content while the users can efficiently add or remove a social contact and flexibly perform the data access control. Moreover, we prove that the users would allow the OSN provider to perform keyword search over the encrypted content for advertising profit, so that the OSN provider can commercialize its products without the knowledge of content.

Long Term Evolution-Advanced (LTE-A) networks exploit the Carrier Aggregation (CA) technique to achieve a higher data rate by allowing user equipments (UEs) to simultaneously aggregate multiple component carriers (CCs). Moreover, MIMO technologies have become increasingly mature and been adopted as a default choice of the 4G standards. However, most of existing studies on resource allocation with carrier aggregation do not consider the MIMO capability of UEs. In this paper, we address the spectrum resource allocation problem with consideration of UEs' MIMO capability as well as modulation and coding schemes (MCSs) selection in carrier aggregation based LTE-A systems. We formulate the problem under both backlogged and finite queue traffic models as an optimization model, and prove its NP-hardness. As a result, a 1/2-approximation algorithm is proposed to find a suboptimal solution of resource allocation. Simulation results show that the proposed algorithm outperforms the existing schemes, and performs fairly close to the optimal solution under the small-scale scenarios.

In this paper, we analyze the packet session channel holding time for packet-switched cellular networks. Channel holding time depends on mobility which is characterized by cell residence time in this paper. We apply Hyper-Erlang distribution model to investigate the packet session channel holding time in which a session will experience active and idle periods. In terms of new session, handoff session in busy mode, handoff session with new arrival packets in idle mode and handoff session without arrival packet in idle mode, we demonstrate that the effective channel holding time is exponentially distributed if and only if the cell residence time is exponentially distributed. The analytical results provide a new approach to evaluate traffic performance and system design in packet-switched cellular networks.

IoT browser is a useful tool for the Internet of Things (IoT), which provides a novel way for people to interact with daily life objects through the Internet. Comparing with traditional web browsing environment, IoT browsing environment has some distinctive features such as the way of interacting with the physical objects, the importance of spatial-temporal information of objects, and the necessity of resource reuse. In this demonstration, we present a prototype of a proposed IoT browsing system architecture with a semantic-based learning-capable middleware for IoT browser and demonstrate the applicability of the system in a browsing scenario. The learning scheme is able to suggest users the next possible events when the users design their own service flows through web interface. The prototype shows that with the help of the IoT browsing system, heterogeneous devices can cooperate with each other to provide IoT services.

A heterogeneous network (HetNet) with macro base stations (BSs) together with low power small cells, such as pico BSs and femto BSs, is a promising solution to enhance network capacity. In HetNet, the transmission range of pico BSs are limited due to the large transmission power difference between macro and pico BSs, and thus pico BSs are typically underutilized. Cell Range Expansion (CRE) is a way to increase the opportunity of the user equipment (UE) associations to pico BSs so that more traffic from the macro cell can be offloaded to the pico cells. However, the expansion region of pico UEs with unbalance downlink and uplink signal qualities suffer from bad downlink quality, and the macro UEs near the expansion region may also experience low uplink rates. Therefore, we propose a new scheme with rate-based CRE offsets in HetNet so that UEs can decide to their associations based on their traffic demands. We formulate this problem as a mixed integer programming problem and prove that it is NP-hard. We then propose a polynomial time heuristic algorithm to solve this problem. The simulation results show that our scheme indeed achieves good traffic offloading gain for HetNet.

In long term evolution-advanced (LTE-A) networks, the carrier aggregation technique is incorporated for user equipments (UEs) to simultaneously aggregate multiple component carriers (CCs) for achieving higher transmission rate. Many research works for LTE-A systems with carrier aggregation configuration have concentrated on the radio resource management problem for downlink transmission, including mainly CC assignment and packet scheduling. Most previous studies have not considered that the assigned CCs in each UE can be changed. Furthermore, they also have not considered the modulation and coding scheme constraint, as specified in LTE-A standards. Therefore, their proposed schemes may limit the radio resource usage and are not compatible with LTE-A systems. In this paper, we assume that the scheduler can reassign CCs to each UE at each transmission time interval and formulate the downlink radio resource scheduling problem under the modulation and coding scheme constraint, which is proved to be NP-hard. Then, a novel greedy-based scheme is proposed to maximize the system throughput while maintaining proportional fairness of radio resource allocation among all UEs. We show that this scheme can guarantee at least half of the performance of the optimal solution. Simulation results show that our proposed scheme outperforms the schemes in previous studies.

This work examines offline and online power control policies for efficient usage of renewable energy in the downlink of a multi-antenna wireless system. Two multiuser beamforming schemes are considered, namely, channel inversion (CI) and maximal ratio transmit (MRT) beamforming schemes. Power control policies are derived for both schemes, respectively, with the goal of maximizing the sum throughput by a deadline subject to energy causality and battery storage constraints. With CI beamforming, the power control problem can be formulated as a convex optimization problem, whose solution can be obtained using the directional water-filling algorithm. With MRT beam-forming, the power control problem becomes non-convex, due to interference between the signals intended for different users, and, thus, is difficult to solve exactly. However, an efficient solution can be obtained by performing successive approximation into a sequence of geometric programming problems, i.e., by employing the condensation method. Offline power control policies are first derived assuming non-causal knowledge of the energy arrival and channel coefficients over time. Online power control policies are then proposed based on observations gained from the offline policy. The performance of the proposed schemes are demonstrated through numerical simulations.

When accidents or disasters happen, emergency response time is always crucial. Most procedures in the existing emergency vehicle dispatching systems rely heavily on manual assignments. In this paper, we propose a novel emergency vehicle dispatching system to reduce emergency response time, which includes automatic emergency resource assignment and driving path planning to reduce unnecessary time delay caused by human misjudgment or the delay caused by traffic jam. As the traffic condition varies from time to time, the traffic information employed in the proposed method needs to trace back to several weeks prior to the dispatching time. Furthermore, we also propose a lane reservation scheme for emergency vehicles to minimize the crash risks. Before an emergency vehicle arrives at each road segment, Road Side Units start to disseminate the warning message at suitable time, so that other drivers could have enough time to take proper actions such as speed acceleration or switching lanes. Simulation results show that the proposed approach can largely reduce the traveling time of emergency vehicles comparing to the shortest path approach with sirens and lights to alert other drivers. With the traveling time as well as emergency resource assignment time being reduced, the emergency rescue teams would gain edges in rescuing lives and property.

Wireless sensor networks have been widely used in many applications. One of them is indoor guiding service for emergency evacuation whose goal is to assist moving objects in escaping a hazardous region safely and quickly when an emergency occurs. In this paper, we propose a distributed and adaptive guiding protocol that takes several factors such as hazardous regions, distance to exits, width of exits, and congestion degree of each location into consideration. This protocol guides moving objects with load balancing among multiple navigation paths to multiple exits and avoids congestion to reduce the evacuation time. Simulation results show that the proposed protocol can guide moving objects (e.g., people) to exits in shorter time and have higher survival rate in comparison to those without balancing the traffic load on navigation paths and exits.

Vehicular Ad-hoc Networks (VANETs) has been regarded as an emerging and promising network for transportation because it can provide safety and useful traffic information for passengers. VANET employs IEEE 802.11p standard as transmission protocol that defines media access control (MAC) and physical layers, where provide one control channel and six service channels. IEEE 802.11p MAC protocol is a contention-based protocol that has low channel utilization under heavy traffic load. In this paper, we propose a Distributed Channel Assignment Scheme (DCAS) to increase the successful rate of channel reservation and avoid hidden terminal problem to increase the channel utilization. Besides, we also propose an emergency state transition mechanism when VANETs need to transmit emergency messages. Through state transition, vehicles in normal state using non-safety applications will enter emergency state to rapidly forward emergency message to reduce transmission delay. Simulation results show that the proposed scheme can improve 27% channel utilization in average comparing with random channel selection scheme.

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.

Guiding navigation is an important application in wireless sensor networks to make moving objects leave dangerous areas safely and quickly. However, guiding policy without considering congestion problem will postpone the escape time. In this paper, we propose a distributed flow-based guiding protocol for indoor environments to evacuate mobile objects from dangerous area to exit. Our goal is to construct less congested paths to minimize the escape time and the congestion time. Each sensor in the network holds an artificial potential value determined by the moving speed of object on a path monitored by it, the distances to exits, and the capacity of exits that have the maximum potential values, and objects are directed to paths with higher potential values. Nevertheless, our approach also solves the local maximum problem that objects are trapped at a non-exit location holding a local maximum potential value. In addition, we adopt a traffic flow model for transforming object density of a road into object's velocity to reduce the computational cost and the communication overhead. Simulation results show our proposed protocol can efficiently decrease the escape time and congestion time.

One important goal of surveillance systems is to collect information about the behavior and position of interested targets in the sensing environment. Traditional video surveillance systems usually cannot provide complete information of interested targets since they are limited by single and fixed monitoring directions. Recently, surveillance systems combining wireless sensor networks with video cameras have become more and more popular. In this demonstration, we show a multi-view surveillance system consisting of several rotatable video cameras and objects. By implementing the proposed visual sensor selection algorithm, our system can provide more meaningful information from multiple rotatable cameras.

Because of shortage of raw materials, the energy-saving issues become popular in Vehicular Ad-hoc Networks (VANETs). A VANET is formed by traveling vehicles with communicating capability and thus it brings various applications. Navigation system is one of important applications in VANETs. The traditional navigation system usually plans a shortest path for users according to geographic maps but the planned path may become a slower one due to the traffic congestion. A congestion path not only delays the traveling time but wastes fuel. So the real-time traffic information should be considered while constructing a navigation path. In this paper, we propose a navigation system to find a fuel-saving navigation path by considering real-time traffic information. In order to estimate the traffic load on the future path, we maintain a table of historical traffic information by Intelligent Transport Systems (ITS). Furthermore, our system can dynamically change the navigation path by updating traffic information. In the simulation results, our approach can save more than 20% fuel consumption when vehicles travel in a traffic congestion environment.

Traffic congestion is a serious problem in urban areas of many countries due to the increasing amount of vehicles on surface streets and accompanies fuel-wasting and air-pollution. This problem can be alleviated by adopting a ride-sharing service. The main idea of ride-sharing service is to collect travelers whose travel destinations are nearby into one vehicle. In doing so, we can reduce the amount of vehicles on surface streets and meantime save fuel. In this paper, we focus on the taxi-sharing service and propose a dynamic taxi-sharing system based on Intelligent Transportation Systems (ITS) technology. In the proposed system, we can immediately serve each irregular ride-sharing request and find a fuel-saving taxi for it. The simulation results show that our solution can exactly select a fuel-saving taxi for each ride-sharing request and outperform in responding time, the number of compared taxis, and fuel-saving while comparing with existing solutions.

Wireless relay network is a low-cost solution for extending the service coverage and increasing the throughput of the conventional single-hop wireless network. By deploying a relay network, a base station (BS) can provide services to subscriber stations (SSs) through relay links. The functionality of a relay station (RS) is simpler than a BS, and RSs only forward packets between SSs, RSs and the BS without too much packet processing. However, current solutions require a RS to store and process the packet before it can determine the destination, and thus introduce extra processing and buffering overheads on the RS. This study proposes a simple and efficient forwarding scheme which multiplexes bursts to the SSs attached to the same access RS. By applying the proposed end-to-end burst switching mechanism, the RS merely checks the frame header and can decide the final destination without packet processing. The experiment results demonstrate the superior performance of the proposed scheme than other approaches.

This paper proposes a new application framework for group tour guiding services based on RFIDs and wireless sensor networks. We consider a sensing field mixed with multiple independent tourist groups, each with a leader and several members. Members of a group will follow the moving path of their leader, but may occasionally roam around randomly on their own interests. Sensor nodes have to track leaders' locations and maintain guiding paths from members to leaders. A member may inquire where his/her leader is, and a leader may "recall" his/her members. We propose a feasible solution to such an application by using existing technologies and off-the-shelf components. A group guiding protocol is presented. The design enables reliable group guiding at low cost and low traffic load. Our prototyping system is reported and system performance is discussed.

One of the major applications of wireless sensor networks is guiding navigation service with its goal to assist moving objects in leaving a hazardous region safely and quickly. In this paper, we propose a distributed guiding navigation protocol that can guide moving objects to multiple exits with load balancing among multiple navigation paths to the exits. With the assistances of sensor nodes, moving objects are guided to different navigation paths so that they can move to exits as soon as possible without causing congestion. In some traditional navigation algorithms, a sensor may select a wrong guiding direction when an information- updating packet has not flooded through the whole network. Hence, the guiding direction of the sensor may oscillate in a short time and guided objects will confuse with this phenomenon, called direction oscillation problem. This problem will be eliminated in our proposed protocol. Simulation results indicate that our protocol can guide moving objects to exits in shorter time and solve the direction oscillation problem effectively.

One of the major applications of wireless sensor networks is guiding navigation service whose goal is to find a way to guide moving objects across a hazardous region covered by sensors. Sensor networks maintain safe paths by which the moving objects can be guided safely to exits. In this paper, we propose a distributed guiding navigation protocol for constructing area-to-area optimal guiding paths that do not traverse through the hazardous areas and to guide the moving objects to escape from this area safely and quickly. Our protocol also allows multiple exits and multiple emergency events in the sensor networks. Moreover, we propose a load-dispersion algorithm including an additional AP layer for moving objects registration and path assignment in multi-exits scenario. Hence, the moving objects can be properly dispersed to multiple paths leading to multiple exits to avoid congestion in the same exit. Simulation results show that our protocol can guide moving objects along shorter paths to reach nearest exits and operate in different scenarios or environments.

One important goal of surveillance systems is to collect information about the behavior and position of interested targets in the sensing environment. These systems can be applied to many applications, such as fire emergency, surveillance system, and smart home. Recently, surveillance systems combining wireless sensor networks with video cameras have become more and more popular. In traditional video surveillance systems, the system performance and cost is proportional to the number of deployed video camera. In this paper, we propose a real time video surveillance system consisting of many low cost sensors and a few wireless video cameras. The system allows a group of cooperating sensor devices to detect and track mobile objects and to report their positions to the sink node in the wireless sensor network. Then, the sink node uses the IP cameras deployed in the sensing area to record these events and display the present situations. We also propose a camera control scheme to initialize the coverage distribution of cameras and support the inter-task handoff operations between cameras. We have implemented the proposed system with 16 sensor nodes and two IP cameras, and evaluated the system performance. The result shows that our surveillance system is adaptable to variant environments and provides real time information of the monitored environment.

Because wireless channel condition is time-varying, the allocated bandwidth is usually not fixed. Therefore, it is a challenge to guarantee QoS, especially for bandwidth- consuming and delay-sensitive multimedia applications. In this paper, we propose a cross-layer mechanism to improve the quality of H.264 video when encountering short-term bandwidth fluctuations over IEEE 802.11e wireless networks. The proposed cross-layer mechanism consists of slice classification at application layer, dynamic packet selective transmission (DPST) at MAC layer, and channel condition prediction at physical layer. Performance of the proposed mechanism is evaluated through extensive simulations. Results show that the proposed cross-layer mechanism provides better video quality and lower packet delay.

The Universal Mobile Telecommunications System (UMTS) all-IP network supports IP multimedia services through the IP multimedia subsystem (IMS). This paper proposes a mobile quality-of-service (QoS) framework for heterogeneous IMS interworking. To reduce the handoff disruption time, this framework supports the IMS mobility based on the concept of session initiation protocol (SIP) multicast. In our approach, the mobility of a user equipment (UE) is modeled as a transition in the multicast group membership. With the concept of dynamic shifting of the multicast group's members, the flow of actual data packets can be switched to the new route as quickly as possible. To overcome mobility impact on service guarantees, UEs need to make QoS resource reservations in advance at neighboring IMS networks, where they may visit during the lifetime of the ongoing sessions. These locations become the leaves of the multicast tree in our approach. To obtain more efficient use of the scarce wireless bandwidth, our approach allows UEs to temporarily exploit the inactive bandwidths reserved by other UEs in the current IMS/access network. Analytic and simulation models are developed to investigate our resource reservation scheme. The results indicate that our scheme yields comparable performance to that of the previously proposed channel assignment schemes.

The use of multiple channels in wireless networks could provide performance advantages in reducing collisions and enabling more concurrent transmissions. So et al. proposed a multi-channel MAC protocol, which uses a single transceiver and divides the beacon interval into two parts: channel negotiation and data transmission. However, the fixed length of channel negotiation interval limits the channel utilization. We propose a new single transceiver MAC protocol, named traffic aware multichannel medium access control (TAMMAC), that can exploit multiple channels with smart window increase and decrease rules to adjust the contention window size dynamically and properly. The simulation results show that the proposed protocol achieves higher aggregate network throughput than other schemes under various traffic loads.

In early 2003, the Singapore Economic Development Board identified Embedded Systems as a major ‘new growth area’ for the Singapore economy, building upon the existing infrastructure of technological companies, and proven ability for companies both local and overseas, to conduct advanced research and development, as well as specialist production, in Singapore. In response to this, Nanyang Technological University School of Computer Engineering proposed, and deployed, a part-time graduate masters’ programme in embedded systems. This paper discusses the need for such an embedded education in Singapore, the syllabus and course coverage which has been developed, and the response of students and industry to the initiative. Pitfalls and problems are identified at each stage.

In multihop MANETs, nodes have to cooperate to forward each other's packets through the networks. Every node, including source and intermediate nodes, has a fair opportunity to transmit a packet Thus, the hot spot may suffer traffic congestion. The packet loss rate and the transmission delay are increased, but the throughput is decreased Due to the contention for the shared channel, the throughput of each single node is limited not only by the channel capacity, but also by the transmissions in its neighborhood (intraflow/interflow contention problem). Furthermore, the network throughput still restrict by the channel capacity. Some other related works using multiple channels simultaneously to transmit packets without interfering each other increases the throughput But if the traffic load is heavy, these schemes may induce more serious packet loss on the contrary because they do not consider the congestion problem especially in multihop MANETs. In this paper, we propose a new multichannel MAC protocol using multichannel transmission, and develop a hop- by-hop congestion control scheme, which is named "Efficient Flow Control with Multichannels" (EFCM). The EFCM scheme modifies the IEEE 802.11 RTS/CTS frame format to reserve bandwidth in different channels. It also solves the hidden terminal problem in the multichannel environment The intermediate nodes have a higher priority than the source (or leaf) nodes to contend for the right of transmission to solve the intraflow contention. In order to solve the interflow contention, congestion control is taken in every node to construct a flow table, which restricts the number of packets of every flow passing by congested nodes. According to the simulation results, the whole network throughputs of EFCM are improved significantly.

Improving search performance is an important issue in peer-to-peer (P2P) network systems. Although Distributed Hash Tables (DHTs) route queries more efficiently than flooding does, it’s complicated for DHTs to support keyword-based searches. Emerging large-scale P2P systems employ clustering to reduce message overheads and provide system scalability. In this paper, we propose an architecture based on interest groups to improve search performance in P2P networks. Query messages are first sent to interested peers that have high probability to hit the queries. Simulation results show that the proposed architecture outperforms related works in terms of message overheads, search latency, and query hit ratio.

Employing multiple channels is an effective way to improve the performance of wireless networks [2-10]. Some previous works on multiple channels [2-4] assume at least two transceivers and result in a higher cost on hardware requirements. The protocol in [5] uses a single transceiver and divides the beacon interval into two parts: channel negotiation and data transmission. However, the fixed length of channel negotiation interval limits the channel utilization. This paper proposed a new single transceiver MAC protocol that can exploit multiple channels effectively and dynamically adjust the length of negotiation interval to better utilize the wireless channel resources. The simulation results show that the proposed protocol achieves higher aggregate network throughput than the fixed schemes on various traffic loads.

In this article, we propose several decentralized protocols that schedule sensors' active and sleeping periods to prolong the network lifetime while maintain the sensing field sufficiently covered. The proposed protocols are based on a model similar to that of Yan et al. [2003], but improve its results in several senses. First, our approach can significantly reduce the computational complexity incurred, and at the same time achieve better accuracy in determining the coverage of the sensing area. Second, we extend the result such that it can support multilayer coverage of the sensing field. Third, we further enhance it [Yan et al. 2003] by proposing several optimization mechanisms to balance or reduce sensors' energy expenditure.

SMPCP is a multicast watermark scheme to protect valued contents from illegal distribution. However, it requires an overhead of O(N) on cryptographic encryptions and message size, here N is the size of group members. This paper proposes a logical key tree based secure multicast protocol, LKT-SMPCP, to improve the overhead in the SMPCP. Experimental results show that LKT-SMPCP reduces the encryption overhead by 30% as compared with the original SMPCP.

The coexistence of heterogeneous wireless networks providing service anywhere at anytime is an inevitable trend in the development of next-generation wireless data networks. Vertical handoff is the switching of the mobile terminal (MT) among different types of wireless networks. How and when to carry out vertical handoff directly affects the performance and quality of network services. In this paper, we propose a novel vertical handoff scheme in which the MT can request and initiate the handoff actively, contrary to other schemes where the MTs participate passively during the handoff process. Our active application oriented scheme provides an efficient interface management for multi-interface MTs to reduce the power consumption caused by unnecessary interface activation. By treating the application running in the MT as the main vertical handoff decision factor, the proposed scheme is able to switch the MT at the right time to the most suitable network to minimize the waste of network resources. Finally, simulation results are presented to show the improved performance over passive schemes.

To guarantee the delay and jitter bounds for real-time traffic, the polling scheme is commonly used in the IEEE 802.11 medium access control (MAC) protocol. However, the polling overhead becomes significant when the continuous and periodic real-time traffic is served. We propose a scheduling mechanism by which wireless stations can issue their frame transmissions automatically without too much indication from the system. The system can initiate a scheduling access phase (SAP) on the channel at anytime during which the scheduled stations can do data transmissions. We specify the transmissions of wireless stations being scheduled in a way of ordered contentions within the SAP. The contending feature can bring the advantages of easy implementation and high channel utilization.

Mobility management and quality-of-service (QoS) provisioning are the important tasks on the future development of wireless networks. The high host mobility makes these tasks more challenging. In this paper, we propose an architecture which supports both mobility and QoS management in Internet protocol (IP)-based wireless networks. In mobility management, the fast handoff, which the packets are forwarded in advance to the neighboring locations where a mobile node (MN) may move to, is provided to reduce the service disruption. Also, the fast location lookup, which the routing information about a MN is replicated to some routers, is provided to avoid the triangular routing problem incurred by the protocol of mobile IP. In QoS provisioning, we enable the end-to-end QoS guarantee by using the resource reservation protocol (RSVP) signaling. In particular, the RSVP aggregation technique is used to avoid the scalability problem. Also, the technique of passive resource reservation is used to reduce the influence of host mobility on the resource reservation delay. We emphasize the integration of mobility and QoS management in the architecture design. A performance analysis is given to justify the benefits of our proposed architecture.

Packet classification is essential for routing, Quality of Service (QoS) provisioning, and policy-based firewall deployment. A packet classifier categorizes incoming packets into specific flows, aggregates, or service classes according to pre-defined rules. Previous works transform range-based fields into prefixes to simplify packet classification by deploying a single prefix-based matching scheme. However, range-to-prefix transformation enlarges rule databases thus resulting in huge memory consumption and inefficient searching performance. This paper suggests a two-stage packet classification algorithm to handle prefixes and ranges separately. A novel prefix-based matching scheme is also proposed. Experimental results indicate 95% reduction of storage space in comparison with the Hierarchical Trie (H-Tries), a typical prefix-based approach. Besides, the two-stage algorithm demonstrates efficient searching performance even when the rule database grows large.

To expand support for applications with QoS requirements in wireless local area networks (WLANs), the 802.11 E Task Group was formed to enhance the current IEEE 802.11 Medium Access Control (MAC) protocol. The multipolling mechanism was discussed in the task group, but some problems remain unsolved. In this paper, we show a design of the multipolling mechanism with the advantages of high channel utilization and low implementation overhead. In our proposed mechanism, wireless stations use a priority-based contention scheme to coordinate in themselves the transmission order on the channel. Moreover, we propose a polling schedule mechanism for our proposed multipoll to serve real-time traffic with constant and variable bit rates. The bounded delay requirement of the real-time traffic can be satisfied in our scheduling model. We establish an admission test to estimate the system capacity and to determine whether a new connection can be accepted. We study the performance of our proposed mechanism analytically, as well as through simulated experiments. The results show that the proposed mechanism is more efficient than the one discussed in the IEEE 802.11 E task group.

This paper presents a novel wireless scheduling mechanism, called Adaptive Service Curve (ASC). The proposed mechanism increases the flexibility with which network operators can adjust the allocation of resources. A good scheduler should exhibit three kinds of flexibility. First, ASC should be able to differentiate the error resilience requirements due to the impact of location-dependent channel errors in wireless networks. Specifically, ASC can employ link adaptation, enabling a choice to be made between maximizing system throughput and making more link effort on error-prone channels. Second, the above flexibility is not system-wide. Rather users can subscribe to different error resilience policies. ASC utilizes the service curve model that can best meet QoS requirements to provide the third kind of flexibility, and prevents an unacceptable over-allocation of radio resources. Accordingly, a framework is proposed to make the existing service curve model operate effectively in wireless environments. The ASC scheduler combines in a single-framework the three aspects of scheduling, namely, link adaptation, flexibility and a mature traffic characterization model. This design represents a complete solution for wireless resource management.

The medium access control (MAC) protocol of the IEEE 802.11 standard is based on carrier sense multiple access with collision avoidance (CSMA/CA). The basic retransmission mechanism, binary exponential backoff, may cause large packet delay and jitter values that are not suitable for real-time traffic. In this paper, we first investigate some MAC enhancement mechanisms discussed in the IEEE 802.11 task group E, which was formed for enhancing the current 802.11 MAC protocol to support for applications with quality of service (QoS) requirements. Then, we propose a jamming-based retransmission mechanism that is compatible with the 802.11 standard and could reduce the packet delay of real-time traffic. Besides, this mechanism performs stably when the traffic load is heavy. The optimal setting of our proposed mechanism is discussed analytically. We perform simulated experiments by comparing our proposed retransmission mechanism with the other two mechanisms discussed in the 802.11 task group E. We show that the jamming-based retransmission mechanism can reduce the packet delay and the packet dropping rate.

We aim to provide a hard QoS guaranteed service with end-to-end behavior across domains in Diff-Serv. We add the bandwidth reservation process for each EF session in Diff-Serv with strict QoS provision. For this purpose, we utilize three mechanisms for the new framework: (1) local centralized resource management, (2) centralized route discovery, and (3) a sender-initiated signaling protocol. The performance of the proposed framework is evaluated against the current Diff-Serv framework and is shown to have advantages in terms of the congestion probability and average delay for both short-term and long-term EF traffic.

To support the real-time transport protocol (RTP) over wireless networks is essential for transporting real-time data streams. However, the RTP introduces significant header overheads, which cannot be adequately employed in wireless networks. An enhanced compressed RTP (ECRTP) with mobility support for wireless networks is presented, which is based on the, compressed RTP (CRTP). The ECRTP uses the local-link retransmission mechanism to recover transmission errors over wireless links. The simulation results show that ECRTP consumes insignificant network bandwidth and maximizes successfully received packets compared with RTP and CRTP in an error-prone and bandwidth limited wireless network. Consequently, the playback quality of real-time data streams is improved for wireless networks.

State-of-the-art cellular networks such as General Packet Radio Service systems (GPRS) with enhanced data rates for global evolution (EDGE) air interfaces can support a wide variety of applications, e.g., Web browsing and video conferencing. The desired quality of communication channels, however, for such wireless networks depends on the interference contributed by location errors and elapsed signal strength. To accommodate different quality-of-service (QoS) classes for such widely received applications, an efficient scheduling for air interfaces must essentially be supported. We propose a dynamic scheduling algorithm by together taking the interference and varying QoS requirements into consideration for GPRS with EDGE air interfaces. Conceptually, the proposed scheme assigns priority in order to the conversational, streaming, interactive and background traffic classes defined by ETSI. Each channel is equipped with an A-buffer to gather the acknowledge messages of the successfully transmitted packets to measure the utilization of the associated channel. A global monitoring device tracks each mobile station's state. Based on the measured channel utilization and the states of mobile stations, the proposed scheduling dynamically assigns channels to the ongoing traffic. From the event-driven simulations, the scheme can significantly outperform the scheme without any support of dynamic channel assignment, especially for the interactive and background traffic classes.

The third-generation wideband CDMA (W-CDMA) systems support the relative higher and variable bit rate transmissions for applications with various quality-of-service (QoS) requirements. Code assignment and reassignment schemes in W-CDMA are essential, with the aim of boosting utilization of codes. A dynamic code assignment scheme (DCA) is proposed for traffic with various QoS classes introduced by Universal Mobile Telecommunication System (UMTS). From the simulation results, the proposed DCA can reduce the new call blocking probability and thus improve the system utilization for W-CDMA.

The Internet and wireless networks are two of the most important technical developments that have had a direct effect on the lives of people over the past few years. The next step is to combine these two technologies to provide wide-area wireless Internet access. Currently, TCP/IP (Transport Control Protocol/Internet Protocol) is the most important protocol that integrates a wide range of different physical networks into the global Internet. The environment of wireless networks violates many assumptions made by traditional TCP/IP. Compared with fixed and wired networks, wireless networks have a high bit-error rate (BER) and offer less available bandwidth. Furthermore, the host mobility also results in packet losses or delays during handoff procedures. Hence, the performance of TCP/IP over such wireless networks without any modification suffers significant degradation of throughput and high interactive delay. In this paper, we propose some schemes to improve the performance of TCP/IP over wireless networks according to their characteristics. We analyze the performance of TCP/IP under different network conditions by using ns-2 (Network Simulator version 2) to facilitate comparisons with previous studies. The simulation results show that our proposed mechanisms achieve better performance than other protocols.

The resource reservation mechanism is essential for QoS provisioning in integrated services networks. The resource reservation protocol (RSVP) is a receiver oriented resource reservation protocol, and an Internet standard approved by the Internet Engineering Task Force (IETF). However, the RSVP designed for the fixed network has been facing a great challenge owing to the participation of wireless networks. In this paper, we describe a new signaling protocol for mobile hosts to reserve resources in the integrated services Internet. Under our approach, we extend the RSVP model based on IP multicast to support mobile hosts. The mobility of a host is modeled as a transition in multicast group membership. Provision of QoS in wireless networks is more complex than in wired networks due to user mobility. To overcome the mobility impact on service guarantees, mobile hosts need to make resource reservation in advance at the locations it may visit during the lifetime of the connections. These locations become the leaves of the multicast tree in our design. To obtain more efficient use of scarce wireless bandwidth, we propose the extended reservation model. A mobile proxy in a cell is required to manage resource reservations and other mobility related tasks on behalf of mobile hosts. The mobility impacts on packet delay, bandwidth utilization and packet loss rate are investigated via simulations.

We propose an efficient multicast cell-scheduling algorithm, called multiple-slot cell-scheduling algorithm, for multicast ATM switching systems with input queues. Cells in an input-queueing system are usually served based on the first-in-first-out (FIFO) discipline, which may have a serious head-of-line (HOL) blocking problem. Our algorithm differs from previous algorithms in that we consider the output contention resolution for multiple time slots instead of the current time slot only. Like a window-based scheduling algorithm, our algorithm allows cells behind an HOL cell to be transmitted prior to the HOL cell in the same input port. Thus, HOL blocking can be alleviated. We have illustrated that the delay-throughput performance of our algorithm outperforms most of those algorithms that consider only the output contention resolution for the current time slot. We also present a simple and efficient architecture for realizing our algorithm, which can dramatically reduce the time complexity. We believe that the proposed architecture is very suitable for multicast asynchronous transfer mode (ATM) switching systems with input queues.

Although earliest-deadline-first (EDF) is recognized as the optimal scheduling discipline to support the bounded-delay service in ATM networks, it lacks of the support of a prioritizing scheme for cell loss control. We modify the simple FIFO to implement a near-EDF scheduling discipline with loss control. The proposed scheme can guarantee the stringent delay bound and minimize the cell loss rate. The adaptive queue lengths in the proposed buffer structure can be determined dynamically according to the traffic load and cell delay constraints to minimize the cell loss rates. With the different deterministic adaptive queue lengths, the proposed scheme is equivalent to the other previous schemes. Performance evaluation shows that the proposed scheme's accessible offered load is better than the other schemes.

We present an efficient cell multiplexing method, called longest delay beyond expectation (LDBE), to schedule real-time traffic in ATM networks. By arranging cell transmission orders, the LDBE scheme can minimize the cell delay variation (CDV), reduce the cell loss ratio (CLR) and avert the excess of cell transfer delay (CTD) bounds, particularly when different CDV tolerance (CDVT) values are applied at each node along the path of a connection. Simulation results demonstrate that the proposed LDBE performs better than some prominent multiplexing methods in terms of these quality of service (QoS) requirements. Furthermore, the LDBE proposed is extended to handle both real-time and non-real-time traffic.

To support multimedia traffic consisting of diverse traffic classes for mobile devices, a traffic management scheme should be developed to provide a seamless wireless ATM based communication system. We propose a novel traffic management scheme based on the Packet Reservation Multiple Access (PRMA) protocol to support QoS guarantee for downlink traffic. The proposed traffic management scheme involves cell scheduling, buffer management, traffic shaping, traffic control, and flow control. The simulation results reveal that the proposed scheme can guarantee QoS (cell delay and cell loss ratio) for both real time (CBR, VBR) and non real time (ABR) traffic in the wireless ATM networks, reduce the buffer size in the Base Station (BS), and enhance the utilization of wireless bandwidth.

Video traffic is expected to account for a significant share of the total traffic volume in future ATM networks. In order to guarantee quality of service, it is important to police and manage the video traffic streams. MPEG, including I-Frame, P-Frame, and B-Frame, is the well accepted standard for video compression. Among these three kinds of frames, I-Frame and P-Frame are critical for video decoding. In this paper, we propose an algorithm to increase the surviving probability of I-Frame and P-Frame, strengthen the functionality of traffic policing, and achieve fairness furthermore. Based on the punish concept, it also establishes a cooperative environment for multiple video streams to share the network bandwidth.

Sharing buffer space between switch ports greatly improves the performance of the switching systems. However sharing buffers in a fair manner is not an easy task. In this paper we propose a high-performance ATM switching system with fairly and completely shared buffers. The core of the proposed switching system is a novel buffer management mechanism with which buffer space in the switching system can be completely shared by all the switch ports in a fair manner. The proposed buffer management mechanism works based on a simple algorithm and can be easily implemented by hardware. The performance of the proposed switching system is evaluated by both analytical model and simulation. The results show that high buffer utilization and low packet lost ratio can be achieved under both uniform and nonuniform traffic loads.

In this paper, a self-routing permutation network based on a binary radix sorting network has been proposed. It has O(log/sup 2/ n) propagation delay and O(n log/sup 2/ n) hardware complexity with bit-parallel input. The hardware complexity can be reduced to O(n log n) with bit-serial input. The binary radix sorting network is recursively constructed by log n stages of bit sorting networks. The bit sorting network is then constructed by a proposed self-routing reverse banyan network. It has O(log n) propagation delay and O(n log n) hardware complexity. The proposed reverse banyan network has been fully verified by Verilog Hardware Description Language in logical level. The VLSI design of its switching elements is simple and regular.

We consider the scheduling problem in time-division multiplexed (TDM) switching systems. In previous works, the interdependence between traffic demands in two consecutive frames is neglected, and scheduling algorithms found up to now have time complexities O(N/sup 5/) or O(N/sup 4.5/), where N is the switch size. However, in many applications like voice or video communications, if a source transmits a packet to a destination in a frame, it is highly probable that it will also transmit a packet to the same destination in the next frame. So it is not necessary to schedule incoming packets for every frame if we can preserve all the switching patterns for the nearest scheduled frame and update the patterns appropriately according to the changes of traffic demands. The adaptive algorithm proposed in this paper assigns time slots to packets according to the changes of traffic demands. This algorithm has the worst case time complexity O(N/sup 2/L), where L is the TDM frame length. Comparing the time complexity of the adaptive algorithm with those of previous scheduling algorithms, the adaptive algorithm can perform better than previous scheduling algorithms when N is large and/or L is small. Since traffic demands in consecutive frames are expected to be interdependent in many applications, the proposed algorithm may offer as an efficient alternative for scheduling time slots in these applications.>

No abstract available.

The reconfigurable mesh, a parallel system with bus autonomy, can support various interconnection schemes during execution of an algorithm. It offers very efficient computation power in many application domains. In digital image processing and computer vision, convexity is a natural shape descriptor and a classifier for objects in the image space. We first present that the problem of identifying extreme points of convex hulls can be solved in O(1) time on the reconfigurable mesh proposed. Furthermore, we present constant time algorithms for a number of convexity-related problems on reconfigurable meshes. These problems include point inclusion, interior detection, area, and width of convex hulls.

We present a constant time sorting algorithm by adopting a 3D reconfigurable mesh with only O(n/sup 3/2/) processors. Our algorithm is developed on an n/sup 1/2//spl times/n/sup 1/2//spl times/n/sup 1/2/ 3-D reconfigurable mesh. Moreover, we further extend the result to k-dimensional reconfigurable meshes for k/spl ges/3. Consequently, an O(4/sup k+1/) time sorting algorithm is obtained by adopting an n/sup 1/(k-1)//spl times/n/sup 1/(k-1)//spl times/.../spl times/n/sup 1/(k-1)/k-D reconfigurable mesh of size O(n/sup 1+1/(k-1)/). Hence, constant time sorting using O(n/sup 1+/spl epsiv//) processors, where O>

The time slot assignment problem in time-division multiplexed switching systems which can support multicast transmissions is studied. It is shown that this problem is NP-complete, i.e., computationally intractable. Two effective heuristic algorithms are proposed, and computer simulations are also performed to evaluate the performance of both algorithms. The results of the simulations indicate that the solutions generated by these heuristic algorithms are very close to the optimal on the average. In addition, this problem is also examined under a more restrictive condition that the destination sets of any two multicast packets are either identical or disjoint, a situation often encountered in many practical applications. It is proved that this special problem is still NP-complete. Two fast heuristic algorithms are given, which can find solutions not greater than twice the optimal solution. Computer simulations for evaluating these two heuristic algorithms are also performed. Experimental results demonstrate that the solutions of the two algorithms are almost equal to the optimal.>

Two-dimensional entropic thresholding is one of the important thresholding techniques for image segmentation. Usually, the global threshold vector is selected from L2 (gray level, local average) pairs through a `maximum' optimization procedure with O(L4) computation complexity. This paper proposes a fast two-phase 2D entropic thresholding algorithm. In order to reduce the computation time, we estimate 9L2/3 candidate threshold vectors from a quantized image of the original in advance. The global threshold vector is then obtained by checking candidates only. The optimal computation complexity is O(L8/3) by quantizing the gray level in L2/3 levels. Experimental results show that the processing time of each image is reduced from more than two hours to about two minutes. The required memory space is also greatly reduced.

Future B-ISDN (broadband integrated services digital network) users will be able to send various kinds of information, such as voice, data, and image, over the same network and send information only when necessary. It has been recognized that variable-rate encoding techniques are more suitable than fixed-rate techniques for encoding images in a B-ISDN environment. A new variable-rate side-match finite-state vector quantization with a block classifier (CSMVQ) algorithm is described. In an ordinary fixed-rate SMVQ, the size of the state codebook is fixed. In the CSMVQ algorithm presented, the size of the state codebook is changed according to the characteristics of the current vector which can be predicted by a block classifier. In experiments, the improvement over SMVQ was up to 1.761 dB at a lower bit rate. Moreover, the improvement over VQ can be up to 3 dB at nearly the same bit rate.

A neural network that combines unsupervised and supervised learning for pattern recognition is proposed. The network is a hierarchical self-organization map, which is trained by unsupervised learning at first. When the network fails to recognize similar patterns, supervised learning is applied to teach the network to give different scaling factors for different features so as to discriminate similar patterns. Simulation results show that the model obtains good generalization capability as well as sharp discrimination between similar patterns.

The authors propose a hierarchical deformation model to describe the deformation of cursive Chinese characters for online character recognition. This approach consists of two levels of match processes. First, the attributed string editing algorithm determines the stroke correspondence between the input and the reference pattern. Next, the constrained parabola transformation is used to reduce the difference between the matched strokes appropriately. Experimental results show that the hierarchical deformation model provides a robust distance measure between patterns, and obtains a quite accurate approximation to the deformation of cursive Chinese characters with much lower computational cost.>

The authors propose a cell scheduling algorithm to increase the throughput of an asynchronous transfer mode (ATM) switching system with services of diverse priority classes. The maximum throughput is increased up to 0.949. The efficiency (output trunk utilization)/(input trunk utilization) is almost equal to 100%, and is almost independent of the switch size and the traffic load. The cell scheduling algorithm is shown to be able to provide high throughput not only for higher priority classes but also for lower priority classes. The mean cell waiting time of the highest priority class are transmitted as soon as possible. In the switching system implemented with the present cell scheduling algorithm, it is sufficient for a sorting network to establish input/output paths through it simultaneously without conflicts and it is not necessary to append a routing network to a sorting network.>

A coding algorithm must have the ability to adapt to changing image characteristics for image sequences. An adaptive finite-state vector quantization (FSVQ) in which the bit rate and the encoding time can be reduced is described. In order to improve the image quality and avoid producing a wrong state for an input vector, a threshold is used in FSVQ to decide whether to switch to a full searching VQ. The codebook is conditionally replenished according to a distortion threshold at a later time to reflect the local statistics of the current frame. After the codebook is replenished, one can quickly reconstruct the state codebooks of FSVQ using the state codebook selection algorithm. In the experiments, the improvement over the static SMVQ is up to 2.40 dB at nearly the same bit rate and the encoding time is only one-ninth the time required by the static SMVQ. Moreover, the improvement over the static VQ is up to 2.91 dB, and the encoding time is only three-fifths the time required by the static VQ for the image sequence 'Claire'.>

Vectorization techniques for solving the theorem-proving problem in propositional logic on vector computers is presented. To take advantage of vector processing, the rules used in the deduction process are first generalized by considering more than one literal at a time. The soundness of the generalized rules is proved. The vectorized representation of the problem and algorithms based on the generalized rules is proposed. Experiments conducted on vector computers show that the vectorized procedure is effective.>

The design of a parallel theorem prover for first-order logic is described. The parallel theorem algorithm is based on the divide-and-conquer strategy. The concept of restricted substitution is used to reduce the number of ground clauses generated during the operation of this theorem prover. In this manner, the ground clause set generated by the theorem prover will be much smaller than that generated directly by Herbrand universe.>

A new adaptive tree-structured vector quantization (adaptive TSVQ) with multipath searching is described. The structure of the codebook tree is reorganized at an update interval, without requiring any transmission of side information. The 1-path tree searching algorithm is the simple way to find the closest codeword in TSVQ. But the disadvantage of 1-path searching is that the selected codeworks are not, in general, closest to the input vectors. Hence, the authors propose the multipath searching algorithm to improve the image quality. In an experiment, the improvement over the fixed TSVQ at the same bit rate is up to 2.03 dB when the number of the leaves in the codebook tree is 256 and 4-path searching is applied.>

Consideration is given to the scheduling problem for avoiding output conflicts in time-division multiplex (TDM) switching systems. In many applications, if a source transmits a packet to a destination in a frame, it is highly probable that it will also transmit another packet to the same destination in the next frame. So it is not necessary to schedule incoming packets for every frame if all the switching patterns for the nearest scheduled frame can be preserved and the patterns updated appropriately according to changes in traffic demand. An adaptive algorithm of a lower time complexity which assigns time slots to packets according to the changes in traffic demands is given. This algorithm has the worst case time complexity O(N/sup 2/L), where L is the TDM frame length and N is the switch size. Simulation results show that the algorithm is efficient for interdependent traffic and for random traffic.>

The time slot assignment problem is studied in time-division multiplexing (TDM) switching systems which can support multicast transmissions. It is shown that this problem is NP-complete, i.e., computationally intractable. Two effective heuristic algorithms are proposed. To evaluate and compare the performance of these algorithms, a lower bound on the solution of this problem is derived and computer simulations are performed. The results of simulations show that the solutions generated by these heuristic algorithms are close to this lower bound on the average.>

Forward loop backward hop (FLBH) networks, characterized by a forward loop connecting all the adjacent nodes and a backward loop connecting nodes separated by a distance of h hops, have a higher connectivity and therefore a higher potential for fault-tolerance than single-loop networks. How to devise efficient fault-tolerant routing algorithms is an important issue on designing FLBH networks. This paper proposes two new fault-tolerant routing algorithms. One is for optimal FLBH networks with h/sup 2/=N, where N is the number of nodes. The other is for arbitrary FLBH networks (i.e., 1>

A pairwise switch-connection mechanism for interconnecting multiple token passing ring networks is proposed. The total number of internetwork packet store-and-forwards occurring at the bridges can be significantly reduced under the new switching method. A simple scheduling algorithm is developed to guarantee non-overlapped pairwise connection among the interconnected ring networks. Easy network access can be achieved through the use of different types of free tokens and local timers. Only simple table look-up operation is needed for the internetwork address translation. Therefore, the internetwork packets can be routed efficiently. Finally, simulation results are provided to show the fair network throughput under such switch-connection approach.>

The authors consider the output contention problem with a view towards increasing the throughput for asynchronous transfer mode (ATM) switching systems. A cell scheduling algorithm for increasing the throughput is proposed. The maximum throughput is increased up to 0.957. The efficiency (output trunk utilization/input trunk utilization) is almost equal to 100% and is independent of the switch size and traffic load. A switching system implemented with this cell scheduling algorithm is also proposed. The switching network usually consists of a sorting network followed by a routing network. Here, it is sufficient for a sorting network to establish input-output paths through it simultaneously without conflicts, and it is not necessary to append a routing network. In addition, a parallel mesh-connected architecture of a component of the switching system is proposed to speed up the cell scheduling of the system. Consequently, this approach can offer an effective alternative to ATM switching systems.>

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.>

A multilayer feedforward neural network is proposed to solve sorting problems. The network has O(n2) neurons and O(n2) links. The number of layers is fixed regardless of input size. Thus, the computation time of the network is independent of input size, and the sorting network has a time complexity of O(1)

The Davis-Putman procedure (DPP) is an efficient method for solving the theorem proving problem in propositional logic. The authors present an effective technique for vectorizing the DPP. To speed up the execution of DPP, the rules used by the procedure are first generalized by considering more than one literal at a time. Then vectorized algorithms based on the generalized rules are proposed. Experiments are conducted on vector computers. The results show that the vectorized version of the Davis-Putnam procedure is effective in solving a variety of instances of the theorem proving problem in propositional logic. The vectorized version of the DPP was effective in cutting down the search space and thus substantially improving the search efficiency.>

Some common guidelines that can be used to design parallel algorithms under the single-channel broadcast communication model are presented. Several graph problems are solved, including topological ordering, the connected component problem, breadth-first search, and depth-first search. If an ideal conflict resolution scheme is used, all of the algorithms require O(n) time by using n processors. Under such a situation, the algorithms are all optimal. If a realistic conflict resolution is used, the algorithms require O(n log n) time by using n/log n processors. For both cases, all of the algorithms achieve optimal speedups.>

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 problem of strongly connecting a multihop packet radio network by using a minimal total amount of transmission power is investigated. This problem is shown to be NP-complete. An approximation algorithm with the same computational complexity as that of finding a minimum spanning tree is given. It is also shown that the approximation algorithm can find a solution no greater than twice that of the optimal solution. Experimental results show that the approximation solution may be close to the optimal solution.>

The authors discuss secure broadcasting, effected by means of a secure lock, on broadcast channels, such as satellite, radio, etc. This lock is implemented by using the Chinese Remainder theorem (CRT). The secure lock offers the following advantages: only one copy of the ciphertext is sent; the deciphering operation is efficient; and the number of secret keys held by each user is minimized. Protocols for secure broadcasting using the secure lock, based on the public-key cryptosystem as well as the private-key cryptosystem, are presented.>

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.>

Single-stage Beta interconnection networks have been proposed for connecting processing elements in multiprocessing systems. An efficient data routing strategy has been designed. Faulty switching elements in the network can be automatically diagnosed. Its fault-tolerant capability is achieved by allowing data to recirculate the network several more passes with the presence of faults. Two parameters are taken into account to evaluate the network, i.e., communication delay d and degree of fault tolerance k. It has been shown elsewhere that k + 1 ≤ d. We have derived, a class of single-stage Beta networks which have been shown to possess the optimal fault tolerance property, i.e., k = d -1.

Automated dynamic validation through assertion checking has been proposed in recent years to ensure program correctness [3,7]. This method has shown to be useful for validating large scale programs. When used in parallel with debugging aids, it can be useful for early detecting and properly locating errors. In this paper, we provide a theoretical basis for assertion checking with regard to validation of program correctness. This gives some guidelines for inserting assertions within the program. An assertion language is provided for stating assertions. Salient features of this language are provided. A language preprocessor is designed to process source program inserted with assertions to generate source code acceptable to the existing compiler. Finally, future extentions to the assertion language and limitations of assertion checking to ensure program correctness are discussed.