In the literature, to date, the maximum first time-to-rendezvous (MFTTR) bound of the most state-of-the-art multi-channel rendezvous algorithm capable of generating the channel hopping (CH) sequence with maximum rendezvous diversity, P-MTP, is still 16 times greater thannanblog logn, wherenaandnbare the numbers of channels available to two users andnis the number of channels in the spectrum. In this paper, we attempt to tighten the MFTTR bound of these kinds of multichannel rendezvous algorithms. In many multichannel rendezvous algorithms, the CH sequence of multiple channels is obtained by concatenation of the CH sequences of two channels iteratively constructed using a two-channel rendezvous algorithm as a subroutine. Thus, we first propose a two-channel rendezvous algorithm, IDRDS-CMM, and then propose a multichannel rendezvous algorithm, C-MTP, which uses IDRDS-CMM as a subroutine. In terms of MFTTR bound, IDRDS-CMM is shown to achieve a significant reduction compared to E-MM, the most state-of-the-art two-channel rendezvous algorithm, and C-MTP can improve P-MTP approximately four times asnais close tonb.

Satellite-assisted quantum network (SQN) is emerging as a promising solution to overcome the distance limitations of ground-based fiber quantum network (QN). However, each satellite and ground station has a limited number of transmitters and receivers, respectively, and the Entanglement Distribution Rate (EDR) decreases with the distance between satellites and ground stations, highlighting the need for effective resource allocation to serve requests in the SQN. In this paper, we present a novel optimization problem, termed ESOP, which aims to maximize the total EDR in the network while simultaneously considering the resource capacities of both satellites and ground stations, as well as the fidelity requirements of individual requests. To solve ESOP, we propose a (2 + ϵ)-approximation algorithm, AESOP, which combines a greedy approach with a tailored local search. Simulation results show that AESOP achieves up to 64% improvement in total EDR compared to the existing method.

Quantum nodes exchange qubits to achieve largescale quantum computing applications in a quantum network (QN). However, due to environmental influences, entangled links used for data transmission would decohere over time. Besides, the scarcity of quantum memory in each quantum node necessitates frequent communication between nodes, leading to significant variations in the traffic matrix. Thus, providing real-time services in QNs becomes particularly important. To this end, this paper presents a new optimization problem and proposes a novel online algorithm, which combines the game-theoretic analysis results with the linear programming (LP) by the primal-dual technique. Finally, the simulation results demonstrate that the proposed algorithm outperforms the other baselines by up to 90 %.

With the enhanced security offered by quantum teleportation, quantum networks (QNs) are gradually gaining significant attention. However, previous research on QNs often exhausts all network resources to serve requests, hence overlooking the scarce resources in QN. This oversight easily leads to resource wastage and requests competing for limited resources. To address the above issues, this paper introduces a new optimization problem named EINS, which minimizes the maximum resource utilization and finds routing paths for each request through certain intermediate nodes. This design cleverly divides the routing path into segments to enhance routing path diversity. To solve the EINS, we design a novel algorithm named GOAL, which provides an$O(\log\vert V\vert)$bound for constraint deviation. It efficiently and equitably distributes requests, ensuring optimal network utilization. Finally, the simulation results manifest that GOAL can outperform the existing methods by up to 99%.

Quantum key distribution (QKD) is currently the only visible technology for secure symmetric key exchange between communicating parties. However, existing quantum photon sources (PSs) in QKD networks for generating keys between nodes are costly but offer limited achievable key rates. Moreover, achievable key rates across links diminish drastically with link distance, underscoring the importance of effectively identifying relay paths and strategically allocating PS resources. To optimize network costs, it is essential to jointly deploy PSs, allocate key rates across links, and determine relay paths based on anticipated traffic. To this end, we formulate a novel optimization problem, termed DAP, which simultaneously considers PS placement, key rate allocation, and relay path identification. Our proposed$O(\log\vert V\vert)$approximation algorithm, ADAP, leverages an advanced linear programming (LP) conversion with tailored rounding techniques. Simulation results manifest that ADAP achieves at least an 83 % reduction in the number of PSs.

To provide real-time map information, roadside units (RSUs) near vehicles cache 3D map tiles to reduce transmission delays and alleviate backhaul congestion. Unfortunately, traditional cache problems primarily focus on maximizing the cache hit rate (i.e., popularity) while often neglecting other criteria, thus suppressing caching efficiency. For instance, the priority of each map tile may vary for different vehicles based on their route plans and current positions. Additionally, caching a greater number of small-scale map tiles with broader coverage helps serve more vehicles’ requests and reduce cache misses. However, these tiles may only be sufficient for vehicles that can tolerate lower detail levels, as they provide less information than large-scale tiles. Furthermore, ensuring the freshness of cached map tiles is essential for maintaining driving safety. To address the interplay among popularity, priority, map scale, and information freshness in online map caching, this paper formulates an online optimization problem and proposes a novel online algorithm called ADAM, which integrates mixed-integer linear programming (MILP) with deep reinforcement learning. The ADAM predicts future total costs to support caching decisions by leveraging an ingeniously designed MILP that emulates the behavior of a neural network. Finally, simulation results manifest that the proposed ADAM outperforms existing methods by an average of 50%.

Quantum networks (QNs) gradually gain significant attention due to their higher security compared with classical networks. Conventional approaches in QN routing often aggregate multiple requests into a batch before determining their routing paths. However, this approach may overlook the limited lifetime of qubits, resulting in critical decoherence. In this paper, we present a new online entanglement routing architecture with an online optimization problem and propose a novel [1, O(log |V|)]-competitive algorithm supporting online requests with admission control, aiming to maximize the number of admitted requests. Finally, extensive simulation results show that our algorithm can outperform the existing approaches by up to 98%.

Telecom carriers have announced new content services by making a partnership with content providers and offered popular video streaming to customers. Via the integration with edge networks, telecom carriers can procure various contents from content providers and place them on edge servers proximate to end users to serve real-time requests with high bandwidth and ultra-low latency. Nevertheless, it is challenging to consider the content procurement, placement, and services jointly due to the user preference, user distribution, storage capacity of edge server, economic costs, etc. Telecom carriers would like to balance the procuring, placing, and transfer costs. To address this problem, the paper formulates an optimization problem and then proposes an approximation algorithm. Finally, the simulation results manifest that our algorithm outperforms other baselines.

In a Low-Earth Orbit (LEO) satellite network, each satellite covers an area for a limited time interval. Thus, once the serving satellite is about to lose coverage of the area, a handover needs to be performed to let another satellite take over serving the user equipment (UE) in the area. Although many LEO handover algorithms have been proposed in the literature to date, none of them can ensure the minimum handovers of UEs (or the minimum average call blocking rate of satellites) when the network resource is sufficient (or insufficient). In the paper, we fill this gap by proposing two graph-based algorithms for networks with sufficient and insufficient resources, respectively. Simulations show the proposed algorithms have significant improvements in the number of handovers of UEs and the call blocking rate of satellites over the state-of-the-art methods.

Dockless electric bike (E-bike) sharing has become a new urban modality of green transportation to offer convenient services. Typically, the service provider arranges a truck starting from the depot to visit multiple parking locations to replace low-energy batteries. However, visiting many parking locations may cause a considerable tour cost. One efficient way is to aggregate low-energy E-bikes together. Some incentive mechanisms are thus adopted to encourage E-bike users to move their bikes to suitable parking locations, but leading to an incentive cost. The service provider would like to balance the tour cost of the truck and the incentive cost of E-bike users. To address this problem, the paper formulates an optimization problem and then proposes an approximation algorithm. The simulation results with the real dataset show that our algorithm outperforms the other baselines.

Recently, the topic for the development of efficient handover algorithms to select the target (serving) base station (BS) such that the average throughput of user equipments (UEs) is maximized in heterogeneous cellular networks has received much attention. In the literature, the latest handover algorithms employ the upper confidence bound (UCB) policy, one efficient method for the multi-armed bandit (MAB) problem, since the UCB policy can identify the critical actions quickly by taking the uncertainty of the action reward into account. However, the UCB policy does not take advantage of the observed features, which could lead to poor performance in the UE throughput since the throughput of a UE served by a BS is highly correlated to the observed features including the bandwidth of the BS, the number of UEs served by the BS, and the spectral efficiency of the UE achieved by the BS. By contrast, besides the consideration of the uncertainty of the action reward, the linear upper confidence bound (LinUCB) policy also makes use of the observed features to estimate the action reward. In this paper, we make the first attempt to propose a LinUCB-based handover algorithm. The challenge is to define the reward and observed features highly correlated to the UE throughput such that the reward is a linear combination of the observed features as demanded by the LinUCB policy. We conduct simulations on the network simulator ns-3 to show that the proposed algorithm outperforms the state-of-the-art handover algorithms in terms of the average UE throughput.

In the Third Generation Partnership Project (3GPP) specification [1], the conditional hand over procedure is defined to reduce the hand over failures in 5G networks by early preparation of the radio resource for user equipment (UE). In this paper, in order to minimize the resource reservation time while maintaining the radio link failures (RLF) rate of a UE, we make the first attempt to trigger the conditional handover of the UE only when the UE would experience an RLF in the near future. Our idea is to adjust the handover margin of triggering the conditional hand over of a UE based on the prediction on whether the UE would experience an RLF in the near future. To achieve an accurate prediction in the urban scenario with blockages, we reduce the conditional handover problem to a classification problem and solve the classification problem using a recurrent neural network (RNN). Simulations show that the proposed algorithm has extraordinary performance in terms of the RLF rate and resource reservation time, as compared with the state-of-the-art methods.

In the literature, there are many handover algorithms of selecting one target serving base station (BS) for a user equipment (UE). However, these algorithms are not suitable for a UE capable of the multi-connectivity communication since they do not address how to determine an adequate number of the target serving BSs for an individual UE and the best combination of the target serving BSs for a UE usually cannot be found by one-by-one greedy selection. On the other hand, the up-to-date handover algorithms of selecting multiple target serving BSs for a UE either do not determine an adequate number of the target serving BSs or demand a considerable time to choose a good set of target serving BSs. In this paper, we propose a Graph-to-Sequence reinforcement learning method to fill this gap. Simulations show that the proposed method outperforms the state-of-the-art algorithms in terms of the average quality of experience (QoE) of a UE.

The Adiabatic Quantum-Flux-Parametron (AQFP), which benefits from low power consumption and rapid switching, is one of the rising superconducting logics. Due to the rapid switching, the delay of the inputs of an AQFP gate is strictly specified so that additional buffers are needed to synchronize the delay. Meanwhile, to maintain the symmetry layout of gates and reduce the undesired parasitic magnetic coupling, the AQFP cell library adopts the minimalist design method in which splitters are employed for the gates with multiple fan-outs. Thus, an AQFP circuit may demand numerous splitters and buffers, resulting in a considerable amount of power consumption and delay. This provides a motivation for proposing an effective splitter and buffer insertion algorithm for the AQFP circuits. In this paper, we propose a dynamic programming-based algorithm that provides an optimal splitter and buffer insertion for each wire of the input circuit. Experimental results show that our method is fast, and has a 10% reduction of additional Josephson Junctions (JJs) in the complicated circuits compared with the state-of-the-art method.

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

In a shared software-defined network (SDN), the controller should provide isolation guarantees across flows (users) to predict network performance and minimize disruption from some malicious flows. In an SDN, packets are forwarded by flow rules installed in flow tables, and the capacity of flow tables is usually limited by power and cost constraints so that a limited number of flows can be accommodated. To date, OpenFlow 1.4.0 introduces the flow rule replacement, which allows replacing existing flow rules with new ones once the flow table is full. This is called flow table overflow. Although flow table overflow may lead to an increase in packet delay, our experiments on an SDN testbed show that the network performance could benefit by admitting more flows through slightly overbooking the flow table resource. In this paper, we address the Flow table Overbooking isoLation guArantees problem (FOLA), which aims to maximize minimum progress of flows and minimize maximum flow table overflow. To that end, an algorithm with guaranteed minimum progress and bounded maximum flow table overflow is proposed. Trace-driven experiments on an SDN testbed show that our solution outperforms state-of-the-art methods for maximizing minimum progress in terms of the minimum progress and network throughput.

We study fair multi-resource allocation in Network Function Virtualization (NFV) clusters, where the relative amounts of (multiple) resources allocated for a virtual network function (VNF) can be flexibly adjusted. In NFV clusters, the fairness across users can benefit from the flexibility of the multi-resource allocation for VNFs, but we also have to address a research challenge: What relative amounts of resources should be allocated to a VNF? Although many studies address fair multi-resource allocation in the literature, they all assume that the relative amounts of resources allocated for a VNF are pre-determined and fixed, which would lead to the poor fairness across users. In this paper, we make the first attempt to propose an algorithm to allocate resources to users under the circumstance of flexible multi-resource allocation for VNFs. Our algorithm is shown to achieve max-min fairness and satisfy two beneficial properties of fair multi-resource allocation: Pareto efficiency and envy-freeness. Simulations also show our algorithm can allocate resources in a fair and efficient way in NFV clusters.

In 5G networks, microcells are densely deployed for the spatial reuse to cooperate with the traditional macrocells, and thus a moving user equipment (UE) usually experiences a more irregular change of the signal-to-interference-plus-noise ratio (SINR) and is more likely to disconnect to the serving cells when proceeding a handover. Hence, efficient handover algorithms in 4G networks no longer perform well in 5G networks. In addition, deep learning is a common method able to deliver highly accurate classification results for classification problems. In this paper, we make the first attempt to consider the SINR change of a UE in the handover problem in 5G networks, and to reduce the handover problem to a classification problem and solve the classification problem using a deep neural network (DNN). Simulations show that the proposed algorithm has a good performance in terms of the radio link failure rate and the ping-pong rate in 5G networks, as compared with the state-of-the-art methods.

Multi-protocol label switching (MPLS) is supported by OpenFlow version 1.2 or higher and widely used in software defined networking (SDN) to achieve higher performance and flexibility. Due to the shortage of the ternary content addressable memory (TCAM), the number of forwarding entries installed in a switch needs to be bounded (node path-degree constraints). Besides, the maximum concurrent flow problem, which asks to maximize the minimum fraction of the flow of a commodity to its demand, is widely studied because of a wide range of applications. In this paper, we address the maximum concurrent flow problem while ensuring the flow routed for a commodity does not exceed its demand (demand constraints) and the node path-degree constraints are imposed, termed the bounded path- degree maximum concurrent flow (BPMCF) problem. We first show the BPMCF problem is NP-hard and intractable to devise any approximation algorithm. Then, we propose an algorithm for the BPMCF problem. Finally, we evaluate the performance of the proposed algorithm through computer simulations and experiments on Global Environment for Network Innovations (GENI) testbed using the real-life traces collected from SNDlib.

In this paper, we study a multiple sink placement problem with latency and reliability guarantee in a lossy wireless sensor network and its applications in an advanced metering infrastructure (AMI) network. We show the problem is NP-hard and propose an algorithm for the problem. The proposed algorithm jointly considers the routing protocol RPL [1], the MAC protocol TSCH [2], and the scheduling approach DeTAS [3] to meet the latency and reliability requirements in a real AMI network. We conduct simulations on the real data for the establishment of an AMI network. Simulation results show the proposed algorithm has a good performance in the number of selected concentrators and the balanced number of smart meters connected to the selected concentrators.

Marketing through online social networks is convenient, low-cost, and beneficial for companies seeking to expand their customer numbers. In the literature, many studies address the influence maximization problem with one or multiple products, which selects initial consumers (seeds) to spread one or multiple product information such that the number of consumers receiving these product information (the influenced consumers) is maximized. However, to date, none of these schemes take the rumors and the beliefs of other persons that could significantly change the consumer's behavioral intention into account at once. In this paper, we fill this gap by proposing a new variant of the influence maximization problem with multiple products, the Budgeted Behavioral Intentions Maximization problem, which asks for a set of seeds with the total cost not greater than a given budget in online social networks such that the total expected behavioral intentions of the consumers influenced by the selected seeds and the rumors are maximized. In addition, we propose an approximation algorithm for the Budgeted Behavioral Intentions Maximization problem. We also conduct simulations to evaluate the performance of our algorithm using real traces and synthesis data. Experimental results show that our algorithm outperforms several greedy algorithms.

Marketing through mobile social networks is convenient, low-cost, and beneficial for small companies seeking to expand their customer numbers. In the literature, many studies address the influence maximization problem, which selects initial consumers (seeds) to spread the product information such that the number of consumers receiving the product information (the influenced consumers) is maximized. However, to date, none of these schemes take the beliefs of other persons that could significantly change the consumer's behavioral intention into account. In this paper, we fill this gap by proposing a new variant of the influence maximization problem, the Budgeted Seed Selection (BSS) problem, which asks for a set of seeds with the total cost not greater than a given budget in a mobile social network such that the total expected behavioral intentions of the consumers influenced by the selected seeds are maximized. In addition, we propose an approximation algorithm for the BSS problem. We also conduct simulations to evaluate the performance of our algorithm using real traces and synthesis data. Experimental results show that our algorithm evaluates an approximately optimal seed set for the BSS problem and outperforms several greedy algorithms.

Geographic routing protocols route packets in a hop-by-hop manner, where a node selects a relay node to forward packets among the (1-hop) neighboring nodes based on the obtained (geographic) location information of the neighboring nodes. To employ geographic routing protocols, two neighboring nodes need to exchange the location information with each other periodically. In a mobile ad hoc network, however, a packet transmitted between two neighboring nodes may be lost due to the out-of-date location information, resulting in demanding extra energy to retransmit the packet. In this paper, by considering the out-of-date neighboring location information, we propose two methods capable of augmenting geographic routing protocols to reduce energy consumption in mobile ad hoc networks. The first one considers a tradeoff between the progress distance and the energy consumption when selecting a relay node. The second one puts emphasis only on the energy consumption when selecting a relay node, and it consumes minimum energy to route a packet between a source-destination pair in the continuous domain. Simulations show that geographic routing protocols augmented with our methods can significantly reduce the energy consumption while preserving the high packet delivery rate.

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.

Recently, Network Function Virtualization (NFV) has been proposed to transform from network hardware appliances to software middleboxes. Normally, a demand needs to invoke several Virtual Network Functions (VNFs) in a particular order following the service chain along a routing path. In this paper, we study the joint problem of VNF placement and path selection to better utilize the network. We discover that the relation between the link and server usage plays a crucial role in the problem. We first propose a systematic way to elastically tune the proper link and server usage of each demand based on network conditions and demand properties. In particular, we compute a proper routing path length, and decide, for each VNF in the service chain, whether to use additional server resources or to reuse resources provided by existing servers. We then propose a chain deployment algorithm to follow the guidance of this link and server usage. Via simulations, we show that our design effectively adapts resource usage to network dynamics, and, hence, serves more demands than other heuristics.

In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist and consider the cases where the link quality is not perfect. We show that these problems are NP-complete and propose$O(1)$-approximation algorithms for each of them. Simulations show that the proposed algorithms have good performance in terms of energy cost.

In geographic routing protocols, face forwarding is often used in helping a packet escape from the stuck state. To guarantee packet delivery, face forwarding usually routes a packet in a planar subgraph of the network, which might disable many edges in the network and, in turn, worsen the routing performance and reduce the link failure tolerance. In this paper, we aim to improve the connectivity of the graphs on which face forwarding can guarantee packet delivery. We present a sufficient condition for the packet delivery guarantee of GFG face forwarding, augment the graph used in face forwarding with selected disabled edges in the network, and propose a geographic routing protocol, termed GFG-NP, in which a packet escapes from the stuck state by performing GFG face forwarding on the augmented graph that might be non-planar. We show, using theoretical analysis, that GFG-NP guarantees packet delivery when performed on the augmented graphs of the partial Delaunay triangulation (PDT) and the CLDP-stable graph constructed by the cross-link detection protocol (CLDP), termed PDT- and CLDP-augmented graphs, respectively. In addition, simulations on network simulator NS-2 show that GFG-NP with face forwarding performed on PDT- and CLDP-augmented graphs outperforms GFG with face forwarding performed on PDT and the CLDP-stable graph, respectively, in terms of load balance, path length, routing latency, and packet delivery rate.

In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We find that many goals for network deployment, such as maximizing the number of covered users, the size of the coverage area, or the total throughput of the network, can be modeled with a submodular set function. Specifically, given a set of routers, the goal is to find a set of locations S, each of which is equipped with a router, such that S maximizes a predefined submodular set function. However, this deployment problem is more difficult than the traditional maximum submodular set function problem, e.g., the maximum coverage problem, because it requires all the deployed routers to form a connected network. In addition, deploying a router in different locations might consume different costs. To address these challenges, this paper introduces two approximation algorithms, one for homogeneous deployment cost scenarios and the other for heterogeneous deployment cost scenarios. Our simulations, using synthetic data and real traces of census in Taipei, Taiwan, show that the proposed algorithms achieve better performances than other heuristics.

Using the double-ruling technique, many data replication and retrieval schemes achieve low data retrieval latency. However, none of these schemes are location-free schemes in mobile ad hoc networks (MANETs). In this paper, we propose a zero-knowledge double-ruling-based location-free data replication and retrieval scheme (MobiMark) in MANETs. Our primary idea is to label the grid-like structured landmarks in the network using the landmark-labeling, dynamically designate the node that is nearest to a landmark as the landmark broker, and transmit the consumers' interests (or producers' data) to all horizontal (or vertical) landmark brokers using the double-ruling technique. Simulations show that MobiMark achieves good performance in terms of data retrieval rate and data retrieval latency.

The MapReduce/Hadoop architecture has become very important and effective in cloud systems because many data-intensive applications are usually required to process big data. In such environments, big data is partitioned and stored over several data nodes; thus, the total completion time of a task would be delayed if the maximum access latency among all pairs of a data node and its assigned computation node is not bounded. Moreover, the computation nodes usually need to communicate with each other for aggregating the computation results; therefore, the maximum access latency among all pairs of assigned computation nodes also needs to be bounded. In the literature, it has been proved that the placement problem of computation nodes (virtual machines) to minimize the maximum access latency among all pairs of a data node and its assigned computation node and among all pairs of assigned computation nodes does not admit any approximation algorithm with a factor smaller than two, whereas no approximation algorithms have been proposed so far. In this paper, we first propose a 3-approximation algorithm for resolving the problem. Subsequently, we close the gap by proposing a 2-approximation algorithm, that is, an optimal approximation algorithm, for resolving the problem in the price of higher time complexity. Finally, we conduct simulations for evaluating the performance of our algorithms.

The topology of a wireless sensor network changes as some sensors run out of power, fail, or join the network. In this paper, a delivery-guaranteed location-free routing protocol, termed LF-GFG, is proposed for a wireless sensor network with changing topology. We first describe the network multivalued embedding protocol to map each node and each link in the network to multiple virtual nodes and multiple virtual links, respectively, to constitute a virtual network in a plane and demonstrate the virtual network planarization protocol to obtain the connected spanning planar subgraph of the virtual network. Then, LF-GFG forwards a packet using the greedy-face-greedy (GFG) algorithm based on the virtual network and the connected spanning planar subgraph. As the network topology changes, the maintenance scheme reconstructs a connected spanning planar subgraph of the virtual network, using just local information, only if the spanning planar subgraph becomes disconnected. Thus, unlike existing location-free routing protocols, LF-GFG demands only lightweight maintenance costs as the network topology changes due to node addition or removal. Simulations in the network simulator NS-2 show that LF-GFG has good performance in terms of the construction message overhead, the maintenance time and message overhead, and the packet delivery rate while ensuring moderate routing latency costs.

In multiuser MIMO (MU-MIMO) LANs, the achievable throughput of a client depends on who is transmitting concurrently with it. Existing MU-MIMO MAC protocols, however, enable clients to use the traditional 802.11 contention to contend for concurrent transmission opportunities on the uplink. Such a contention-based protocol not only wastes lots of channel time on multiple rounds of contention but also fails to maximally deliver the gain of MU-MIMO because users randomly join concurrent transmissions without considering their channel characteristics. To address such inefficiency, this paper introduces MIMOMate, a leader-contention-based MU-MIMO MAC protocol that matches clients as concurrent transmitters according to their channel characteristics to maximally deliver the MU-MIMO gain while ensuring all users fairly share concurrent transmission opportunities. Furthermore, MIMOMate elects the leader of the matched users to contend for transmission opportunities using traditional 802.11 CSMA/CA. It hence requires only a single contention overhead for concurrent streams and can be compatible with legacy 802.11 devices. A prototype implementation in USRP N200 shows that MIMOMate achieves an average throughput gain of 1.42× and $1.52× over the traditional contention-based protocol for two- and three-antenna AP scenarios, respectively, and also provides fairness for clients.

In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We found that many goals for network deployment, such as maximizing the number of covered users or areas, or the total throughput of the network, can be modelled with the submodular set function. Specifically, given a set of routers, the goal is to find a set of locations S, each of which is equipped with a router, such that S maximizes a predefined submodular set function. However, this deployment problem is more difficult than the traditional maximum submodular set function problem, e.g., the maximum coverage problem, because it requires all the deployed routers to form a connected network. In addition, deploying a router in different locations might consume different costs. To address these challenges, this paper introduces two approximation algorithms, one for homogeneous deployment cost scenarios and the other for heterogeneous deployment cost scenarios. Our simulations, using synthetic data and real traces of census in Taipei, show that the proposed algorithms achieve a better performance than other heuristics.

We address the problem of information brokerage, where information consumers search for the data acquired by information producers. To the best of our knowledge, there exists no retrieval-guaranteed location-aware information brokerage scheme with a bounded data retrieval path length and bounded replication and retrieval message overhead costs available for use in 3D wireless ad hoc networks to date. In this paper, we propose a novel location-aware information brokerage scheme, termed LAIB, where the network area is divided into cube grids, and data are replicated and retrieved in the hashed geographic location in each grid designated by the producer and the consumer, respectively. In LAIB, a polylogarithmic number of grids are designated by the producer and by the consumer, and at least one grid, whose distance from the grid of the consumer is smaller than the distance from the grid of the consumer to the grid of the producer, is designated by both the producer and the consumer. Simulations show that, as the network area is divided into a moderate number of grids, LAIB has good performance in term of retrieval latency stretch while ensuring moderate replication memory, replication message, and retrieval message overhead costs.

In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist. We show these two problems are NP-complete, and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms each have good performance in terms of the energy cost.

We study the information brokerage schemes in wireless sensor networks, which allow consumers to obtain data from producers by replicating and retrieving data in a certain set of sensors, and propose a novel information brokerage scheme, termed RDRIB. Unlike existing information brokerage schemes, RDRIB guarantees successful data retrieval without using any boundary detection algorithm and the geographic location information acquired by the global positioning system (GPS). In RDRIB, the double-ruling technique is used to replicate and retrieve the data within a constructed virtual boundary, and simulations show that RDRIB has good performance in terms of the replication memory overhead, the replication message overhead, the retrieval message overhead, the retrieval latency, and the construction message overhead.

In the tracking system, a better prediction model can significantly reduce power consumption in a wireless sensor network because fewer redundant sensors will be activated to keep monitoring the object. The Gauss-Markov mobility model is one of the best mobility models to describe object trajectory because it can capture the correlation of object velocity in time. Traditionally, the Gauss-Markov parameters are estimated using an autocorrelation technique or a recursive least-squares estimation technique; either of these techniques, however, requires a large amount of historical movement information of the mobile object, which is not suitable for tracking objects in a wireless sensor network because they demand a considerable amount of message communication overhead between wireless sensors which are usually battery powered. In this paper, we develop a Gauss-Markov parameter estimator for wireless sensor networks (GMPE_MLH) using a maximum likelihood technique. The GMPE_MLH model estimates the Gauss-Markov parameters with few requirements in terms of message communication overhead. Simulations demonstrate that the GMPE_MLH model generates negligible differences between the actual and estimated values of the Gauss-Markov parameters and provides comparable prediction of the mobile object's location to the Gauss-Markov parameter estimators using an autocorrelation technique or a recursive least-squares estimation.

Wireless sensor networks are formed by connected sensors that each have the ability to collect, process, and store environmental information as well as communicate with others via inter-sensor wireless communication. These characteristics allow wireless sensor networks to be used in a wide range of applications. In many applications, such as environmental monitoring, battlefield surveillance, nuclear, biological, and chemical (NBC) attack detection, and so on, critical areas and common areas must be distinguished adequately, and it is more practical and efficient to monitor critical areas rather than common areas if the sensor field is large, or the available budget cannot provide enough sensors to fully cover the entire sensor field. This provides the motivation for the problem of deploying the minimum sensors on grid points to construct a connected wireless sensor network able to fully cover critical square grids, termed CRITICAL-SQUARE-GRID COVERAGE. In this paper, we propose an approximation algorithm for CRITICAL-SQUARE-GRID COVERAGE. Simulations show that the proposed algorithm provides a good solution for CRITICAL-SQUARE-GRID COVERAGE.

Because the global positioning system (GPS) consumes a large amount of power and does not work indoors, many GPS-free information brokerage schemes are proposed for wireless sensor networks. Each of them, however, either cannot guarantee successful data retrieval or demands a great deal of message overhead to replicate the data. In this paper, we propose a GPS-free information brokerage scheme, RDRIB, in which the double-ruling technique is used to replicate and retrieve the data. RDRIB guarantees successful data retrieval, and, in addition, simulations show that RDRIB has good performance in terms of the replication message overhead and the construction message overhead.

In GPSR-like routing, such as GPSR, GFG, GOAFR+, and GPVFR, perimeter forwarding is used to recover from a greedy forwarding failure by routing the packet to a progress node along the face boundary. The problem of perimeter forwarding is that many hops may be taken if the packet is forwarded in the wrong direction. We propose an algorithm, termed ProgressFace, that uses an additional traversal step to decide the direction of perimeter forwarding. A concave node sends a short packet to traverse the face boundary to identify the progress set, which consists of at most four nodes, such that, for any destination, at least one progress node is in the progress set or the neighbor set. Additionally, the hop distances of the nodes in the progress set along both directions are evaluated so that the shorter one is identified. The following packets encountering the concave node each are then sent along the corresponding direction toward the progress node in the progress set or the neighbor set. Simulations show that GPSR, GFG, GOAFR+, and GPVFR each conduct a shorter routing path, if augmented with the ProgressFace algorithm.

Because the global positioning system (GPS) consumes a large amount of power and does not work indoors, many virtual-coordinate-based routing protocols are proposed for wireless sensor networks in which geographic location information is unavailable. Each of them, however, cannot guarantee packet delivery or constructs a virtual coordinate system with a complex structure. In this paper, we propose a method capable of augmenting virtual-coordinate-based routing protocols to guarantee packet delivery. Firstly, we introduce the virtual face construction protocol and the virtual face naming protocol to construct and name virtual faces, respectively. Subsequently, the VirtualFace algorithm is presented to route a packet from a dead-end node to a progress node by traversing the boundaries of the virtual faces from face to face. Simulations show that virtual-coordinate-based routing protocols including GLIDER, Hop ID, GLDR, and VCap augmented with the VirtualFace algorithm guarantee packet delivery while ensuring moderate routing path length overhead costs.

A wireless sensor network has unidirectional links because sensors can have different transmission ranges, sensors have unstable transmission ranges, and a hidden terminal problem exists. In this paper, we introduce a virtual coordinate assignment protocol (ABVCap_Uni) to assign virtual coordinates to nodes that have no geographic information in wireless sensor networks with unidirectional links, and we propose a routing protocol based on the ABVCap_Uni virtual coordinates. Our routing protocol guarantees packet delivery without computation and storage of global topology features in a discrete domain. Using simulation, we evaluate the performance of the proposed routing protocol (ABVCap_Uni routing), the greedy landmark- descent routing protocol (GLDR+VLM routing), and the greedy routing protocol based on physical coordinates (Euclidean routing). The simulations demonstrate that our routing protocol ensures moderate routing path length cost overhead.

This work is to augment a debris flow observation and early warning system with wireless sensor networks. Previously, the GIS at Fengchia University has constructed and deployed state-of-the-art, stationary and mobile types of observation systems at nearly 20 sites throughout Taiwan. These sites collect data from sensors ranging from rain gauges and tension cables to ultrasonic sensors and CCD cameras, and transmit them back to the GIS via a lower-orbit satellite uplink in real-time. A new wireless sensor network and middleware system are being designed and implemented to overcome several limitations with the current system. Wireless communication capabilities are being incorporated to enhance the coverage. Previously, most connections between the sensors and the server before the satellite uplink are wired or Wi-Fi with fixed topology and limited range. New wireless interfaces with a 500 m - 1 km range plus energy harvesting devices on the sensors reduces deployment effort and cost. More importantly, it is now becoming possible to construct and deploy brand new types of mobile sensor nodes that move with the debris flow along its path. Such sensor nodes are to be housed in pyramid-shaped, weather-proof capsules that contain motion sensors, GPS and other localization devices, energy harvesting and storage devices, and wireless transceivers. Normally in low-power or standby mode, these capsules would be deployed in the path of potential debris flows. They would stand steadily during normal weather conditions including wind, rain, and water flow. They would get triggered by a threshold motion detector or a rain gauge and start actively monitoring the flow. As it flows with the debris, these capsules transmit their sensor data wirelessly, via other relaying nodes if necessary. Based on the shape and mass of the capsule itself and the velocity, researchers can derive the direction and magnitude of the flow in brand new ways.

Wireless sensor networks have often been used to monitor and report the locations of moving objects. Since sensors can also be used for storage, a wireless sensor network can be considered a distributed database, enabling us to update and query the location information of moving objects. Many researchers have studied the problem of how to construct message-pruning trees that can update a database and query objects with minimum cost (the Minimum Cost Message-Pruning Tree problem). The trees are constructed in such a way that the total cost of updating the database and querying objects is kept as minimum as possible, while the hardness of the Minimum Cost Message-Pruning Tree problem remains unknown. In this paper, we first show that the Minimum Cost Message-Pruning Tree problem is NP-complete. Subsequently, since the message-pruning tree with minimum cost is hard to be constructed in polynomial time, we propose a new data aggregation structure, a message-pruning tree with shortcuts, instead of the message-pruning tree. Simulation results show that the proposed data aggregation structure significantly reduces the total cost of updating the database and querying objects, as compared to the message-pruning tree.

A k-hop dominating set is a subset of nodes such that each node that is not in the set can be reached within k hops from at least one node in the set. A connected k-hop dominating set can be used for disseminating topology update packets or route request packets, in which the flooding search space is reduced to the set, resulting in significant flooding overhead reduction in broadcast-related applications. In mobile ad hoc networks, a connected k-hop dominating set may become disconnected due to node mobility or switch-off, which necessitates the reformation of the k-hop dominating set. In this paper, we identify a sufficient condition that guarantees the connectivity of the virtual backbone. The condition can be verified in a distributed manner by the node only having the link information of its neighbors. (Unless specified otherwise, the term "neighbor" denotes a "1-hop neighbor." The link information of neighbors can be obtained by 2-hop neighbor information or 1-hop neighbor positions.) With the help of this condition, we propose a distributed algorithm for efficiently constructing and maintaining connected k-hop dominating sets in mobile ad hoc networks. Simulations show that our connected k-hop dominating set is small and stable and needs little maintenance overhead in the random-walk mobility and Gauss-Markov mobility models.

In this paper, we propose a method of constructing a virtual coordinate system (ABVCap) in wireless sensor networks where location information is not available. A routing protocol based on ABVCap virtual coordinates is also introduced. Our routing protocol guarantees packet delivery and does not require computing and storing of the global topological features. Using simulations, we evaluate the performance of the proposed routing protocol (ABVCap routing), the greedy routing protocol based on VCap virtual coordinates (VCap routing), the greedy routing protocol based on physical coordinates (Euclidean routing), greedy perimeter stateless routing (GPSR routing), and geometric spanner routing (GSR routing). The simulations show that our method guarantees packet delivery while ensuring moderate routing path length overhead costs.

This paper proves that deploying sensors on grid points to construct a wireless sensor network that fully covers critical grids using minimum sensors (critical-grid coverage problem) and that fully covers a maximum total weight of grids using a given number of sensors (weighted-grid coverage problem) are each NP-complete

We provide a better sufficient condition for the connectivity of cluster heads asymptotically almost surely (a.a.s.) and a tighter bound on the number of cluster heads in HEED (O. Younis and S. Fahmy, 2004)

A core-based group-shared multicast tree is a shortest path tree rooted at core node that distributes packets to and from all group members. Traditionally, the bandwidth cost consumed by transmitting a packet via the tree is evaluated by the total weights of all the edges. And, the cost is minimized by constructing the multicast tree that has minimum total weights of edges to span all group members. However, when the local broadcasting operation is used to multicast a packet, we found that the cost is supposed to be evaluated by the total weights of all senders that include the core and all non-leaves. Since the multicast tree with the number of nodes greater than or equal to three has minimum cost only when the core is not a leaf it leads us to find the multicast tree with the minimum number of non-leaves when each sender node has a unit weight. However, no polynomial time approximation scheme can be found for the minimum non-leaf multicast tree problem unless P=NP since the problem is not only NP-hard but also MAX-SNP hard. Thus, a heuristic is proposed to dynamically construct and adjust the multicast tree in a mobile ad hoc network. Experimental results show that our multicast tree has smaller number of non-leaves than others in the geometrically distributed network model.

Message routing achieves the internode communication in parallel computers. A reliable routing is supposed to be deadlock-free and fault-tolerant. While many routing algorithms are able to tolerate a large number of faults enclosed by rectangular faulty blocks, there is no existing algorithm that is capable of handling irregular faulty patterns for wormhole networks. In this paper, a two-staged adaptive and deadlock-free routing algorithm called "Routing for Irregular Faulty Patterns" (RIFP) is proposed. It can tolerate irregular faulty patterns by transmitting messages from sources or to destinations within faulty blocks via multiple "intermediate nodes." A method employed by RIFP is first introduced to generate intermediate nodes using the local failure information. By its aid, two communicating nodes can always exchange their data or intermediate results if there is at least one path between them. RIFP needs two virtual channels per physical link in meshes.

We propose an adaptive and deadlock-free routing algorithm to tolerate irregular faulty patterns using two virtual channels per physical link. It can improve the node utilization up to 100%. When a node becomes faulty or recovered, the central control unit constructs a directed path graph which is used for generating the intermediate nodes of the message path. Thus a message can be transmitted from sources or to destinations within faulty blocks via a set of "intermediate nodes". Our method requires the global failure information if the central control unit is not available.

Unicast V is a progressive, misrouting algorithm for packet or virtual cut-through networks. A progressive protocol forwards a message at an intermediate node if a nonfaulty profitable link is available and waits, deroutes, or aborts otherwise. A misrouting protocol uses both profitable and nonprofitable links at each node; thus, a message can move farther away from its destination at some steps. Unicast V is simple for hardware implementation, requires a very small message overhead, and makes routing decisions by local failure information only. However, it is claimed to be partially adaptive and to be able to tolerate static faults in hypercubes only. In this paper, we uncover some new features of Unicast V: (1) it is fully-adaptive, (2) it also applies to meshes and tori, and (3) it can tolerate dynamic faults by careful implementation. In addition, we also provide bounds on the performance of the algorithm.