One of the most important topics in Human-Centered Computing (HCC) is to recognise human's activities. In this paper, the technology of wireless-based activity recognition is introduced. By using wireless signals, one can achieve Non-Line-Of-Sight (NLOS) recognition without carrying any devices. Also, it is easy to deploy a wireless-based recognition system due to the ubiquity of wireless communication systems. The basic idea is to detect different characteristics of signal propagation that correspond to the distinct human behaviors. As a result, action recognition is performed by analyzing the distinguishable features of signal propagation. This paper introduces the basic principles and applications of wireless-based activity recognition, and discusses the challenges and related performance metrics. Finally, open problems are discussed to point out the future research trends.

Coordination among users is inevitable in wireless communication for efficient medium access. Even though the data rate of individual user increases significantly, the performance of wireless network does not grow up accordingly due to the high MAC coordination overhead. In this paper, we present VFA, namely virtual frame aggregation, to achieve high coordination efficiency by amortizing the overhead over multiple transmissions. VFA provides a novel way to construct a winner cluster and allow the winners to transmit without interruption. Specifically, in a multicarrier network, every contending node chooses a subcarrier and the nodes are ordered by the index of the chosen subcarrier. When there are some subcarriers chosen by two or more nodes, an additional slot is exploited to reorder the collided nodes. Finally, all ordered nodes form a cluster and the transmissions are issued sequentially and uninterruptedly. Simulation results show that usually two slots are enough to construct a sufficiently large winner cluster. Moreover, VFA achieves a notable throughput gain over IEEE 802.11 as high as 120% with better fairness under various scenarios.

Coordination among users is an indispensable part in wireless networks for efficient medium access. Alone with the rapid increase of transmission rate, however, coordination time becomes insufferable. We present AFD, namely asymmetric full duplex, to achieve high coordination efficiency at nearly zero overhead. In AFD, channel contention is performed simultaneously with data transmission. We propose a 3D pipeline contention scheme where the contention process is divided into several parallel stages and executed in a pipelined manner in a 3D domain specified by time, frequency and spatial antenna. To mitigate the interference between the data packet and the contention signal, we adopt a singleton PN sequence as a contention pilot. AFD provides a novel network-scale full duplex capability. The performance is evaluated by both simulations and measurements in a testbed. AFD outperforms IEEE 802.11 significantly, i.e., the Jain's fairness index is around 0.95 with a throughput gain up to 120%.

Successive interference cancellation (SIC) is an effective way of multipacket reception to combat interference in wireless networks. We focus on link scheduling in wireless networks with SIC, and propose a layered protocol model and a layered physical model to characterize the impact of SIC. In both the interference models, we show that several existing scheduling schemes achieve the same order of approximation ratios, independent of whether or not SIC is available. Moreover, the capacity order in a network with SIC is the same as that without SIC. We then examine the impact of SIC from first principles. In both chain and cell topologies, SIC does improve the throughput with a gain between 20 and 100 percent. However, unless SIC is properly characterized, any scheduling scheme cannot effectively utilize the new transmission opportunities. The results indicate the challenge of designing an SIC-aware scheduling scheme, and suggest that the approximation ratio is insufficient to measure the scheduling performance when SIC is available.

Successive interference cancellation (SIC) is an effective way of multipacket reception to combat interference. As conventional CSMA (Carrier Sense Multiple Access) is designed for single packet reception, it is unclear whether or not CSMA performs well to exploit the SIC capability. In this paper, we analyze the performance of a simple CSMA protocol in a network with SIC. For a given link, we derive the residing areas of an interfering node when simultaneous transmission is allowed and when the interference is harmful, respectively. We show that, though SIC provides many new transmission opportunities, CSMA cannot effectively exploit them. There is a fundamental tradeoff in a CSMA protocol between exploiting the transmission opportunities from SIC and capturing the harmful interference. In many cases, when CSMA achieves its best performance, almost all new transmission opportunities are not exploited. It is therefore very necessary to design a new distributed access protocol in wireless networks with SIC.

Broadcast is an essential and widely used operation in multihop wireless networks. Minimum latency broadcast scheduling (MLBS) aims to find a collision-free scheduling for broadcast with the minimum latency. Previous work on MLBS mostly assumes that nodes are always active, and, thus, is not suitable for duty-cycled scenarios. In this paper, we investigate the MLBS problem in duty cycled multihop wireless networks (MLBSDC problem). We prove both the one-to-all and the all-to-all MLBSDC problems to be NP hard. We propose a novel approximation algorithm called OTAB for the one-to-all MLBSDC problem, and two approximation algorithms called UTB and UNB for the all-to-all MLBSDC problem under the unit-size and the unbounded-size message models, respectively. The approximation ratios of the OTAB, UTB, and UNB algorithms are at most 17|T|, 17|T| + 20, and (Δ + 22)|T|, respectively, where |T| denotes the number of time slots in a scheduling period, and Δ denotes the maximum node degree of the network. The overhead of our algorithms is at most constant times as large as the minimum overhead in terms of the total number of transmissions. We also devise a method called Prune to further reduce the overhead of our algorithms. Extensive simulations are conducted to evaluate the performance of our algorithms.

We propose a new jamming attack model from spatial perspective: given k jammers, how does the attacker minimize the pair-wise connectivity among the nodes in Wireless Sensor Network (WSN)? We call this problem k-Jammer Deployment Problem (k-JDP). First, we prove that the decision version of k-JDP is NP-complete even in the ideal situation where the attacker has full knowledge of topology information. Second, we propose a mathematical formulation based on Integer Programming (IP) model which yields an optimal solution. Third, we present a heuristic algorithm HAJDP, and compare it with the IP model. Numerical results show that HAJDP is computationally efficient.

Successive interference cancellation (SIC) is an effective way of multipacket reception to combat interference. We consider the problem of maximizing the number of successful transmissions based on the physical model in wireless networks with SIC at the physical layer. We propose weighted simultaneity graph to characterize the sequential detection nature of SIC and the accumulative effect of multiple interfering signals. A context-aware metric, transmission price, is defined to measure the interference of a link set. As maximizing the number of supported links is NP-hard, a greedy scheme is proposed to efficiently construct a near-optimal maximal feasible set of links. We show that the approximation performance is bounded by the transmission price of the constructed link set. The performance of the proposed scheme is further verified by simulation.

We consider the greedy scheduling based on the physical model in wireless networks with successive interference cancellation (SIC). There are two major stages in a scheduling scheme, link selection (to decide which link is scheduled next) and time slot selection (to deciding which slot is allocated to a given link). Most available schemes take a first-fit policy in the latter and strive to achieve good performance by careful selection of link ordering with respect to interference. Due to the accumulation effect and sequential detection nature of SIC, however, it is difficult to evaluate the interference of a link. As a result, many existing scheduling schemes become less efficient. In this paper, we take a new look on the problem and focus to the time slot selection stage. We define tolerance margin to measure the saturation of a link set and present two heuristic policies: one is to schedule a link to a slot such that the resulting set of links has a maximum tolerance margin; the other is to choose a slot such that the increase of tolerance margin is minimum. Simulation results show that the performance of the proposed schemes is better than the first-fit policy and is close to the optimal solution.

Successive interference cancellation (SIC) is an effective way of multipacket reception (MPR) to combat interference in wireless networks. To understand the potential MPR advantages, we study link scheduling in an ad hoc network with SIC at the physical layer. The fact that the links detected sequentially by SIC are correlated at the receiver poses key technical challenges. We characterize the link dependence and propose simultaneity graph (SG) to capture the effect of SIC. Then interference number is defined to measure the interference of a link. We show that scheduling over SG is NP-hard and the maximum interference number bounds the performance of maximal greedy schemes. An independent set based greedy scheme is explored to efficiently construct a maximal feasible schedule. Moreover, with careful selection of link ordering, we present a scheduling scheme that improves the bound. The performance is evaluated by both simulations and measurements in testbed. The throughput gain is on average 40% and up to 120% over IEEE 802.11. The complexity of SG is comparable with that of conflict graph, especially when the network size is not large.

Jamming attacks can severely affect the performance of Wireless Sensor Networks (WSNs) due to their broadcast nature. The most reliable solution to reduce the impact of such attacks is to detect and localize the source of the attack. In this paper, we investigate the feasibility of localizing an omni-antenna jammer. We propose Catch the Jammer (CJ), an efficient jammer localization scheme whereby victim nodes at the border of the jammed region share their location information with their one-hop neighbor nodes which further collaborate to find the position of the jammer. This new localization technique first computes a convex hull for the set of victim nodes and further extracts the corresponding minimum covering circle. Simulation results show that CJ outperforms most of the existing localization algorithms depending on the variation of the jammer's transmission range and the position of the jammer.

Successive interference cancellation (SIC) is an effective way of multipacket reception to combat interference. We study link scheduling under SINR (Signal to Interference Noise Ratio) model in ad hoc networks with SIC at physical layer. The facts that interference is accumulated and the links decoded sequentially by SIC are correlated pose key technical challenges. We propose conflict set graph (CSG) to characterize the interference and define interference degree to measure the interference of a link. As scheduling over CSG is NP-hard, independent set based greedy scheme is explored to efficiently construct maximal feasible schedule. The performance is evaluated by simulations. As compared to the simple greedy method, the throughput gain is on average 30% and up to 60%.

Broadcast is an essential and widely-used operation in multi-hop wireless networks. Minimum latency broadcast scheduling (MLBS) aims to provide a collision-free scheduling for broadcast with the minimum latency. Previous work on MLBS mostly assumes that nodes are always active, and thus is not suitable for duty-cycle-aware scenarios. In this paper, we investigate the duty-cycle-aware minimum latency broadcast scheduling (DCA-MLBS) problem in multi-hop wireless networks. We prove both the one-to-all and the all-to-all DCA-MLBS problems to be NP-hard. We propose a novel approximation algorithm called OTAB for the one-to-all DCA-MLBS problem, and two approximation algorithms called UTB and UNB for the all-to-all DCA-MLBS problem under the unit-size and the unbounded-size message models respectively. The OTAB algorithm achieves a constant approximation ratio of 17|T|, where |T| denotes the number of time-slots in a scheduling period. The UTB and UNB algorithms achieve the approximation ratios of 17|T|+20 and (Δ+22)|T| respectively, where Δ denotes the maximum node degree of the network. Extensive simulations are conducted to evaluate the performance of our algorithms.

Successive interference cancellation (SIC) is an effective technique of multipacket reception to combat interference. As not all collision are resolvable, careful transmission coordination is required. We study link scheduling in wireless networks with SIC at the physical layer. A new model, simultaneity graph (SG), is proposed to characterize the link correlation introduced by SIC. Then two new scheduling schemes are presented: 1) a slot-oriented scheme which assigns a maximal feasible link set to a time slot and 2) a link-oriented scheme which assigns each link a sufficient number of slots. The performance is evaluated by simulations and the results demonstrate that the throughput gain is on average 50% and up to 110% over IEEE 802.11. The complexity of SG is only a bit higher than that of the available widely-used models (e.g., conflict graph).

BACKGROUND: In the field of RNA secondary structure prediction, the RNAalifold algorithm is one of the most popular methods using free energy minimization. However, general-purpose computers including parallel computers or multi-core computers exhibit parallel efficiency of no more than 50%. Field Programmable Gate-Array (FPGA) chips provide a new approach to accelerate RNAalifold by exploiting fine-grained custom design. RESULTS: RNAalifold shows complicated data dependences, in which the dependence distance is variable, and the dependence direction is also across two dimensions. We propose a systolic array structure including one master Processing Element (PE) and multiple slave PEs for fine grain hardware implementation on FPGA. We exploit data reuse schemes to reduce the need to load energy matrices from external memory. We also propose several methods to reduce energy table parameter size by 80%. CONCLUSION: To our knowledge, our implementation with 16 PEs is the only FPGA accelerator implementing the complete RNAalifold algorithm. The experimental results show a factor of 12.2 speedup over the RNAalifold (ViennaPackage - 1.6.5) software for a group of aligned RNA sequences with 2981-residue running on a Personal Computer (PC) platform with Pentium 4 2.6 GHz CPU.

In the field of RNA secondary structure prediction, the Zuker algorithm is one of the most popular methods using free energy minimization. However, general-purpose computers including parallel computers or multi-core computers exhibit parallel efficiency of no more than 50% on Zuker. FPGA chips provide a new approach to accelerate the Zuker algorithm by exploiting fine-grained custom design. Zuker shows complicated data dependences, in which the dependence distance is variable, and the dependence direction is also across two dimensions. We propose a systolic array structure including one master PE and multiple slave PEs for fine grain hardware implementation on FPGA. We exploit data reuse schemes to reduce the need to load energy matrices from external memory. We also propose several methods to reduce energy table parameter size by 85%. To our knowledge, our implementation with 16 PEs is the only FPGA accelerator implementing the complete Zuker algorithm. The experimental results show a factor of 14 speedup over the ViennaRNA-1.6.5 software for 2981-residue RNA sequence running on a PC platform with Pentium 4 2.6 GHz CPU.

One way to improve the throughput of a wireless ad hoc network at the media access (MAC) layer is to allow as much as possible concurrent transmissions among neighboring nodes. In this paper, we present a novel high-throughput MAC protocol, called Concurrent Transmission MAC(CTMAC), which supports concurrent transmission while allowing the network to have a simple design with a single channel, single transceiver, and single transmission power architecture. CTMAC inserts additional control gap between the transmission of control packets (RTS/CTS) and data packets (DATA/ACK), which allows a series of RTS/CTS exchanges to take place between the nodes in the vicinity of the transmitting or receiving node to schedule possible multiple, concurrent data transmissions. To safeguard the concurrent data transmission, collision avoidance information is included in the control packets and used by the neighboring nodes to determine whether they should begin their transmissions. Also, to isolate the possible interference between DATA packets and ACK packets, a new ACK sequence mechanism is proposed. Simulation results show that a significant gain in throughput can be obtained by the CTMAC protocol compared with the existing work including the IEEE 802.11 MAC protocol.

In the paper, we present a design of FPGA SAR processor with four 1D FFT processing elements, double internal RAM buffers and double external SDRAM modules. Without traditional corner turn phase, we propose a data layout scheme mapping one row of logical matrix into a rectangular window in physical banks of SDRAM in order to increase the practical I/O throughout between SDRAM modules and SAR processing elements. In addition, we theoretically analyses the optimal window size to minimize the total number of opening/closing pages when performing 2D FFT by balancing the number of handling physical pages between row accesses and column accesses. The experimental results show our window layout approach achieves 650 MB/s of effective bandwidth, reaching nearly 82% of peak bandwidth, with 58.1% increases compared to traditional Corner Turn approaches. The proposed SAR processor has been implemented in an FPGA test-bed, outperforming related works in both of computing speed and image scale.

Algorithms of Active Shape Model, as one of the most popular methods for recognizing non-rigid objects, require huge computation power for real time people tracking. After analyzing the parallel characteristics of the algorithm, we propose a deep pipelined structure for accelerating the Active Shape Model algorithm. The computing engine is organized into a deep pipeline network composing of multiple floating-point arithmetic units, including adders, multipliers, dividers and SQRT etc. In the optimization of the memory efficiency for loading random data in large images during the step of local search, we propose an on-chip buffer scheme to eliminate random accesses to off-chip memory. Experimental results show that our FPGA implementation achieves over 15 times of speedup compared with the software implementation in Pentium 4 computer.

Given the multi-rate option in most 802.11 standards, rate adaptation based on dynamic channel condition is crucial to the system performance. This paper presents an efficient rate adaptation mechanism at MAC layer, called ERA, to improve the transport layer throughput. Such scheme raises the transmission rate aggressively, e.g., upon only a few consecutive successful transmissions. In opposite, we reduce the transmission rate more cautiously only when the station encounters severe consecutive frame losses or relatively high loss ratio at MAC layer. ERA also attempts to protect the performance under steady condition without losing the ability to respond to the channel variation quickly. We evaluate ERA using NS-2 simulations and find that it performs better than or at least similarly with many other proposals in various scenarios. ERA is a sender-based method and requires minor modification at sender side only, thus completely standard-compliant and very easy to be implemented and deployed.