In the next-generation emergency communication networks, unmanned aerial vehicles (UAVs), serving as aerial base stations, have attracted increasing attention recently due to their high mobility and low cost. Therefore, this paper conceives a heterogeneous UAVs assisted intelligent communication network system, in which tethered UAVs (T-UAV) make ground users (GUs) scheduling decisions to avoid resource competition, while other UAVs cooperate to provide communication services. However, the limited onboard resources of UAVs and cooperativecompetitive problems among heterogeneous UAVs becomes key challenges in UAV-assisted intelligent emergency communication networks. In order to tackle these issues, we propose a heterogeneous multi-agent approximate policy optimization (HMAPPO) algorithm to maximize the total fair energy efficiency by jointly optimizing UAV trajectories and user scheduling. Simulation results demonstrate that HMAPPO outperforms other baseline algorithms in terms of energy efficiency of the system and fairness of GUs. Furthermore, benefit to the partial parameter sharing mechanism, the proposed HMAPPO significantly accelerates the training process compared to other benchmark algorithms.

The safe and high-efficiency operation of low-altitude vehicles (LAVs) is the key to supporting the rapid development of the low-altitude economy. However, the conventional space-air-ground integrated network (C-SAGIN) mainly focuses on ground users, which is difficult to provide high-quality services for LAVs. In this article, we first propose a novel architecture of low-altitude centric space-air-ground integrated network (LAC-SAGIN), where low-altitude airspace and LAVs become the communication centers. A detailed comparison is further illustrated between these two architectures in terms of their composition and performance metrics. Although LAC-SAGIN can effectively support the low-latency and continuous communication of LAVs, it still faces several key implementation challenges including insufficient low-altitude infrastructures, high mobility of LAVs and its diversified task requirements, and low transmission efficiency and energy efficiency in airspace communication. To address these challenges, the corresponding three countermeasures are proposed, which reveal the future research direction of LAC-SAGIN.

Unmanned Aerial Vehicle (UAV) clusters are widely used in spectrum reconnaissance, where spectrum samples are transmitted back to the sink through flying ad hoc network (FANET). High sampling frequencies are required, but result in a large amount of data not being transmitted over the wireless network, affecting throughput and reliability of the network. The problem boils down to what a good sampling frequency is and how to find it. There is an unknown dynamic sampling frequency threshold, beyond which high packet loss occurs. Prior work focused on achieving higher frequencies through FANET optimization but neglected methods to find this threshold and achieve a maximum value. We propose an adaptive protocol based on binary search. With limited bandwidth and consistent sampling frequency, the protocol dynamically adjusts sampling frequencies in a phased manner at the application layer to maximize the sampling frequency that the network can handle. In addition to spectrum reconnaissance, this protocol can be extended to other applications with consistent sampling frequencies. We have constructed an application based on the EXata simulation platform to analyze the performance of the protocol in delay, stability, reliability, and search times. Simulation results show the protocol improves the efficiency and survivability of spectrum reconnaissance.

We consider flying ad hoc networks (FANETs) operating in frequency-sweeping jamming environment, where jamming significantly impairs the performance of routing protocols, leading to unstable network communications and data loss. Currently, jamming is defended at physical and link layer by military radio stations, which focuses on restoring communication of a single link. Existing routing protocols fail to utilize valuable information from these radio stations effectively to restore a multi-hop path. To address this issue, we propose a novel routing protocol optimization method that combines spectrum awareness techniques to further mitigate the adverse effects of jammers on overall network performance. The proposed method utilizes the obtained jammer information and bit error rate to modify various parameters in the routing protocol, enabling it to adapt to jamming scenarios. We implement the optimized protocol on the EXata simulation platform. The simulation results show that, compared with the reference protocols, the proposed protocol can increase the throughput by up to 12% and improve the packet delivery ratio by up to 14% in the presence of frequency-sweeping jammers.

Unmanned Aerial Vehicle (UAV) is frequently used in tactical scenarios due to its flexibility, where networking among UAVs is an enabling technology for cooperation. However, dy-namic location changes and jamming attacks in tactical scenarios pose significant challenges to the stability and reliability of UAV networks. Observing that network conditions change frequently and a single protocol does not work well across different network conditions, we propose a MAC protocol switching strategy, MS-MAC, which is driven by the missions and interference, switching among carrier sense multiple access (CSMA) protocol and time division multiple access (TDMA) protocol. Instead of fixing the number of slots in TDMA, we propose a dynamic variant whose time slot number is determined by traffic load. MS-MAC switches between dynamic TDMA and CSMA based on channel status. We implement the protocol on the EXata platform, and simulations verify the effectiveness of the protocol against existing protocols.

Nowadays, unmanned aerial vehicle (UAV) clusters are widely used in military and civil scenarios to perform spectrum reconnaissance. In this task, a high sampling frequency is desirable, but it results in a large volume of data that may not be transmitted through the wireless network. The problem boils down to what a good sampling frequency is and how to find it. There is an unknown dynamic sampling frequency threshold exceeding which leads to high packet loss. To find this threshold and achieve the maximum sampling frequency, we propose a distributed protocol based on binary search to find the best sampling frequency, taking consideration of performance metrics like latency, stability, reliability, and search times. Under the premise of limited bandwidth and consistent spectrum sampling frequency of UAVs, our protocol can dynamically adjust the spectrum sampling frequency at the application layer. We have built a network application on the EXata simulation platform to analyze the performance of the proposed protocol. The simulation results show that the protocol improves the efficiency and survivability of spectrum reconnaissance.

Unmanned Aerial Vehicle (UAV) swarm is becoming an important part of the future battlefield. Due to the high confrontation and the multiplicity types of interference in the battlefield environment, ensuring the topology integrity of the UAV formation becomes the premise of achieving the target mission. In this paper, we propose an optimal swarm reconstruction strategy for scenarios where some UAVs are destroyed. Our strategy reorganizes the remaining isolated UAVs into UAV clusters through reconstruction. We formulate the problem as an integer linear programming problem and propose a minimum-cost maximum-flow-based algorithm to solve it to optimality in polynomial time. Numerical results show that the proposed strategy can find the optimal path-cost solution, and the solution also takes into account the remaining energy and topoloaical change,

With an increasing number of mobile devices equipped with screens and cameras, screen-camera communication (SCC) systems enable data exchange between devices conveniently and efficiently. By encoding data with spatial and temporal diversity on a screen, multiple users with a camera can receive data without setting up a wireless network. However, as the transmitter pushes the limits of increasing throughput with a high display rate, the receiver actually suffers from a low goodput caused by composite frames. Those frames cannot be decoded correctly with existing methods. To address this problem, we propose a reliable data recovery scheme named RescQR. In RescQR, a mixture separation scheme coupled with a dedicated frame border is proposed to separate composite frames. A Viterbi-based data recovery scheme is proposed to recover data from blurred regions in composite frames. Additionally, an auto-configuration method with the help of a front camera is proposed to adjust parameters automatically according to the estimated distance between the screen and the camera. Our prototype and experiments demonstrate that RescQR achieves a data goodput of 400+kbps even with standard QR codes, which significantly outperforms previous solutions.

UAV networks are wireless networks composed of dynamic UAVs, characterized by a complex and constantly changing wireless environment. A recent TCP variant, BBR, has been verified to significantly improve packet loss resistance when compared to traditional TCP variants on wired networks. In this paper, we evaluate multiple TCP variants on dynamic UAV networks, taking into account wireless dynamics caused by factors such as mobility, malicious attacks, and traffic from other legitimate users. Our results demonstrate that BBR does not always perform better than other TCP variants in a wireless environment, as opposed to wired networks. Depending on the cause of wireless environment dynamics, other TCP variants may work more effectively. Our findings suggest that no single TCP variant consistently outperforms others in UAV networks. Therefore, when selecting a TCP variant, careful consideration of the different UAV missions is necessary.

This paper proposes Advanced Fast Recovery OLSR (AFR-OLSR) for Unmanned Aerial Vehicles (UAVs) with sudden link outages, and implements a multipath version of this protocol. AFR-OLSR can maintain high packet delivery ratio and hardly bring extra network delay in the scenario of nodes suddenly offline or moving at high speed in UAV swarm. We improve the route calculation rule by defining a new link state and using penalty function to reduce the priority of selecting the link state. We use a constant bit rate (CBR) application running on selected nodes to simulate traffic in the network and measure the performance of data transmission. Experimental results show that the proposed protocol has a significant performance improvement.

Unmanned Aerial Vehicles (UAVs), now often deployed on battlefields, use wireless networks to communicate with each other. Such wireless communication, however, may become unreliable under the jamming from opponents, and existing UAV routing protocols perform poorly when dealing with the jamming. In this paper, we propose to use the spectrum jamming prediction data from the radio environment map (REM) to update the network topology. The key is to model the network as a weighted graph where the weights of the edges between two neighboring nodes are functions of the location of the jammer. We then update the routing paths accordingly in real-time. The protocol can be incorporated with existing table-driven protocols. We implement the protocol in a commercial network simulator. Simulations show that our routing protocol improves the packet delivery ratio and throughput of existing table-driven routing protocols.

Controller Area Networks (CANs), the most widely used protocols for in-vehicle networks, are vulnerable to various attacks due to the lack of security countermeasures by design. CAN messages are broadcast without source/destination labeling and lack built-in encryption or authentication mechanisms, thus suffering many attacks. To address this problem, we propose a lightweight CAN message obfuscation technique called ShuffleCAN. Motivated by the idea of moving target defense (MTD), ShuffleCAN is designed with a combined shuffling scheme based on the hash chain and combinatorial coding techniques to achieve both ID anonymization and payload shuffling. With ShuffleCAN, selected or all transmitter and receiver pairs can communicate in a private dialect over the standard CAN protocol, so the eavesdropper cannot understand the meaning of each message or inject a valid fake message. We implemented a prototype and evaluated ShuffleCAN on Toyota’s testbed PASTA. The experimental results show that ShuffleCAN outperforms state-of-the-art CAN protection schemes.

To control the rapid spread of COVID-19, we consider deploying a set of Unmanned Aerial Vehicles (UAVs) to form a quarantine barrier such that anyone crossing the barrier can be detected. We use a charging pile to recharge UAVs. The problem is scheduling UAVs to cover the barrier, and, for any scheduling strategy, estimating the minimum number of UAVs needed to cover the barrier forever. We propose breaking the barrier into subsegments so that each subsegment can be monitored by a single UAV. We then analyze two scheduling strategies, where the first one is simple to implement and the second one requires fewer UAVs. The first strategy divides UAVs into groups with each group covering a subsegment. For this strategy, we derive a closed-form formula for the minimum number of UAVs. In the case of insufficient UAVs, we give a recursive function to compute the exact coverage time and give a dynamic-programming algorithm to allocate UAVs to subsegments to maximize the overall coverage time. The second strategy schedules all UAVs dynamically. We prove a lower and an upper bound on the minimum number of UAVs. We implement a prototype system to verify the proposed coverage model and perform simulations to investigate the performance.

When UAVs are sent out for investigation such as battlefield reconnaissance, data from different UAVs should be transmitted to a central station, forming convergecast communication traffic. When infrastructure support is not available, data travels along a multi-hop routing path to the destination, and a routing protocol is needed to find these paths. In this work, we evaluate one commonly used protocol, BATMAN-adv, on commercially available Wi-Fi chipsets in embedded systems. We find that BATMAN-adv can form the desired routing paths, but the efficiency can be improved. In particular, this protocol does not consider traffic from other sources, and may lead to crowded paths. In addition, TCP works mostly well on the found routing paths, and its performance is comparable to UDP, but its built-in resource allocation mechanism may not meet an application's need. Consequently, both routing protocols and transport layer protocol should be revised to better suit convergecast applications.

To estimate the distance between a user and the target object for personal interest or for subsequent actions, the commonly used method is to search the target in the map application. However this is limited by GPS signal status under different environments and incomplete information on the map application of smartphones. This paper introduces a ranging method, CACam, which utilizes consecutive angle measurement based on camera of smartphone. Geometric model and ranging process are proposed to calculate the distance. When the user aligns the target from different position points, we record readings from the gyroscope sensor during every rotation in the procedure. The camera is used for aligning the target to build geometric model. Vector mapping of angular readings and data processing of intermediate points are used to get more accurate angles, which is suitable for the situation that the smartphone could not be strictly rotated in perpendicular to the plane of the gravity. The effectiveness of our ranging method is verified through experiments in outdoor environments.

When a UAV broadcasts its location periodically during flight, a target will observe the strongest signal when the UAV is at the closest location; thus, the target can infer its location based on the observed signals and the UAV’s trajectory. We consider how to design trajectories for UAVs such that all targets can locate themselves, and the maximum length of trajectories is minimized. To make the problem tractable, we impose constraints on the set of possible trajectories such that they only contain the edges of small squares. We propose an integer-linear-programming-based solution, which runs in exponential time, and two polynomial-time constant-factor approximation algorithms. We implement a prototype system to verify the feasibility of the localization method. Simulations show that our approach outperforms the existing ones in terms of flight length and localization error.

In case of energy depletion at some nodes, a sensor network may become disconnected, and data from live nodes may not be sent to the sink. This problem can be solved by a UAV acting as a mobile data collector. However, the traditional approach is to treat live sensor nodes as independent data sources. In this paper, we consider a cooperative approach where live sensors form sub-networks, instead of acting indepen-dently. Sensors within a subnetwork can send data to each other. A UAV only needs to visit subnetworks, instead of individual sensor nodes, to collect data. We formulate the problem and propose an iterative optimization algorithm to find the shortest data collection trajectory. Given any trajectory, our algorithm iteratively merges nodes within the same subnetwork and adjusts hovering locations to minimize trajectory length. Simulations show that, compared with the traditional TSP formulation, our approach can significantly reduces the length of the trajectory.

This paper presents ChirpMu, a system that encodes information into chirp symbols and embeds the symbols with music. Users enjoy music without realizing the existence of chirp sounds, while their smartphones can decode the information. ChirpMu can be used to broadcast information such as Wi-Fi secrets or coupons in shopping malls. It features novel chirp symbol design that can combat sound attenuation and environment noise. In addition, ChirpMu properly adjusts the portion of chirp symbols with music, so that the chirp symbols cannot be heard by users but can be decoded by smartphones with low error rate. Various real-world experiments show that ChirpMu can achieve low bit error rate.

In a minimum load spanning tree (MLST) problem, we are given an undirected graph and nondecreasing load functions for nodes defined on nodes’ degrees in a spanning tree, and the objective is to find a spanning tree that minimizes the maximum load among all nodes. We propose the first [Formula: see text] time exact algorithm for the MLST problem, where [Formula: see text] is the number of nodes and [Formula: see text] ignores polynomial factor. The algorithm is obtained by repeatedly querying whether a candidate objective value is feasible, where each query can be formulated as a bounded degree spanning tree problem (BDST). We propose a novel solution to BDST by extending an inclusion-exclusion based algorithm. To further enhance the time efficiency of the previous algorithm, we then propose a faster algorithm by generalizing the concept of branching walks. In addition, for the purpose of comparison, we give the first mixed integer linear programming formulation for MLST. In numerical analysis, we consider various load functions on a randomly generated network. The results verify the effectiveness of the proposed algorithms. Summary of Contribution: Minimum load spanning tree (MLST) plays an important role in various applications such as wireless sensor networks (WSNs). In many applications of WSNs, we often need to collect data from all sensors to some specified sink. In this paper, we propose the first exact algorithms for the MLST problem. Besides having theoretical guarantees, our algorithms have extraordinarily good performance in practice. We believe that our results make significant contributions to the field of graph theory, internet of things, and WSNs.

In this paper, we consider the maximum lifetime data gathering tree (MLDT) problem in sensor networks. A data gathering tree is a spanning tree rooted at a specified sink so that every node can send its messages to the sink along the tree. The lifetime of a tree is defined as the minimum lifetime among nodes where each node’s lifetime is determined by its initial energy and transmission load. The MLDT problem is NP-hard, and the state-of-the-art solution formulates a decision version of the problem as an integer linear program (ILP) and then solves it by conducting binary search over all possible lifetimes. In this paper, we first give an ILP for the optimization problem rather than its decision version, and then show that using ILP solvers to solve these programs could be highly inefficient. We then propose a branch-and-bound algorithm that incorporates two novel features. First, the bounding method takes into account integer flows, and contains a new set of constraints. Second, a special set of edges are deleted to reduce the number of subproblems generated by the branching process. Numerical simulations on randomly generated networks show that the proposed algorithm outperforms existing algorithms in terms of the number of solved problem instances in a fixed amount of time. Summary of Contribution: We study the maximum lifetime data gathering tree (MLDT) problem in the context of wireless sensor network. MLDT is a fundamental problem in both computer science and operations research. Since sensor nodes are often resource limited, the data gathering tree must be carefully constructed to prolong the network lifetime. In this paper, we first give an integer linear program for the optimization problem rather than its decision version, and then show that using ILP solvers to solve these programs could be highly inefficient. We then propose a branch and bound algorithm that incorporates two novel features.

Area coverage is one of the most common and important tasks for flying ad hoc networks (FANETs). The increasingly large scale of FANETs brings challenges in communication and coverage. Clustering is an effective technique for networking and management for large-scale ad hoc networks. Meanwhile, some applications, i.e., face recognition, need to perform intensive computation after unmanned aerial vehicles (UAVs) perform area coverage. Due to long response delay in transferring data to the cloud, it becomes a trend to use mobile-edge computing (MEC) for processing data in FANETs, which selects the node of rich computing resources, i.e., cluster head (CH), as MEC server, thus the delay performance of the edge node to the server is particularly critical. However, there is a conflict between area coverage efficiency and delay performance. Area coverage expects UAVs to spread as widely as possible, which may lead to a longer delay. In this article, we consider maximizing coverage efficiency under delay constraints. We define the coverage efficiency and propose an iterative coverage-efficient clustering algorithm (CECA) by applying penalty and block coordinate descent methods. Specifically, the CHs, positions and transmit powers are alternately optimized in each iteration. In addition, CECA can adjust delay constraints according to task requirements. Extensive simulation results show that our proposed approach is superior to other approaches in terms of coverage efficiency and delay.

We consider barrier coverage applications where a set of UAVs are deployed to monitor whether intruders pass through a line, i.e., the barrier. Due to limited energy supply of UAVs, a charging pile is used to recharge UAVs. The problem is to place UAVs on top of the barrier and schedule them to the charging pile such that the barrier is seamlessly covered and the total number of UAVs is minimized. We decompose the problem into subproblems by dividing the barrier into disjoint subsegments and covering each subsegment independently. We prove a theoretical lower bound on the minimum number of UAVs required to cover the barrier forever. We then propose two scheduling strategies. In the first strategy, only fully recharged backup UAVs will be scheduled to take over UAVs running out of energy. If there are enough UAVs, this strategy can cover the barrier forever. The second strategy is proposed to deal with the situation that the number of UAVs is insufficient. Under the strategy, if no backup UAV is fully recharged, the one with the most battery energy will be selected to take over the monitoring task. When the number of UAVs is insufficient, the barrier can still be covered for a long time. We analytically derive the number of UAVs required by the first strategy, and the monitoring duration of the second strategy in case of insufficient UAVs. Simulations verify the effectiveness of the proposed solutions.

In this paper, we consider a scenario where an unmanned aerial vehicle (UAV) collects data from a set of nodes placed on a two-dimensional (2-D) plane. The UAV flies along a given line to collect data. To prevent transmission collisions, only one node is allowed to transmit data to the UAV at any time, and the number of nodes that can transmit data to the UAV cannot exceed a specified number to avoid frequent switches. The problem is to select a subset of nodes and schedule their transmission time to maximize the UAV's throughput. After formulating the problem, we find that it is difficult to solve due to mixture of real variables and integer variables. We then propose to decompose the problem into subproblems, and give a polynomial time algorithm to solve each subproblem to optimality. We then get an exact algorithm by solving all subproblems. Unfortunately, due to an exponential number of subproblems, the overall running time is exponential with respect to the input size. We then propose two polynomial-time suboptimal algorithms to solve the problem, both of which explore a polynomial number of subproblems. Simulations show that the suboptimal algorithms perform comparably with the exponential-time exact algorithm, while the running time is much smaller.

We consider using UAVs to provide location service to ground targets. UAVs fly over the target area and broadcast their locations periodically via wireless signals. When a UAV flies along a straight line, a target will observe the strongest signal when the UAV is at the closest location, based on which it can infer its location. The problem is to minimize the flight length subject to the constraint that the transmission range of a UAV is limited and all targets in the area should be located. We formulate the problem and give an optimal flight path to cover a square with side length no greater than a certain value. In the general case when the given area cannot be covered by the square, we propose to divide UAVs into two groups, whose flight paths are either parallel or orthogonal. We conduct simulations to compare our approach with existing approaches. Results verify the superiority of our approach in terms of flight length and localization error.

Due to the flexibility and affordability, multi-target positioning based on cooperation of Unmanned Aerial Vehicles (UAVs) becomes attractive in recent years. Trilateration is popular and easy to implement, but still faces challenges in multi-UAV scenario. First, multiple distance measurements from a single UAV on same targets will lead to large accumulated errors. Second, the time interval between successive distance measurements on the same target cannot be long due to the mobility of the target. Finally, UAVs have limited onboard energy which constrains the flight duration and the mission will fail when some UAVs reach the limitation. In this paper, to complete multi-target positioning mission, we aim at minimizing the maximum energy consumption among all UAVs, which can be decomposed into two subproblems after dividing all UAVs into groups of three. Then we propose a two-stage heuristic algorithm, in which we first use adjusted Genetic Algorithm (GA) to plan the trajectories of all groups with bounded maximum energy consumption and then we pursue to minimize the maximum energy consumption among UAVs in a group. Compared to two other algorithms, extensive simulations show that the proposed algorithm can reduce up to 24.9% and 11.8% in terms of maximum and average energy consumption, respectively.

Shopping malls, restaurants, and book shops usually offer free WiFi to customers, but they cannot afford non-customers (i.e., WiFi free riders) consuming their limited bandwidth. To provide WiFi information (i.e., SSID and password) secretly to customers, they usually display it in places where only customers can see, and update it regularly. The drawbacks are that customers need to enter the password manually and sometimes they do not know the location of the information. In this paper, we propose an alternative solution. In our system, the WiFi providers set up a speaker to continuously broadcast acoustic signals encoding WiFi information, and the customers use their smartphones to receive and decode the signals. Because acoustic signals attenuate rapidly through walls, only customers in the venue can acquire WiFi information. We implement a prototype system and show the feasibility of our approach. Experiments indicate that in our system, a user can connect successfully to the WiFi within several seconds.

Network failures are common in wide area networks (WANs). Failure recovery in a software-defined WAN takes minutes or longer, as the controller needs to calculate a new traffic engineering solution and update the forwarding rules across all switches. This severely degrades application performance. Existing reactive and proactive approaches inevitably lead to transient congestion or bandwidth underutilization and impair the efficiency of running the expensive WANs. We present Sentinel, a novel failure recovery system for traffic engineering in software-defined WANs. Sentinel pre-computes and installs backup tunnels to accelerate failure recovery. When a link fails, switches locally redirect traffic to backup tunnels and recover immediately in the data plane, thus substantially reducing the transient congestion compared to reactive rescaling. On the other hand, Sentinel completely avoids the bandwidth headroom required by existing proactive approaches. Extensive experiments on Mininet and numerical simulations show that similar to state-of-the-art FFC, Sentinel reduces congestion by 45% compared with rescaling, and its algorithm runs much faster than FFC. Sentinel only introduces a small number of additional forwarding rules and can be readily implemented on today’s Openflow switches.

In some large-scale RFID systems where tags carry values, the extrema are critical statistics. We consider estimating the extrema, i.e., estimating the maximum and minimum values simultaneously. A straightforward approach is to perform binary search on the possible values, each time requesting tags with values in a certain range to respond. We show that this approach is suboptimal due to the interframe overhead between two frames in practical RFID systems. We propose a class of protocols to find the minimum value or maximum value separately, and show how to select the best protocol according to the hardware parameters of RFID systems. We then revise the protocol to estimate the minimum and maximum values simultaneously, and give the optimal parameters. Extensive simulations show that our protocol gives the smallest estimation error within any allocated time.

Maximizing the lifetime of wireless sensor networks is NP‐hard, and existing exact algorithms run in exponential time. These algorithms implicitly use only one CPU core. In this work, we propose to use multiple CPU cores to speed up the computation. The key is to decompose the problem into independent subproblems and then solve them on different cores simultaneously. We propose three decomposition approaches. Two of them are based on the notion that a tree does not contain cycles, and the third is based on the notion that, in any tree, a node has at most one parent. Simulations on an 8‐core desktop computer show that our approach can speed up existing algorithms significantly.

In wireless sensor networks, maximizing the lifetime of a data gathering tree is known to be NP-hard, so various (exponential-time) exact algorithms are designed to find the best data gathering tree. The state-of-the-art exact algorithm recursively performs graph decomposition to reduce search space. However, it essentially enumerates all possibilities in adjacent graph decompositions, and cannot handle moderately large sensor networks. In this paper, we propose an exact algorithm using integer linear programming. The challenge is that some constraints are not linear in the optimization problem. To address this challenge, instead of the optimization problem, we formulate the decision problem, and solve each decision problem by integer linear programming. The optimal value is then found by binary search over all possible lifetimes. To reduce the running time, we preprocess the graph by decomposing it into bi- connected subnetworks, and propose various rules to reduce the number of candidate lifetimes. Numerical results on simulated networks show that, within two hours, our algorithm can solve more problem instances than previous algorithms.

Securing a wireless channel between any two vehicles is a crucial component of vehicular networks security. This can be done by using a secret key to encrypt the messages. We propose a scheme to allow two cars to extract a shared secret from RSSI (Received Signal Strength Indicator) values in such a way that nearby cars cannot obtain the same key. The key is information-theoretically secure, i.e., it is secure against an adversary with unlimited computing power. Although there are existing solutions of key extraction in the indoor or low-speed environments, the unique channel conditions make them inapplicable to vehicular environments. Our scheme effectively and efficiently handles the high noise and mismatch features of the measured samples so that it can be executed in the noisy vehicular environment. We also propose an online parameter learning mechanism to adapt to different channel conditions. Extensive real-world experiments are conducted to validate our solution.

We present Sentinel, a novel failure recovery system for traffic engineering that pre-computes and installs backup tunnels to improve the robustness of software defined wide area networks (WANs). When a link fails, switches locally redirect traffic to backup tunnels and recover immediately in the data plane, thus substantially reducing the transient congestion compared to reactive rescaling. On the other hand Sentinel completely avoids the bandwidth headroom required by existing proactive approaches like FFC, and improves efficiency of operating the expensive WAN. We make several technical contributions in designing Sentinel. We formulate traffic engineering with backup tunnels (TE-BT) as optimization programs. We propose an approximation algorithm to efficiently solve the problem. We further present a concrete design and implementation of the system based on Openflow group tables for backup tunnels. Extensive experiments on Mininet and numerical simulations show that similar to FFC, Sentinel reduces congestion by 45% compared with rescaling, and its algorithm runs much faster than FFC. Sentinel only introduces a small number of additional forwarding rules and can be readily implemented on today's Openflow switches.

A traditional approach to solving the large delay problem of campus networks is to upgrade the link connecting the gateway to the Internet. Inspired by the emerging content-centric network (CCN) and software defined network (SDN) architecture, we propose an alternative solution where the campus network uses a few CCN routers with caching ability, so that duplicate requests for the same content can be satisfied locally without traffic from the Internet. In our solution, we formulate the problem of deciding the cached content at each router to minimize the total delay of all requests. We prove that the problem is NP-hard, and no polynomial time algorithm can provide a constant approximation ratio, unless P=NP. We then propose an exponential-time exact algorithm and three polynomial-time heuristic algorithms. Numerical results show that our solution can reduce network delay significantly, compared to existing cache decision algorithms.

One ultimate goal of wireless sensor networks is to collect the sensed data from a set of sensors and transmit them to some sink node via a data gathering tree. In this work, we are interested in data aggregation, where the sink node wants to know the value for a certain function of all sensed data, such as minimum, maximum, average, and summation. Given a data aggregation tree, sensors receive messages from children periodically, merge them with its own packet, and send the new packet to its parent. The problem of finding an aggregation tree with the maximum lifetime has been proved to be NP-hard and can be generalized to finding a spanning tree with the minimum maximum vertex load, where the load of a vertex is a nondecreasing function of its degree in the tree. Although there is a rich body of research in those problems, they either fail to meet a theoretical bound or need high running time. In this paper, we develop a novel algorithm with provable performance bounds for the generalized problem. We show that the running time of our algorithm is in the order of O(mnα(m, n)), where m is the number of edges, n is the number of sensors, and α is the inverse Ackerman function. Though our work is motivated by applications in sensor networks, the proposed algorithm is general enough to handle a wide range of degree-oriented spanning tree problems, including bounded degree spanning tree problem and minimum degree spanning tree problem. When applied to these problems, it incurs a lower computational cost in comparison to existing methods. Simulation results validate our theoretical analysis.

Network coding has the potential to provide powerful support to transmit real-time traffic in wireless network. In this paper, we utilize pairwise coding to schedule the flows which have heterogeneous delay constraints and weights. Our goal is to maximize the weighted sum of scheduled packets that satisfy the delay constraints. We formulate the problem as an integer linear programming problem, and propose two algorithms to solve it. The first algorithm drops the integral constraints and rounds the fractional solutions in such a way that the rounded solution is also optimal. Inspired by the first algorithm and for better running time, we propose the second algorithm based on a minimum cost flow formulation. The formulation is proved to be equivalent to the original integer linear programming formulation. Simulations are conducted to show the effectiveness of our approach over two greedy algorithms.

The soaring adoption of location-based social networks (LBSNs) makes it possible to analyze human socio-spatial behaviors based on large-scale realistic data, which is important to both the research community and the design of new location-based social applications. However, performing direct measurements on LBSNs is impractical, because of the security mechanisms of existing LBSNs, and high time and resource costs. The problem is exacerbated by the scarcity of available LBSN datasets, which is mainly due to the privacy concerns and the hardness of distributing large-volume data. As a result, only a very few number of LBSN datasets are publicly released. In this paper, we extract and study the universal statistical features of three LBSN datasets, and propose LBSNSim, a trace-driven model for generating synthetic LBSN datasets capturing the properties of the original datasets. Our evaluation shows that LBSNSim provides an accurate representation of target LBSNs.

Cognitive radio (CR) networks have an ample but dynamic amount of spectrum for communications. Communication rendezvous in CR networks is the process of establishing a control channel between radios before they can communicate. Designing a communication rendezvous protocol that can take advantage of all the available spectrum at the same time is of great importance, because it alleviates load on control channels, and thus further reduces probability of collisions. In this paper, we present ETCH, efficient channel-hopping-based MAC-layer protocols for communication rendezvous in CR networks. Compared to the existing solutions, ETCH fully exploits spectrum diversity in communication rendezvous by allowing all the rendezvous channels to be utilized at the same time. We propose two protocols, SYNC-ETCH, which is a synchronous protocol assuming CR nodes can synchronize their channel hopping processes, and ASYNC-ETCH, which is an asynchronous protocol not relying on global clock synchronization. Our theoretical analysis and ns-2-based evaluation show that ETCH achieves better performances of time-to-rendezvous and throughput than the existing work.

In wireless sensor networks, the spanning tree is usually used as a routing structure to collect data. In some situations, nodes do in-network aggregation to reduce transmissions, save energy, and maximize network lifetime. Because of the restricted energy of sensor nodes, how to build an aggregation tree of maximum lifetime is an important issue. It has been proved to be NP-complete in previous works. As shortest path spanning trees intuitively have short delay, it is imperative to find an energy-efficient shortest path tree for time-critical applications. In this article, we first study the problem of building maximum lifetime shortest path aggregation trees in wireless sensor networks. We show that when restricted to shortest path trees, building maximum lifetime aggregation trees can be solved in polynomial time. We present a centralized algorithm and design a distributed protocol for building such trees. Simulation results show that our approaches greatly improve the lifetime of the network and are very effective compared to other solutions. We extend our discussion to networks without aggregation and present interesting results.

This paper presents APT, a localization system for outdoor pedestrians with smartphones. APT performs better than the built-in GPS module of the smartphone in terms of accuracy. This is achieved by introducing a robust dead reckoning algorithm and an error-tolerant algorithm for map matching. When the user is walking with the smartphone, the dead reckoning algorithm monitors steps and walking direction in real time. It then reports new steps and turns to the map-matching algorithm. Based on updated information, this algorithm adjusts the user's location on a map in an error-tolerant manner. If location ambiguity among several routes occurs after adjustments, the GPS module is queried to help eliminate this ambiguity. Evaluations in practice show that the error of our system is less than 1/2 that of GPS.

A crucial component of vehicular network security is to establish a secure wireless channel between any two vehicles. In this paper, we propose a scheme to allow two cars to extract a secret key from RSSI (Received Signal Strength Indicator) values in such a way that nearby cars cannot obtain the same secret. Our solution can be executed in noisy, outdoor vehicular environments. We also propose an online parameter learning mechanism to adapt to different channel conditions. We conduct extensive realworld experiments to validate our solution.

As the first step of the communication procedure in 802.11, an unwise selection of the access point (AP) hurts one client's throughput. This performance downgrade is usually hard to be offset by other methods, such as efficient rate adaptations. In this paper, we study this AP selection problem in a decentralized manner, with the objective of maximizing the minimum throughput among all clients. We reveal through theoretical analysis that the selfish strategy, which commonly applies in decentralized systems, cannot effectively achieve this objective. Accordingly, we propose an online AP association strategy that not only achieves a minimum throughput (among all clients) that is provably close to the optimum, but also works effectively in practice with reasonable computation and transmission overhead. The association protocol applying this strategy is implemented on the commercial hardware and compatible with legacy APs without any modification. We demonstrate its feasibility and performance through real experiments and intensive simulations.

We study the time duration of neighbor discovery in peer-to-peer wireless networks with multi-channel multi-packet reception capability. Radios with this capability, at any time slot, can either transmit messages in one channel or receive messages from all channels. This capability is provided by emerging CDMA/OFDMA techniques. Neighbor discovery in this scenario is different from other multi-packet reception scenarios like MIMO since collision can still happen in single channel. To discover neighbors with such capability in single-hop networks, we prove that the expected running time of all randomized algorithms is Θ(n/k) where n is the number of nodes and k is the number of channels. We provide a Las Vegas algorithm that finds all neighbors with variable running time. We prove that its running time is Θ(n/k ln n) with high probability. We also give a Monte Carlo algorithm that terminates in Θ(n/k) time. We show that it finds all neighbors with high probability. Both algorithms are validated by simulation.

In many applications of wireless sensor networks, a sensor node senses the environment to get data and delivers them to the sink via a single hop or multi-hop path. Many systems use a tree rooted at the sink as the underlying routing structure. Since the sensor node is energy constrained, how to construct a good tree to prolong the lifetime of the network is an important problem. We consider this problem under the scenario where nodes have different initial energy, and they can do in-network aggregation. In previous works, it has been proved that finding a maximum lifetime tree from all feasible spanning trees is NP-complete. Since delay is also an important element in time-critical applications, and shortest path trees intuitively have short delay, it is imperative to find a shortest path tree with long lifetime. This paper studies the problem of maximizing the lifetime of data aggregation trees, which are limited to shortest path trees. We find that when it is restricted to shortest path trees, the original problem is in P. We transform the problem into a general version of semi-matching problem, and show that the problem can be solved by min-cost max-flow approach in polynomial time. Also we design a distributed solution. Simulation results show that our approach greatly improves the lifetime of the network and is more competitive when it is applied in a dense network.

Sensors can be deployed along a road or bridge to form a one-dimensional wireless sensor network where nodes have a spatial ordering. This spatial characteristic indicates relative locations for nodes and facilitates functions like object tracking and monitoring in the network. We target at deriving this ordering without attaching extra hardware to sensor nodes. In this work, we propose to exploit RSSI (received signal strength indicator) to generate the spatial ordering. The approach is based on our observation: the largest RSSI value indicates the shortest distance. Evaluations on two datasets show that our algorithm generates the spatial ordering at high success rate.