Traffic flow prediction remains a critical issue in intelligent transport systems. Despite significant efforts in traffic flow modeling, existing approaches exhibit several notable limitations: (i) Most models fail to capture traffic flow similarities over long distances and extended periods; (ii) They struggle to account for spatio-temporal heterogeneity induced by varying traffic flow patterns; (iii) Due to their static modeling approach, they struggle to effectively capture the intricate spatio-temporal entanglement. To address these challenges, we propose a traffic flow prediction framework based on self-supervised learning spatio-temporal entanglement transformer(SSL-STMFormer). This framework adopts a self-supervised learning paradigm, leveraging a transformer architecture that captures richer spatio-temporal information to better represent traffic flow patterns. Specifically, a temporal attention module and a spatial attention module are employed to capture the spatio-temporal dependencies of traffic dynamics, respectively, and spatio-temporal entanglement-aware methods are introduced to allow the model to perceive spatio-temporal entanglement and thus better modelling of real traffic environments. Furthermore, to achieve adaptive spatio-temporal self-supervised learning, adaptive data augmentation is applied to the input traffic flow data, and the traffic flow prediction task is enhanced with temporal heterogeneity module and spatial heterogeneity module. Extensive experimental evaluations conducted on six publicly available real-world transportation datasets demonstrate that our method achieves substantial improvements across these datasets.

Because of the ambiguous and subjective property of the facial expression, the label noise is widely existing in the FER dataset. For this problem, in the training phase, current methods often directly predict whether the label is noised or not, aiming to reduce the contribution of the noised data. However, we argue that this kind of method suffers from the low reliability of such noise data decision operation. It makes that some mistakenly abounded clean data are not utilized sufficiently and some mistakenly kept noised data disturbing the model learning. In this paper, we propose a more reliable noise-label suppression method called ReSup. First, instead of directly predicting noised or not, ReSup makes the noise data decision by modeling the distribution of noise and clean labels simultaneously according to the disagreement between the prediction and the target. Specifically, to achieve optimal distribution modeling, ReSup models the similarity distribution of all samples. To further enhance the reliability of our noise decision results, ReSup uses two networks to jointly achieve noise suppression. Specifically, ReSup utilize the property that two networks are less likely to make the same mistakes, making two networks swap decisions and tending to trust decisions with high agreement. Extensive experiments on popular datasets shows the effectiveness of ReSup.

Facial Expression Recognition (FER) has received considerable research attention owing to its poor robustness in real-world scenarios. This issue, defined as the uncertainty problem in FER, is often solved by recognizing the noise samples in FER datasets. Unlike noise samples with incorrect labels, ambiguous samples exhibit mixed emotions that align with multiple basic expressions. It makes them indistinguishable in training and harms model robustness. To address this issue, we propose an ambiguity-aware FER framework called Co-dance with Ambiguity (CoA). CoA combines an Emotion Extraction Module (EEM) and an Expression Description Module (EDM) to leverage ambiguity for better performance and robustness. Specifically, EEM employs a coupled-stream structure to extract both representative and detailed features through diverse-scale fusion and patch-attention sensing. EDM adjusts ground-truth labels of ambiguous samples by introducing label pairs derived from the top two highest predictions, describing the mixed-emotion nature. The pairs guide the model to align feature extraction with the inherent ambiguity of ambiguous samples during training. Extensive experiments on five in-the-wild FER datasets demonstrate the superiority of CoA over advanced methods. Moreover, introducing ambiguity-aware strategies enriches feature representations and significantly enhances robustness when faced with a high ratio of ambiguous samples in FER.

Addressing the challenge in Facial Expression Recognition (FER) of majority expressions like happiness and neutral overshadowing minority ones, we introduce K-positive Face Net (K-Face Net), a two-stage framework enhancing diverse expression recognition. In its representation learning stage, K-Face Net employs a novel K-positive loss to select K same-class samples as positive groups, reducing the distance of features between the anchor and the groups and achieving compact clustering. The subsequent classification stage utilizes Spatial Pooling across spatial and global dimensions, increasing inter-class feature distances for balanced recognition. Extensive experiments demonstrate that K-Face Net makes better performance in minority categories and achieves state-of-the-art on three popular datasets in both average and overall accuracy. K-Face Net provides a new perspective in enhancing the recognition of underrepresented facial expressions in real-world scenarios.

Recent research on facial expression recognition (FER) has achieved significant performance on FER datasets. However, in real-world recognition scenarios, performance is often compromised by occlusion, particularly after the COVID-19. To address this issue, we propose a novel framework named OCLIPER, an visual-language model designed to enhance occluded facial expression recognition. Specifically, Our approach consists of two parts: 1) Visual Part: We initially generated realistic occlusions commonly encountered in daily life, such as masks, glasses, and hands, by incorporating them into FER datasets. Subsequently, we introduce a similarity loss between original facial images and occluded facial images. This guides the image encoder to learn a robust facial representation insensitive to occlusion. 2) Text Part: Learnable prompts and the Occluded Facial Expression Descriptor (OFED) are utilized as inputs to the text encoder. Learnable prompts assist the model in understanding relevant context information for each expression. OFED comprises a series of text descriptions of facial expressions behind occlusion, generated by ChatGPT. Ultimately, the text part guides the image part in learning occlusion-resistant features. Experimental results on various databases demonstrate the superiority of our proposed method over state-of-the-art approaches.

Hand gesture recognition (HGR) is essential for human-machine interaction. Although the existing solutions achieve good performance in specific tasks, they still face challenges when users navigate through different application contexts, i.e., demanding multi-task ability to support newly arrived HGR tasks. In this paper, we propose the first IMU-vision based system hosted on wrist-worn devices to support multi-task HGR, denoted as MultiHGR. The system introduces a novel two-stage training strategy, i.e., task-agnostic stage to align cross-modal features from unlabeled arbitrary gesture through contrastive learning, and task-related stage to learn modality contributions with limited labeled data in specific tasks through self-attention mechanism. Since only the second task-related stage should be executed for each new task, MultiHGR could accommodate multiple tasks with significant reduced training cost and storage requirement. The evaluation results on three HGR tasks demonstrates that MultiHGR reduces 64.92% training time, and 24.04% storage as compared with traditional multimodal single-task models, and MultiHGR outperforms unimodal single-task models with 14.37%, 19.28%, and 31% improvements in these three tasks, respectively. As compared with state-of-the-art multimodal single-task model, MultiHGR achieves average 6.35% accuracy improvement, along with 65.74% training time reduction.

The blossoming semi-automated vehicles allow drivers to engage in various non-driving-related tasks, which may stimulate diverse emotions, thus affecting takeover safety. Though the effects of emotion on takeover behavior have recently been examined, how to effectively obtain and utilize drivers' emotions for predicting takeover behavior remains largely unexplored. We propose EmoTake, a deep learning-empowered system that explores drivers' emotional and physical states to predict takeover readiness, reaction time, and quality. The key enabler is a deep neural framework that extracts drivers' fine-grained body movements from a camera and interprets them into drivers' multi-channel emotional and physical information (e.g., facial expression, and head pose) for prediction. Our study (N = 26) verifies the efficiency of EmoTake and shows that: 1) facial expression benefits prediction; 2) emotions have diverse impacts on takeovers. Our findings provide insights into takeover prediction and in-vehicle emotion regulation.

WiFi connection has been suffering from MAC forgery attacks due to the loose authentication mechanism between access points (APs) and clients. To address this problem, the physical (PHY) layer information-based fingerprint has been adopted for safe WiFi authentication. Since such a fingerprint is constant and unique for each specific network interface card (NIC), it can effectively prevent MAC forgery attacks. However, the PHY layer information-based fingerprint is still vulnerable to malicious attacks as it is extracted from Channel State Information (CSI), and its stability can be affected by the wireless environment. In this paper, we propose a novel undetectable attack framework, called PhyFinAtt, base on which the attacker can undermine the stability of the PHY layer-based authentication fingerprints through human movement and further attack the WiFi authentication protocols. Specifically, we first demonstrate that human movement at a designated location can affect the PHY fingerprint. We then illustrate the impact of human movement on the PHY fingerprint and the relationship between the movement and the channel quality to ensure that the PHY fingerprint is destroyed by the movement in an undetected way without affecting normal communication. Extensive experiments in real-world scenarios show that our proposed attack can effectively disrupt the stability of the PHY fingerprints and significantly degrade the performance of the authentication protocols based on such fingerprints. To the best of our knowledge, this is the first study on effective attacks against the PHY information-based WiFi authentication protocols. Furthermore, we also present a practical defense mechanism without involving any additional equipment to mitigate attacks similar to PhyFinAtt.

Social networks exhibit a distinct "celebrity effect" whereby influential individuals have a more significant impact on others compared to ordinary individuals, unlike other network structures such as citation networks and knowledge graphs. Despite its common occurrence in social networks, the celebrity effect is frequently overlooked by existing social recommendation methods when modeling social relationships, thereby hindering the full exploitation of social networks to mine similarities between users. In this paper, we fill this gap and propose a Celebrity-aware Graph Contrastive Learning Framework for Social Recommendation (CGCL), which explicitly models the celebrity effect in the social domain. Technically, we measure the different influences of celebrity and ordinary nodes by mining social network structure features, such as closeness centrality. To model the celebrity effect in social networks, we design a novel user-user impact-aware aggregation method, which incorporates the celebrity-aware influence information into the message propagation process. Additionally, we design a graph neural network-based framework which incorporates social semantics into the user-item interaction modeling with contrastive learning-enhanced data augmentation. The experimental results on three real-world datasets show the effectiveness of the proposed framework. We conduct ablation experiments to prove that the key components of our model benefit the recommendation performance improvement.

The abundance of data provided by mobile edge devices enables a wide range of mobile edge computing (MEC) applications. Numerous studies have investigated efficient offloading methods for bandwidth savings in MEC. However, they focus on trading the device's computational cost for a reduction in communication, while edge devices can be rather resource-limited and must handle several jobs simultaneously. In this paper, the computation overhead on the device is pushed to its absolute minimum (almost no overhead), and consideration is given to enhancing the accuracy of the image recognition task within the constraints of the transmission volume limitation. We propose a mask-reconstruct system called MOT to mask images on the device side and recover images with the Masked Autoencoders (MAE)-based model on the server side. We further design a feedback-driven scheme to achieve content-aware transmission. Extensive experiments have been conducted to verify the effectiveness of the MOT.

Emotion plays a critical role in making the computer more human-like. As the first and most essential step, emotion recognition emerges recently as a hot but relatively nascent topic, i.e., current research mainly focuses on single modality (e.g., facial expression) while human emotion expressions are multi-modal in nature. To this end, we propose an unobtrusive emotion recognition system leveraging two emotion-rich and tightly-coupled modalities, i.e., gesture and facial expression. The system design faces two major challenges, namely, how to capture the emotional expression in both modalities without disturbing the subject and how to leverage the relationship between modalities for recognizing the emotion. For the former, we explore WiFi and vision for unobtrusive and contactless gesture and facial expression sensing, respectively. For the latter, we propose a novel deep learning framework named Multi-Source Learning (MSL) to efficiently exploit both self-correlation in the modality and cross-correlation between modalities for fine-grained emotion recognition. To evaluate the proposed method, we prototype the system on low-cost commodity WiFi and vision devices, build a first-of-its-kind WiFi-Vision emotion dataset, and conduct extensive experiments. Empirical results not only verify the effectiveness of WiFE in emotion recognition, but also confirm the superiority of multi-modality over single-modality.

Facial Expression Recognition (FER) has recently emerged as a crucial area in Human-Computer Interaction (HCI) system for understanding the user’s inner state and intention. However, feature- and label-noise constitute the major challenge for FER in the wild due to the ambiguity of facial expressions worsened by low-quality images. To deal with this problem, in this paper, we propose a simple but effective Facial Expression Noise-tolerant Network (FENN) which explores the inter-class correlations for mitigating ambiguity that usually happens between morphologically similar classes. Specifically, FENN leverages a multivariate normal distribution to model such correlations at the final hidden layer of the neural network to suppress the heteroscedastic uncertainty caused by inter-class label noise. Furthermore, the discriminative ability of deep features is weakened by the subtle differences between expressions and the presence of feature noise. FENN utilizes a feature-noise mitigation module to extract compact intra-class feature representations under feature noise while preserving the intrinsic inter-class relationships. We conduct extensive experiments to evaluate the effectiveness of FENN on both original annotated images and synthetic noisy annotated images from RAF-DB, AffectNet, and FERPlus in-the-wild facial expression datasets. The results show that FENN significantly outperforms state-of-the-art FER methods.

Vital sign (breathing and heartbeat) monitoring is essential for patient care and sleep disease prevention. Most current solutions are based on wearable sensors or cameras; however, the former could affect sleep quality, while the latter often present privacy concerns. To address these shortcomings, we propose Wital, a contactless vital sign monitoring system based on low-cost and widespread commercial off-the-shelf (COTS) Wi-Fi devices. There are two challenges that need to be overcome. First, the torso deformations caused by breathing/heartbeats are weak. How can such deformations be effectively captured? Second, movements such as turning over affect the accuracy of vital sign monitoring. How can such detrimental effects be avoided? For the former, we propose a non-line-of-sight (NLOS) sensing model for modeling the relationship between the energy ratio of line-of-sight (LOS) to NLOS signals and the vital sign monitoring capability using Ricean K theory and use this model to guide the system construction to better capture the deformations caused by breathing/heartbeats. For the latter, we propose a motion segmentation method based on motion regularity detection that accurately distinguishes respiration from other motions, and we remove periods that include movements such as turning over to eliminate detrimental effects. We have implemented and validated Wital on low-cost COTS devices. The experimental results demonstrate the effectiveness of Wital in monitoring vital signs.

Emotion recognition plays a vital role in current research on human-computer interaction, and human emotion expressions are multi-modal. In this paper, we propose a passive multi-modal emotion recognition system based on facial expression and gesture. To achieve the system design, two major challenges must be addressed, namely, how to capture facial expression and gesture without disturbing the subject, and how to use the correlation between the two modalities to better recognize emotions. For the former, we use WiFi and vision for the passive gesture and facial expression capture, respectively. For the latter, we design a Multi-Source Learning method inspired by Multi-Task Learning to efficiently exploit the correlation between modalities for better emotion recognition. Finally, to evaluate the effectiveness of our system, we use low-cost vision and WiFi devices to prototype the system and build a WiFi-Vision emotion dataset for related research, and we verify the effectiveness of our system in emotion recognition and the superiority of multi-modality over single-modality through conduct extensive experiments.

Label-noise constitutes a major challenge for facial expression recognition in the wild due to the ambiguity of facial expressions worsened by low-quality images. To deal with this problem, we propose a simple but effective Label-noise Robust Network (LRN) which explores the inter-class correlations for mitigating ambiguity that usually happens between morphologically similar classes. Specifically, LRN leverages a multivariate normal distribution to model such correlations at the final hidden layer of the neural network to suppress the heteroscedastic uncertainty caused by inter-class label noise. Furthermore, LRN utilizes a confidence-based label-free loss to extract compact intra-class feature representations under label noise while preserving the intrinsic inter-class relationships. Experiments on three in-the-wild facial expression datasets demonstrates the superiority of our method.

Magnetic resonant coupling (MRC) wireless power transfer (WPT) is a convenient and potential power supply solution for smart devices. The scheduling problem in the multiple-input multiple-output (MIMO) scenarios is essential to concentrate energy at the receiver (RX) side. Meanwhile, strong TX-RX coupling could ensure better power transfer efficiency (PTE), but may cause lower power delivered to load (PDL) when transmitter voltages are bounded. In this paper, we propose the frequency adjustment based PDL maximization scheme for MIMO MRC-WPT systems. We formulate such joint optimization problem and decouple it into two sub-problems, i.e., high-level frequency adjustment and low-level voltage adaptation. We solve these two sub-problems with gradient descent based and alternating direction method of multipliers (ADMM) based algorithms, respectively. We further design an energy-voltage transform matrix algebra based estimation mechanism to reduce context measurement overhead. We prototype the proposed system, and conduct extensive experiments to evaluate its performance. As compared with the PTE maximization solutions, our system trades smaller efficiency for larger energy, i.e., 361% PDL improvement with respect to 26% PTE losses when TX-RX distance is 10cm.

Human pulmonary function declines with age. Elders, especially those with lung or cardiovascular diseases, yearn for daily lung function tests for timely diagnosis and treatment. However, current clinical spirometers are cumbersome and ex-pensive while home-use portable ones’ accuracy is questionable. Moreover, both kinds require contact measurements and could cause cross infection, especially hazardous for contagious diseases like COVID-19. To this end, we propose SpiroFi, a contactless system that leverages WiFi Channel State Information (CSI) for convenient yet accurate Pulmonary Function Testing (PFT) out of clinic. The key enabler underlying SpiroFi is a set of algorithms that can extract chest wall movement from WiFi signal variations and interpret such information into lung function indices. We have realized SpiroFi on low-cost commodity WiFi devices and tested it in a home-like site where it achieves 2.55% monitoring error over healthy youths. Then, with the Ethics Committee (EC) approval, we conducted a 2-month clinic study in a city hospital over elders with basic diseases. SprioFi still yields 6.05% monitoring error despite elders’ degenerated pulmonary function and body control. Also, the correlation between lung function and age as well as chronic diseases has been revealed, highlighting the importance of daily PFT for the elderly.

Gestures constitute an important form of nonverbal communication where bodily actions are used for delivering messages alone or in parallel with spoken words. Recently, there exists an emerging trend of WiFi sensing-enabled gesture recognition due to its inherent merits like remote sensing, non-line-of-sight covering, and privacy-friendly. However, current WiFi-based approaches mainly reply on domain-specific training since they don’t know “where to look” and “when to look.” To this end, we propose WiGRUNT, a WiFi-enabled gesture recognition system using dual-attention network, to mimic how a keen human being intercepting a gesture regardless of the environment variations. The key insight is to train the network to dynamically focus on the domain-independent features of a gesture on the WiFi channel state information via a spatial-temporal dual-attention mechanism. WiGRUNT roots in a deep residual network (ResNet) backbone to evaluate the importance of spatial-temporal clues and exploit their inbuilt sequential correlations for fine-grained gesture recognition. We evaluate WiGRUNT on the open Widar3 dataset and show that it significantly outperforms its state-of-the-art rivals by achieving the best-ever performance in-domain or cross-domain.

User authentication plays a critical role in access control of a man-machine system, where the knowledge factor, such as a personal identification number, constitutes the most widely used authentication element. However, knowledge factors are usually vulnerable to the spoofing attack. Recently, the inheritance factor, such as fingerprints, emerges as an efficient alternative resilient to malicious users, but it normally requires special equipment. To this end, in this article, we propose WiPass, a device-free authentication system only leveraging the pervasive Wi-Fi infrastructure to explore keystroke dynamics (manner and rhythm of keystrokes) captured by the channel state information to recognize legitimate users while rejecting spoofers. However, it remains an open challenge to characterize the behavioral features hidden in the human subtle motions, such as keystrokes. Therefore, we build a signal enhancement model using Ricean distribution to amplify user keystroke dynamics and a hybrid learning model for user authentication, which consists of two parts, i.e., convolutional neural network based feature extraction and support vector machine based classification. The former relies on visualizing the channel responses into time-series images to learn the behavioral features of keystrokes in energy and spectrum domains, whereas the latter exploits such behavioral features for user authentication. We prototype WiPass on the low-cost off-the-shelf Wi-Fi devices and verify its performance. Empirical results show that WiPass achieves on average 92.1% authentication accuracy, 5.9% false accept rate, and 6.3% false reject rate in three real environments.

Real-time vital signs (breathing and heartbeat) monitoring is essential for patient care and sleep disease prevention. Current solutions are mostly based on wearable sensors or cameras, the former affects the quality of sleep, while the latter is not conducive to privacy protection, and the cost of these methods is usually expensive. In this paper, we propose Wital, a real-time vital signs monitoring system based on the low-cost and widespread COTS WiFi device. Most of the existing WiFi-based vital signs monitoring solutions utilize the line of sight (LOS) WiFi signals to achieve powerful performance. However, in our daily environments, NLOS sensing is more common. In this article, we first model the relationship between the energy ratio of LOS/NLOS signals and the ability to monitor vital signs based on the Ricean-K theory and theoretically prove that blocking LOS signals in NLOS sensing is more beneficial. We have also established a real-time vital signs monitoring system to verify our method, and the experimental results prove the effectiveness of our method.

Material identification is playing an increasingly important role in our daily lives such as public security checks. X-ray-based technologies are highly radioactive because they rely on specialized devices to transmit high-frequency signals. Ultrasound-based technologies are cumbersome due to their large size. RF-based approaches necessitate the use of RFID which is usually expensive to be used in home and office environments. To this end, WiFi-based material identification approach has emerged recently as a low-cost yet effective alternative. In this paper, we propose WiMate, a noncontact material identification system leveraging only off-the-shelf WiFi devices. The key enabler of WiMate is a novel theoretical model we build to characterize how the electromagnetic wave decays when penetrating different materials. Our model identifies a unique feature for each material that only depends on the material itself. Consequently, we can leverage this feature coupling with the machine learning techniques for robust and accurate material identification. We prototype WiMate using low-cost commodity WiFi devices and evaluate its performance in real-world. The empirical study shows that WiMate can identify six different materials, i.e., board, paperboard, nickel, wood chip, iron and titanium, with an average accuracy of 96.20%.

Federated learning has been proposed as a promising distributed machine learning paradigm with strong privacy protection on training data. Existing work mainly focuses on training convolutional neural network (CNN) models good at learning on image/voice data. However, many applications generate graph data and graph learning cannot be efficiently supported by existing federated learning techniques. In this paper, we study federated graph learning (FGL) under the cross-silo setting where several servers are connected by a wide-area network, with the objective of improving the Quality-of-Service (QoS) of graph learning tasks. We find that communication becomes the main system bottleneck because of frequent information exchanges among federated severs and limited network bandwidth. To conquer this challenge, we design Glint, a decentralized federated graph learning system with two novel designs: network traffic throttling and priority-based flows scheduling. To evaluate the effectiveness of Glint, we conduct both experiments on a testbed and trace-driven simulations. The results show that Glint can significantly outperform existing federated learning solutions.

User authentication is the first and most critical step in protecting a man-machine system from a malicious spoofer. However, security and privacy are just like the two sides of one coin, hard to see both at the same time, especially by the current mainstream credential- and biometric-based approaches. To this end, we propose WiONE, a safe and privacy-preserving user authentication system leveraging the ubiquitous Wi-Fi infrastructure by exploring “how you behave” rather than “who you are”. The key idea is to apply deep learning to user physical behavior captured by Wi-Fi channel state information (CSI) to identify legitimate users while rejecting spoofers. The design of WiONE faces two challenges, namely, how to capture the subtle behavior, such as a keystroke on CSI, and how to mitigate the heavy environment-specific training required by deep learning. For the former, we design a behavior enhancement model based on the Rician fading to highlight the behavior-induced information by suppressing the behavior-unrelated information on channel response. For the latter, we develop a behavior characterization method tailored for the prototypical networks to facilitate the extraction of the domain-independent behavioral features and enable one-shot recognition of a new user in a new environment. Numerous experiments are conducted in several real-world environments, and the results show that WiONE outperforms its state-of-the-art rivals in authentication performance with much less training effort.

Sleep is a major event of our daily lives. Its quality constitutes a critical indicator of people's health conditions, both mentally and physically. Existing sensor-based or vision-based sleep monitoring systems either are obstructive to use or fail to provide adequate coverage. With the fast expansion of wireless infrastructures nowadays, channel data, which is pervasive and transparent, emerges as another alternative. To this end, we propose Sleepy, a wireless channel data driven sleep monitoring system leveraging commercial WiFi devices. The key idea of Sleepy is that the energy feature of the wireless channel follows a Gaussian Mixture Model (GMM) derived from the accumulated channel data over a long period. Therefore, a GMM based foreground extraction method has been designed to adaptively distinguish motions like rollovers (foreground) from background (stationary postures), leading to certain major merits, e.g., no calibrations or target-dependent training needed. We prototype Sleepy and evaluate it in two real environments. In the short-term controlled experiments, Sleepy achieves 95.65 percent detection accuracy (DA) and 2.16 percent false negative rate (FNR) on average. In the 60-minute real sleep studies, Sleepy demonstrates strong stability, i.e., 0 percent FNR and 98.22 percent DA. Considering that Sleepy is compatible with existing WiFi infrastructure, it constitutes a low-cost yet promising solution for sleep monitoring.

Good quality sleep is essential for good health and sleep monitoring becomes a vital research topic. This paper provides a low cost, continuous and contactless WiFi-based vital signs (breathing and heart rate) monitoring method. In particular, we set up the antennas based on Fresnel diffraction model and signal propagation theory, which enhances the detection of weak breathing/heartbeat motion. We implement a prototype system using the off-shelf devices and a real-time processing system to monitor vital signs in real time. The experimental results indicate the accurate breathing rate and heart rate detection performance. To the best of our knowledge, this is the first work to use a pair of WiFi devices and omnidirectional antennas to achieve real-time individual breathing rate and heart rate monitoring in different sleeping postures.

How can we effectively log a fine-grained sleep record consisting of still postures and in-place motions for the sleep disorder diagnosis without any specialized hardware? Existing sensor-based or vision-based solutions are either obstructive to use or rely on particular devices. This paper introduces SleepGuardian, a Radio Frequency (RF) based sleep monitoring system leveraging only omnipresent WiFi signals to provide a silent (unobtrusive and free of privacy concerns) yet loyal (finegrained and reliable) logging service. The key to SleepGuardian is to model the energy feature of wireless channel as a Gaussian Mixture Model (GMM) to adaptively recognize motions happened during sleep. We prototype SleepGuardian with off-the-shelf WiFi devices and evaluate it in an office. Experimental results over 11 subjects with several artificial and real periods of sleep demonstrate that SleepGuardian is effective since it achieves 100% overall accuracy (ACC), 0% false negative rate (FNR) and 0.64 s mean absolute error (MAE) on average. Considering that SleepGuardian is compatible with existing WiFi infrastructure, it constitutes a low-cost yet promising solution for sleep monitoring.

Falls are the second leading cause of injury deaths worldwide, inducing over 0.6 million accidental deaths per year. Among various prevention strategies, fall-related research has been prioritized. However, conventional fall detection solutions rely on computer vision or wearable sensors embody several inherent limitations such as scalability, coverage, and privacy issues. To this end, we present FallSense, a transparent and real-time fall sensing system driven by wireless channel data. FallSense is built on a Dynamic Template Matching (DTM) algorithm, which can start with a light training set and keep updating on usage. FallSense has been realized on commodity WiFi devices and evaluated in real environments. Experimental results show that FallSense outperforms another state-of-the-art approach WiFall in terms of detection precision, false alarm rate and complexity.

Constructing Radio Environment Map (REM) accurately and cost-efficiently is of great importance to realize dynamic spectrum access. Two kinds of approaches are widely investigated recently, i.e., radio propagation model based approaches and sensor monitoring based approaches. However, these existing approaches are suffering from either inaccurate spectrum availability or high deployment cost. To this end, outsourcing the spectrum sensing task to mobile users that are outfitted with spectrum sensors could greatly reduce the operator's expenditure, and meanwhile, achieve a satisfactory accuracy. The key of crowdsourced REM construction is to attract user participation. In this paper, we propose a novel online incentive mechanism for constructing a fine-grained REM with crowdsourcing in a realistic scenario, where the mobile users arrive and leave in an online manner. The proposed mechanism is proven to satisfy the truthfulness, individual rationality, computational efficiency and consumer sovereignty. Evaluation results demonstrate that the proposed mechanism outperforms the baseline schemes substantially.

Facilitating real-time query over massive IoT data streams becomes increasingly important nowadays, for that it can boost the performances of real-time network services significantly. Let δ = e1, e2, ⋯ , et, ⋯ represent an IoT data stream, where each element et arrives at time point t. In this paper, we consider the problem of how to support fast range emptiness querying over an IoT data stream δ in sliding window model with a space-efficient data structure, and we denote this problem as the (ε, L)-ARE-problem. To be more formally, subjected to the constraint of one-pass scan of stream δ, the main task of the (ε, L)-ARE-problem is to design a space-efficient data structure that is capable of always representing W(t, n), which are the n latest elements of stream δ until time point t (i.e., W(t, n) = emax{1,t-n+1}, ⋯ , et-1, et), and quickly answering an emptiness query of the form ”W(t, n) ∩ I = 0?”, with a false positive rate no larger than ε, for any query interval I of length up to L. We design a space-efficient data structure D to solve the (ε, L)-ARE-problem and prove that D has constant time cost for querying an interval, inserting a stream element and evicting outdated elements. The efficiency is demonstrated with extensive simulation results as well.

In this paper, we present WoSense, a device-free and real-time behavior analysis system leveraging only WiFi infrastructures. WoSense aims to remotely recognize various human behaviors like surfing, gaming and working around computers, which are considered to be an essential part of our daily lives both at work and at home. The key of WoSense is to exploit the signal distortions on channel data caused by gestures like finger and hand movements, and then identify possible behaviors via the composite of gestures. Therefore, two critical challenges need to be tackled: how to enhance such insignificant distortions led by micro gestures, how to segment the continuous signals according to different gestures in a real-time manner? For the former, instead of relying on empirical studies like our rivals, WoSense offers a Fresnel zone based model with theoretic understandings between the gestures and signal distortions. For the latter, WoSense employs a light-weight automatic segmentation algorithm exploring the variance feature of channel data. We prototype WoSense on the commodity low-cost WiFi devices and evaluate its performance in extensive real- world experiments. WoSense achieves an average 96.77% accuracy for distinguishing the typing and mousing gestures, and 92.5% accuracy for recognizing four different behaviors, i.e., stationary, surfing, gaming and working.

Emotion is a unique feature of human beings. Recent research in emotion sensing has already revealed its potentials in enhancing our living experiences through applications like emotion companion and autism treatment. However, existing solutions exploring audiovisual clues or psychological sensors have several critical concerns such as the availability (specialized hardware), reliability (illumination and line-of-sight constraints) and privacy issues (being watched). To this end, we present EmoSense, a first-of-its-kind WiFi-based emotion sensing system leveraging the temporal and frequency fingerprints on the wireless channel data induced by the physical expression of emotion. EmoSense has been prototyped with off- the-shelf WiFi devices and evaluated by comparing with the main-stream sensor-based approach in real environments. Experimental results demonstrate its effectiveness and robustness. Considering that EmoSense is compatible with existing WiFi infrastructures, it constitutes a low-cost yet promising solution for emotion sensing.

In order to cope with the increasing number of cyber attacks, network operators must monitor the whole network situations in real time. Traditional network monitoring method that usually works on a single machine, however, is no longer suitable for the huge traffic data nowadays due to its poor processing ability. In this paper, we propose a machine-learning based online Internet traffic monitoring system using Spark Streaming, a stream- processing-based big data framework, to detect DDoS attacks in real time. The system consists of three parts, collector, messaging system and stream processor. We use a correlation-based feature selection method and choose 4 most necessary network features in our machine- learning-based DDoS detection algorithm. We verify the result of feature selection method by a comparative experiment and compare the detection accuracy of 3 machine learning methods - Naïve Bayes, Logistic Regression and Decision Tree. Finally, we conduct experiments in a cluster with the standalone mode, showing that our system can detect 3 typical DDoS attacks - TCP flooding, UDP flooding and ICMP flooding at the accuracy of more than 99.3%. It also shows the system performs well even for large Internet traffic.

Sleep is a major event of our daily lives. Its quality constitutes a critical indicator of people's health conditions, both mentally and physically. Existing sleep monitoring systems either are obstructive to use or fail to provide adequate coverage. To overcome these shortages, we propose Sleepy, an adaptive and noninvasive sleep monitoring system leveraging channel response in the commercial WiFi devices. Sleepy needs no calibrations or target-dependent training to recognize posture changes during sleep. To achieve that, a Gaussian Mixture Model (GMM) based foreground extraction method has been designed to adaptively distinguish motions like rollovers (foreground) from background (stationary postures). We prototype Sleepy and evaluate it in two real environments. In the short-term controlled experiments, Sleepy achieves 95.04% detection accuracy and 4.07% false negative rate. In the 60-minute real sleep studies, Sleepy demonstrates strong stability. Considering that Sleepy is compatible with existing WiFi infrastructures, it constitutes a low-cost yet promising solution for sleep monitoring.

In spectrum sharing system, an exclusion zone is defined to protect both primary and secondary users from interference. Reducing the size of exclusion zone is critical for efficiently utilizing the fallow spectrum. In this paper, we propose a novel crowdsourcing augmented exclusion zone refinement framework. In our framework, a barter-like exchange model using spectrum access right is employed to incentivize the secondary users (SUs) to participate in the crowdsourcing. We further design a truthful auction mechanism to select the SUs and determine their access time in a computationally efficient way. We perform simulations to validate the proposed mechanism, and compare it with two baseline schemes.

To improve the spectrum utilization efficiency, radio propagation model based spectrum database is widely investigated recently. However, it is prone to offer inaccurate and stale spectrum availability since the empirical models do not count for local environment details. One promising solution is to incorporate real- time spectrum measurement into the quasi-static spectrum database. In this paper, we propose a novel fine-grained incentive mechanism for sensing augmented spectrum database. We first present a reverse auction framework, which minimizes the operator's total expenditure subject to the quality requirement of each spot that needs to be augmented. Then we propose a practical incentive mechanism to solve the auction problem, which is proven to be truthful, individual rational and computationally efficient. Simulation results demonstrate that the proposed mechanism could save noticeable expenditure compared to two baseline schemes.

Human activity recognition based on wireless signals emerges as a research hotspot recently. Though tremendous efforts have been devoted and significant progresses have been achieved, one fundamental issue still remains open, i.e., theoretical modeling between signal dynamics and human activities. This paper fills in the blank by addressing several theoretical issues and providing insightful mathematical analysis including a signal-activity model. To validate such analysis, a prototype system has been built, where a series of real-world experiments has been conducted. Empirical results have justified our theoretical findings. Moreover, important hands-on experiences on the system implementation and parameter settings have been offered.

Motion is a critical indicator of human presence and activities. Recent developments in the field of indoor motion detection have the potential to enhance various aspects of our daily experiences like intrusion detection and sleep monitoring. Existing indoor motion detection solutions either are obstructive to use or fail to provide adequate coverage. To overcome these shortages, a noninvasive and cost-effective motion detection system (MoSense) is proposed for periodically detecting motions by exploring channel response in the commodity WiFi devices. The central idea is that signals in a ``silence'' environment serve well as a ``golden'' benchmark for recognizing motions that lead to signal fluctuations. A prototype of MoSense is realized and evaluated in real environments. By comparing MoSense with another state-of-the-art method, i.e., FIMD, we have shown that MoSense outperforms FIMD in terms of computational complexity, detection accuracy and false alarm rate. Considering that MoSense is compatible with existing WiFi infrastructure, it constitutes a low-cost yet promising solution for motion detection.

Motion is a critical indicator of human presence and activities. Recent developments in the field of indoor motion detection have revealed their potentials in enhancing our living experiences through applications like intrusion detection and sleep monitoring. However, existing solutions still face several critical downsides such as the availability (specialized hardware), reliability (illumination and line-of-sight constraints), and privacy issues (being watched). To overcome such shortages, a radio frequency (RF) based device-free motion detection system (MoSense) is designed via leveraging the attenuation of ubiquitous WiFi signals induced by motions to deliver a reliable and transparent detection service in realtime. The design and implementation of MoSense face two challenges: 1) characterizing stationary states and 2) the noisy subcarriers. For the first challenge, a silence analysis model is proposed to characterize stationary states for distinguishing motions. For the second challenge, we design a distance-based mechanism to select certain subcarriers that better capture the impact of motions from the noisy channel through measuring the similarity between subcarriers. A prototype of MoSense is realized and evaluated in real environments. By comparing MoSense with other two state-of-the-art systems, i.e., FIMD and FRID, we have shown that MoSense is superior in terms of precision, false negative rate and computational complexity. Considering that MoSense is compatible with existing WiFi infrastructure, it constitutes a low-cost yet promising solution for motion detection.

This paper presents a novel WLAN-based indoor localization algorithm (i.e., HED) to combat the environmental dynamics by tolerating the sequence disorders caused by AP (access point) changes, while harvesting from the bursting number of available wireless resources. Via extensive real-world experiments lasting for over 6 months, we show the superiority of our HED algorithm in terms of accuracy and complexity over two state-of-the-art solutions that are also designed to resist the dynamics, i.e., FreeLoc and LCS (Longest Common Subsequences). Moreover, experimental results not only confirm the benefits brought by environmental dynamics, but also provide valuable investigations and hand-on experiences on the real-world localization system.

Summary The flourishing social networks nowadays have greatly enriched our ways of communications and thus brought people in the world much closer than ever. However, critical contexts of the traditional face‐to‐face communications, for example, body gestures, could be missing during the online communication, hampering the user experiences. To fill in the blank, this paper presents a passive and devices‐free activity recognition system, by harvesting fingerprints of different activities from ubiquitous WiFi signals. It can be integrated into any existing WLAN networks without additional hardware supports. Also, it does not need the subjects to be cooperative during the recognition process. A prototype system is built and evaluated via extensive real‐world experiments. By comparing with three state‐of‐the art solutions, that is, K‐nearest neighbor, naive Bayes, and bagging, we show the superiority of the proposed method in terms of accuracy and complexity. Copyright © 2015 John Wiley & Sons, Ltd.

Indoor human activity recognition remains a hot topic and receives tremendous research efforts during the last few decades. However, previous solutions either rely on special hardware, or demand the cooperation of subjects. Therefore, the scalability issue remains a great challenge. To this end, we present an online activity recognition system, which explores WiFi ambient signals for received signal strength indicator (RSSI) fingerprint of different activities. It can be integrated into any existing WLAN networks without additional hardware support. Also, it does not need the subjects to be cooperative during the recognition process. More specifically, we first conduct an empirical study to gain in-depth understanding of WiFi characteristics, e.g., the impact of activities on the WiFi RSSI. Then, we present an online activity recognition architecture that is flexible and can adapt to different settings/conditions/scenarios. Lastly, a prototype system is built and evaluated via extensive real-world experiments. A novel fusion algorithm is specifically designed based on the classification tree to better classify activities with similar signatures. Experimental results show that the fusion algorithm outperforms three other well-known classifiers [i.e., NaiveBayes, Bagging, and k-nearest neighbor (k-NN)] in terms of accuracy and complexity. Important sights and hands-on experiences have been obtained to guide the system implementation and outline future research directions.

Dynamic spectrum reallocation, under which the spectrum owners temporarily share the underutilized spectrum to secondary users for economic profit, is an important approach to improve the spectrum utilization ratio. Auction is believed to be a natural marketing tool to incentivize the spectrum owners, and thus redistribute the idle spectrum efficiently. Extensive researches have been done in the problem of truthful spectrum auction, in which the bidders bid based on their true valuations of the spectrum. The true valuation of the individual bidder, however, is a private information which should be protected against exposure. In this paper, we propose a privacy preserving truthful spectrum auction scheme by utilizing homomorphic encryption. The proposed scheme reveals the group bids but hides the users' bids even from the auctioneer. The evaluation results show that the proposed scheme achieves good spectrum utilization efficiency with low communication and computation overheads.

Indoor localization remains a hot topic during the last few decades. Previous research mainly relies on wireless fingerprints and thus demands a large number of APs or labor-intensive site survey. To this end, by exploring Bluetooth features and leveraging user motions, we introduce a novel localization scheme that needs neither APs nor site survey. More specifically, through a systematic experimental study, we gain in-depth understandings of Bluetooth characteristics e.g., The impact of various factors such as distance, orientation, and obstacles on the Bluetooth RSSI (Received Signal Strength Indicator). With the empirical experiences, a novel motion-assisted localization model is built to describe the relationship between RSSI and device location. Based on the model, we design a localization scheme that iteratively adjusts the search directions according to RSSI changes to approach the target device. We prototype and evaluate our system in several real-world scenarios. Extensive experiments show that the proposed scheme is efficient in terms of localization accuracy, searching time and energy consumption.

In this paper, we study the network Lifetime Maximization problem in Mobile healthcare sensor systems (LMM). For the healthecare system, we consider a dynamic scenario where users are mobile at their own wills and periodically report their personal health information (PHI) to a static sink, e.g. a powerful server, for further processing and distributing. The objective is to optimize the network lifetime by flow scheduling. The major difficulty lies in the time-dependent network topologies. Therefore, we propose a novel temporal-spatial network modeling method by extending current model with time dimension. Based on this model, we show that if the movement of users are known in advance (i.e. offline case), the problem can be optimally solved in polynomial time by a linear programming. However, the online LMM problem is much more difficult to tackle, since we prove that there exists no online algorithm with a constant performance ratio to the offline optimal algorithm in terms of the network lifetime. We further design simulations to show the performance gap between online and offline LMM. Considering the user mobility within a given scenario follows some certain patterns, we show the potential improvements of using a prediction-based method. This investigation provides certain insights on designing efficient online algorithms for the LMM problem.

This paper exploits sink mobility to prolong the network lifetime in wireless sensor networks where the information delay caused by moving the sink should be bounded. Due to the combinational complexity of this problem, most previous proposals focus on heuristics and provable optimal algorithms remain unknown. In this paper, we build a unified framework for analyzing this joint sink mobility, routing, delay, and so on. We discuss the induced subproblems and present efficient solutions for them. Then, we generalize these solutions and propose a polynomial-time optimal algorithm for the origin problem. In simulations, we show the benefits of involving a mobile sink and the impact of network parameters (e.g., the number of sensors, the delay bound, etc.) on the network lifetime. Furthermore, we study the effects of different trajectories of the sink and provide important insights for designing mobility schemes in real-world mobile WNNs.

ABSTRACT This paper deals with the partial target coverage problem in wireless sensor networks under a novel coverage model. The most commonly used method in previous literature on the target coverage problem is to divide continuous time into discrete slots of different lengths, each of which is dominated by a subset of sensors while setting all the other sensors into the sleep state to save energy. This method, however, suffers from shortcomings such as high computational complexity and no performance bound. We showed that the partial target coverage problem can be optimally solved in polynomial time. First, we built a linear programming formulation, which considers the total time that a sensor spends on covering targets, in order to obtain a lifetime upper bound. Based on the information derived in previous formulation, we developed a sensor assignment algorithm to seek an optimal schedule meeting the lifetime upper bound. A formal proof of optimality was provided. We compared the proposed algorithm with the well‐known column generation algorithm and showed that the proposed algorithm significantly improves performance in terms of computational time. Experiments were conducted to study the impact of different network parameters on the network lifetime, and their results led us to several interesting insights. Copyright © 2011 John Wiley & Sons, Ltd.

The resource allocation problem to support scalable-video multicast for wireless relay networks is complex due to the existence of the relay station. In this paper, we consider the resource allocation for SVC multicast over two-hop wireless relay networks to maximize the total system utility of all users where the system utility can be a general non-negative, non-decreasing function. We model the problem in three-layer structure (choice elements, action elements, and user elements) to cope with the joint dependency and overlapping phenomena. We formulate the problem as Cascaded Coverage Problem (CCP) and propose a greedy algorithm with polynomial time complexity. Simulation results show that our algorithm keeps good performance as compared with the optimal result. We also evaluate the influence of different user distribution types and the number of relay stations.

This paper exploits sink mobility to prolong the network lifetime in wireless sensor networks (WSNs) where the information delay caused by moving the sink should be bounded. We build a unified framework for analyzing this joint sink mobility and routing problem. We offer a mathematical modeling that is general and captures diversified issues, e.g. sink mobility, routing, delay, etc. We discuss the induced subproblems and present efficient solutions for them. Then, we generalize these solutions and propose a polynomial-time optimal algorithm for the origin problem. In simulations, we show the benefits of involving a mobile sink. We also show that the impact of the delay bound on the network lifetime.

Orthogonal frequency division multiplexing (OFDM) is regarded as a promising technique for the next generation wireless networks. In OFDM system, transmitter can provide high data rates by dividing channels into multiple orthogonal subcarriers and then allocates them to different users. But in the field of multicast, the conventional method ignores the differences of the channel condition between the users and therefore forces the modulation be adjusted to serve the worst user. The unique contribution of our work is to maximize the total throughput in a time efficient manner. In this paper, we propose a dynamic-programming-based algorithm to find the maximum capacity of system in a global manner after partitioning the available power into schedulable equal pieces. Experimental results demonstrate the effectiveness and efficiency of the proposed algorithm, the system throughput gap between the proposed dynamic-programming-based algorithm and the optimal algorithm is within about 2%, and significantly outperform the lowest channel gain method as well as the previous works.

Future 4G cellular networks are featured with high data rates and improved coverage, which will enable real-time video multicast and broadcast services. Scalable video coding with different modulation and coding schemes (MCSs) applied to different video layers is very appropriate for wireless multicast services because it can provide different video quality to different users according to their channel conditions and light-weight feedback on how many packets they have received. It is important to choose an appropriate MCS for each layer, decide how many parity packets in one layer should be transmitted, and determine the resources allocated to multiple video sessions to apply scalable video coding to wireless multicast streaming. This paper proposes an optimal algorithm that finds the optimal total system utility of all users where the utility can be a generic nonnegative, non-decreasing function of the received rate. The results from simulations revealed that our algorithm offer significant improvements to video quality over an optimal algorithm without feedback from users and a naïve algorithm especially in scenarios with multiple video session and limited resources.

Video multicast over wireless networks has its own challenges when facing the heterogeneity of networks and end-user capabilities, along with packet losses. Scalable video coding using different modulation and coding schemes (MCSs) applied to different video layers can provide different video qualities to different users according to their channel conditions. A layered hybrid NC/ARQ scheme is proposed in this paper to handle packet losses together with a structure network coding (SNC) technique to encode the SVC stream. It is important to choose an appropriate MCS for each layer, decide how many SNC packets in one layer should be transmitted, and determine the resources allocated to multiple video sessions to apply scalable video coding to wireless multicast streaming. We prove that such a resource allocation problem is NP-hard and propose an optimal algorithm with a pseudo-polynomial run time under a reasonable assumption. We also discuss the phenomenon of unexpected packet losses caused degradation of the layered hybrid NC/ARQ schemes in a high packet loss ratio environment, and propose a solution for overcoming such a problem. Our algorithm can attain the optimal transmission configuration for maximizing the expected utility for all receivers. The results from simulations revealed that our algorithm offers significant improvements to the video quality over an optimal algorithm without needing feedback from the receivers and an algorithm using a layered hybrid FEC/ARQ scheme, and it has the outstanding ability to combat unexpected packet losses.

As a promising way in surveillance applications, wireless sensor networks (WSNs) often encounter the target coverage (TC) problem, i.e., scheduling energy-limited sensors to monitor physical targets to prolong the network lifetime. Due to the complexity of the problem (scheduling in time domain), previous proposals mainly focus on heuristics and provable optimal algorithms remain unknown. In this paper, we fill in the research blank by providing several theoretical results. First, we present a mathematical formulation and several investigations of the problem in time domain. Such time-related results provide fundamental understandings of the problem and serve as a basis. Second, we offer an upper bound on the network lifetime derived from the time-dependant formulation. The bound, which is solvable in polynomial-time, serves as a performance benchmark. Third, we verify the set cover-based method, which is widely used by previous studies, via a transformation of the problem from time to space domain. Lastly, we offer a specialized nonlinear column generation (CG) based approach to solve the problem in space domain optimally. Simulation results show that not only the bound is effective, but also the CG-based approach offers significant improvement on the network lifetime over a brutal search algorithm and a state-of-art heuristic.

Sink scheduling is shown to be a promising scheme in wireless sensor networks. However, previous approaches on this topic suffer from poor performance due to lack of joint considerations. Therefore, in this paper, we aim to fill in the research blank. First, we develop a novel notation Placement Pattern (PP) to bound time-varying routes with placement of sinks. This bounding technique transforms time-related constraints into pattern-based ones and allows us to formulate this optimization in pattern domain. If there is only one sink, we develop a polynomial time algorithm to solve it optimally. If there are multiple sinks, we develop a column generation based approach to solve it efficiently. Simulations not only demonstrate the efficiency of proposed algorithms but also substantiate the importance of sink mobility for energy-constrained sensor networks.

A forest fire has long been a severe threat to the forest resources and human life. The threat could effectively be mitigated by timely and accurate detection. In this paper, we propose a novel accurate forest fire detection system using Wireless Sensor Networks (WSNs). In the proposed system, the detection accuracy is increased by applying the multi-criteria detection that an alarm decision depends on multiple attributes of a forest fire. The multi-criteria detection is implemented by the artificial neural network which fuses sensing data corresponding to multiple attributes of a forest fire into an alarm decision. Due to the utilization of the artificial neural network, the proposed system enjoys low overhead and the self-learning capability. Furthermore, we have developed a prototype consisting TelosB sensor nodes and carried out extensive experiments to study the performance of the proposed system. We have also developed a solar battery in order to persistently power the unattended sensor node deployed in the forest.

We address the optimal sink scheduling problem in wireless sensor networks (WSNs). The problem is inherently difficult since sink scheduling and data routing are tightly coupled. Previous approaches either have questionable performance due to no joint considerations, or are based on relaxed constraints. Our aim is to fill in this blank in the research. First, by discretizing continuous time, we develop a novel bound technique to connect time-varying routes with the placement of sinks. This bounding technique transforms time-related constraints into pattern-based ones and allows us to mathematically formulate this optimization in a pattern-based way. The complexity of directly solving this optimization is intractable; therefore, on the basis of column generation (CG), a computationally efficient algorithm is developed to reduce the complexity by decomposing the problem into sub-problems and iteratively solving them to approach optimality. Simulations demonstrate the efficiency of the algorithm and substantiate the importance of sink mobility in energy-constrained sensor networks.

Recently, sink deployment, in the form of deploying the sink among different sites so as to leverage traffic burden, is shown to be a promising scheme to save energy and prolong network lifetime in wireless sensor networks. For this paradigm, the choice of sink sites plays a critical role in the overall system performance. In this paper, we address the optimal deployment problem for the sink in wireless sensor networks, where routing issues are naturally involved. The major contribution of this paper is the development of an efficient grid-based algorithm to solve this problem. By dividing the continuous search space into a limited number of so-called communication intersections, computational complexity has been significantly reduced. A formal proof of optimality for this algorithm is given and several interesting properties have been revealed by theoretic analysis as well as experimental results.

This paper deals with the partial target coverage (PTC) problem in wireless sensor networks with the objective of optimizing network lifetime. We first build a linear programming formulation, which takes total time a sensor spends on covering some targets into consideration, in order to obtain a lifetime upper bound. Then, based on the information of this formulation, we develop a sensor assignment algorithm to seek an optimal time table meeting the lifetime upper bound. A formal proof of optimality is given. We compare the proposed algorithm with a state-of-the-art algorithm: column generation approach and show that the proposed algorithm significantly outperforms in terms of computational time. Experiments have been conducted to study the effect of network parameters on network lifetime and interesting insights have been offered.

The target coverage problem is one of the most fundamental challenges in wireless sensor networks. Due to the complexity of the problem (time-dependent network topology and coverage constraints), previous studies have mainly focused on heuristic algorithms and the theoretical bound remains unknown. In this paper, we aim to fill in this gap by providing fundamental results. First, we investigate the properties of a problem in time domain via an example topology and build a novel transformation to connect a problem in the time domain with a corresponding problem in the space domain while maintaining the same network lifetime. Based on this transformation, we mathematically formulate the problem and build a column-generation based algorithm, which decomposes the original formulation into two sub-formulations and iteratively solves them in a way that approaches the optimal solution. We prove that the network lifetime that can be guaranteed by the proposed algorithm is at least (1-¿) of the optimum, where ¿ can be made arbitrarily small depending on the required precision.

Target coverage problem in wireless sensor networks remains a challenge. Due to nonlinear nature, previous work has mainly focused on heuristic algorithms, which remain difficult to characterize and have no performance guarantee. To solve the problem, this paper offers two important contributions. The first contribution is to have two lifetime upper bounds, which could be used to justify performance of previously proposed heuristic algorithms. One upper bound is based on the relaxation and reformulation technique while the other is derived by relaxing coverage constraints. We study the interesting connection between those two bounds and thus endow them with physical meanings. The second contribution is proposing a column generation based (CG) approach. The objective is to find an optimal schedule, defined as a time table specifying from what time up to what time which sensor watches which targets while the maximum lifetime has been obtained. We also offer an in-depth theoretic analysis as well as several novel techniques to further optimize the approach. Numerical results not only demonstrate that the lifetime upper bounds are very tight, but also verify that the proposed CG based approach constantly yields the optimal or near optimal solution.

Abstract Wireless sensor networks have emerged recently as an effective way of monitoring remote or inhospitable physical targets, which usually have different quality of service (QoS) constraints, i.e., different targets may need different sensing quality in terms of the number of transducers, sampling rate, etc. In this paper, we address the problem of optimizing network lifetime while capturing those diversified QoS coverage constraints in such surveillance sensor networks. We show that this problem belongs to NP‐complete class. We define a subset of sensors meeting QoS requirements as acoverage pattern, and if the full set of coverage patterns is given, we can mathematically formulate the problem. Directly solving this formulation however is difficult since number of coverage patterns may be exponential to number of sensors and targets. Hence, a column generation (CG)‐based approach is proposed to decompose the original formulation into two subproblems and solve them iteratively. Here a column corresponds to a feasible coverage pattern, and the idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. An initial feasible set of patterns is generated through a novel random selection algorithm (RSA), in order to launch our approach. Experimental data demonstrate that the proposed CG‐based approach is an efficient solution, even in a harsh environment. Simulation results also reveal the impact of different network parameters on network lifetime, giving certain guidance on designing and maintaining such surveillance sensor networks. Copyright © 2009 John Wiley & Sons, Ltd.

timization under storage constraint for wireless sensor networks with a mobile sink node. The problem is particularly challenging since we need to consider both mobility scheme and storage con- straint. Previous works suggest to use a simple single-hop routing model in which source nodes can only communication with the sink node directly in those mobile networks, However, we notice that this statement is unsuitable for sensor networks with storage constraint because we prove it is a NP-complete problem under single-hop routing model by reducing the Traveling Salesman Problem (TSP) to it in polynomial time. Hence, we try a different way. First we analyze this problem and give a lifetime upperbound, so whether this upperbound is tight is what we concern mostly. Thus, we first construct a 2-approximation O(n2) algorithm to solve the TSP problem, then a novel data diffusion mechanism is built to achieve this upperbound. We prove that under some reasonable assumptions, our algorithm can output this optimal lifetime.

optimization under coverage and connectivity requirements for sensor networks where different targets need to be monitored by different types of sensors running at possibly different sampling rates as well as different initial energy reserve. The problem is particularly challenging since we need to consider both connectiv- ity requirement and so-called target Q-coverage requirement, i.e., different targets may require different sensing quality in terms of the number of transducers, sampling rate, etc. First we formulate this NP-complete lifetime optimization problem, which is general and allows unprecedented diversity in coverage requirements, communication ranges, and sensing ranges. Our approach is based on column generation, where a column corresponds to a feasible solution; our idea is to find a column with steepest ascent in lifetime, based on which we iteratively search for the maximum lifetime solution. To speed up the convergence rate, we generate an initial solution through a novel random selection algorithm. Through extensive simulations, we systematically study the effect of target priorities, communication ranges, and sensing ranges on the lifetime.

Many applications in wireless sensor networks like video surveillance have the requirement of timely data delivery. Real-time routing is needed in these applications. Because of the limitation of node energy, energy efficiency is also an important concern in routing protocol design in order to increase the network lifetime. In this paper, we propose a global-energy-balancing routing scheme (GEBR) for real-time traffic based on directed diffusion (DD), which balances node energy utilization to increase the network lifetime. GEBR can find an optimal path in sensor networks for data transfer considering global energy balance and limited delivery delay. Simulation results show that GEBR significantly outperforms DD in uniform energy utilization. GEBR achieves better global energy balance and longer network lifetime. The time for real-time service of the sensor networks using GEBR is prolonged by about 4.37% and the network lifetime is prolonged by 44.6%.