Search

Due to software implementation failure and misuse of cryptography, data encryption can no longer be considered a safeguard from security attacks. As a result, adversaries with eavesdropping capability along a routing path can compromise data privacy. In addition, should an adversary be one of the intermediate relay nodes in a path, she can deny data forwarding to disconnect the end-to-end communications. One solution is to avoid message routing through certain insecure areas, such as malicious countries or likely-compromised nodes. To this end, an avoidance routing based on the single path has been proposed. However, this single-path-based protocol relies on the availability of a safe path, i.e., no adversary is in the proximity of the whole path, which is difficult to achieve and therefore limits the routing opportunity. To tackle this issue, we propose an avoidance routing framework, namely timer-based multi-path avoidance routing (TMPAR). In our approach, a source node first encodes a message into $k$ different pieces, and each piece is sent via a different path. During its path discovery phase, a timer is used to efficiently discover a better set of paths. The destination can assemble the original message easily. Under the condition that no adversary obtains all the $k$ pieces of the message, the proposed TMPAR can securely deliver a message to its destination in spite of eavesdropping. The extensive ns-2 simulation results demonstrate that our TMPAR achieves its design goals.

The performance of key authentication and the degree of privacy in large-scale RFID systems are considered by many researchers as tradeoffs. Based on how keys are managed in the system, the privacy preserving tag authentications proposed in the past can be categorized into tree-based and group-based approaches. While a tree-based approach achieves high performance in key authentication, it suffers from the issue of low privacy should a fraction of tags be compromised. On the contrary, while group-based key authentication is relatively invulnerable to compromise attacks, it is not scalable to a large number of tags. In this paper, we propose a new private tag authentication protocol based on skip lists, named randomized skip lists-based authentication (RSLA). Without sacrificing the authentication performance, RSLA provides a high privacy preserving mechanism. While RSLA provides the same level of unpredictability-based-privacy and indistinguishability-based privacy compared with other structured key management approaches, our scheme achieves the highest system anonymity with good performance in key look up and update. In addition, the simulation results match our analyses closely.

Designing fast and secure RFID private authentication with structured key management is one of the most essential components for RFID-enabled large-scale object management. Since group keys are shared by some tags in structured key-based authentication, physical tampering of tags, so called the compromise attack, may enable the adversary to obtain group keys stored in the compromised tags, which in turn can be used to distinguish other tags. All existing structured key-based protocols try to reduce the common group key effect to preserve high privacy. However, the theoretical bound of weak privacy achievable by structured key-based authentication remains unknown. In this paper, we investigate weak privacy in RFID authentication. To this end, we first formulate a mathematical model which identifies the probability of two tags being linked with respect to the number of group keys. Our model shows that the existing solutions are far from the ultimate goal in weak privacy. Then, we propose a k-neighbor graph-based RFID authentication (KNGA) protocol, where random walk over a k-neighbor graph is performed. In addition, we show that KNGA achieves the performance bound, and we then quantify the degree of privacy by anonymity. Finally, the extensive simulations demonstrate that the proposed protocol successfully achieves its design goals.

Radio frequency identification (RFID) is widely used as a tagging system to facilitate physical transactions in the real world. Thanks to the availability of inexpensive passive RF tags, RFID technology is now the catalyst of Internet of Things, i.e., every object can be uniquely identified in an Internet-like way. In the future, many individual RFID systems are likely to be integrated into a few exascale RFID systems. In an integrated RFID system, service providers (SPs) that offer RFID-based data service and clients that use the data service are different organizations. As a consequence, quality of data in terms of authenticity is of significant concern. In this paper, we first formulate a data verification problem in RFID systems and build a model of integrated RFID systems where multiple SPs and clients exist. Then, we propose two data verification protocols to ensure data generated by SPs associated with a particular tag and has not been modified. In addition, we implement our system as a prototype. The computer simulations, analyses, and testbeds based on the prototype all demonstrate that the proposed verifiable integrated RFID system achieves a high level of security and performance.

Privacy protection is the primary concern when RFID applications are deployed in our daily lives. Due to the computational power constraints of passive tags, non-encryption-based singulation protocols have been recently developed, in which wireless jamming is used. However, the existing private tag access protocols without shared secrets rely on impractical physical layer assumptions, and thus they are difficult to deploy. To tackle this issue, we first redesign the architecture of RFID system by dividing an RF reader into two different devices, an RF activator and a trusted shield device (TSD). Then, we propose a novel coding scheme, namely Random Flipping Random Jamming (RFRJ), to protect tags’ content. Unlike the past work, the proposed singulation protocol utilizes only the physical layer techniques that are already implemented. Analyses and simulation results validate our distributed architecture with the RFRJ coding scheme, which defends tags’ privacy against various adversaries including the random guessing attack, correlation attack, ghost-and-leech attack, and eavesdropping.

The strategy for node deployment to achieve multiple connectivity and coverage plays an important role in various wireless senor network applications. To alleviate the operational cost, the number of nodes to be deployed needs to be reduced. While the optimal $k$ -connectivity deployment patterns ( $k \le 6$ ) and the multiple $k$ -coverage problem ( $k \le 3$ ) have been extensively studied for 2-D networks, a general method to identify the optimal deployment pattern for any given sensor coverage requirement has yet to be found. Considering the ease of sensor deployment and operation, the deployment patterns should be identical and symmetric in the deployment region. This implies that the Voronoi diagram of the optimal deployment is a regular tessellation. Based on the fact that there exist only three regular tessellations, we propose a framework, namely, range elimination scheme (RES), to compute the optimal $k$ -coverage deployment pattern for any given $k$ value to accommodate various wireless sensor application requirements. We apply RES to show the optimal $k$ -coverage deployment patterns for $4 \le k \le 9$ . Our analytical and simulation results show that our proposed framework successfully identifies the optimal deployment patterns and significantly reduces the number of sensors to be deployed.

Mobile target detection is a significant application in wireless sensor networks (WSNs). In fact, it is rather expensive to require every part of the region of interest (RoI) to be covered in a large-scale WSN for target detection. Trap coverage has been proposed to trade off between sensing performance and the cost of sensor deployments. It restricts the farthest distance that a target can move without being detected rather than providing full coverage to the region. However, the results cannot be directly applied in a real WSN since the detection pattern of a sensor in practical scenarios follows a probabilistic sensing model. Moreover, the trap coverage model does not consider the various moving speeds of targets, which is important for trapping targets. To extend the concept of mobile target trapping into a real large-scale WSN, we analyze the detection probability of a mobile target in the sensor network theoretically and define probabilistic trap coverage in this paper, which restricts the farthest displacement of a mobile target with a detection probability less than the threshold. We develop the theory of circle graph, which can be generally applied in the area of intrusion detection such as trap coverage and barrier coverage. We further study the practical issue of how to schedule sensors to maximize the lifetime of a network while guaranteeing probabilistic trap coverage. A localized protocol is proposed to solve the problem, and the performance of the protocol is theoretically analyzed. The lower bound of lifetime acquired by the protocol is nearly half the optimum lifetime. To evaluate our design, we perform extensive simulations to compare our algorithm with the state-of-the-art solution and demonstrate the superiority of our algorithm.

Intrusion detection is a significant application in wireless sensor networks (WSNs). S. Kumar et al have introduced the concept of barrier coverage, which deploys sensors in a narrow belt region to guarantee that any intrusion across the region is to be detected. However, the practical issues have not been investigated such as scheduling sensors energy-efficiently while guaranteeing the detection probability of any intrusion across the region based on probabilistic sensing model. Besides, the intruders may be humans, animals, fighter planes or other things, which obviously have diverse moving speeds. In this paper, we analyze the detection probability of arbitrary path across the barrier of sensors theoretically and take the maximum speed of possible intruders into consideration since the sensor networks are designed for different intruders in different scenarios. Based on the theoretical analysis of detection probability, we formulate Minimum Weight e-Barrier Problem about how to schedule sensors energy-efficiently and prove it is NP-hard. We propose both global and local solutions to the problem. The global solution called Minimum Weight Barrier Algorithm is a bounded approximation algorithm, based on which a localized protocol for energy-efficient scheduling is designed. To evaluate our design, we analyze the performance of our approaches theoretically and also perform extensive simulations to demonstrate the effectiveness of our proposed algorithm.

To make a network last beyond the lifetime of an individual sensor node, redundant nodes must be deployed. What sleep-wake-up schedule can then be used for individual nodes so that the redundancy is appropriately exploited to maximize the network lifetime? We develop optimal solutions to both problems for the case when wireless sensor nodes are deployed to form an impenetrable barrier for detecting movements. In addition to being provably optimal, our algorithms work for nondisk sensing regions and heterogeneous sensing regions. Further, we provide an optimal solution for the more difficult case when the lifetimes of individual nodes are not equal. Developing optimal algorithms for both homogeneous and heterogeneous lifetimes allows us to obtain, by simulation, several interesting results. We show that even when an optimal number of sensor nodes has been deployed randomly, statistical redundancy can be exploited to extend the network lifetime by up to seven times. We also use simulation to show that the assumption of homogeneous lifetime can result in severe loss (two-thirds) of the network lifetime. Although these results are specifically for barrier coverage, they provide an indication of behavior for other coverage models.

In this paper, we study deployment patterns to achieve full coverage and k -connectivity (k ≤ 6) under different ratios of the sensor communication range (denoted by Rc) to the sensing range (denoted by Rs) for homogeneous wireless sensor networks (WSNs). In particular, we propose new patterns for 3- and 5-connectivity. We also discover that there exists a hexagon-based universally elemental pattern that can generate all known optimal patterns. The previously proposed Voronoi-based approach cannot be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon-based methodology. We prove the optimality of deployment patterns to achieve 3-connectivity, 4-connectivity, and 5-connectivity for certain ranges of Rc/Rs, respectively, and prove the optimality of deployment patterns to achieve 6-connectivity under all ranges of Rc/Rs.

Global barrier coverage, which requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice. In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage, even when the region of deployment is arbitrarily curved. Although local barrier coverage does not deterministically guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called localized barrier coverage protocol (LBCP). We prove that LBCP guarantees local barrier coverage and show that LBCP provides close to optimal enhancement in the network lifetime, while providing global barrier coverage most of the time. They outperform an existing algorithm called randomized independent sleeping (RIS) by up to six times.

In this paper, we study optimal deployment in terms of the number of sensors required to achieve four-connectivity and full coverage under different ratios of sensors' communication range (denoted by rc) to their sensing range (denoted by rs). We propose a new pattern, the Diamond pattern, which can be viewed as a series of evolving patterns. When rc/rs ? ?(3), the Diamond pattern coincides with the well-known triangle lattice pattern; when rc/rs ? ?(2), it degenerates to a Square pattern (i.e., a square grid). We prove that our proposed pattern is asymptotically optimal when rc/rs > ?(2) to achieve four-connectivity and full coverage. We also discover another new deployment pattern called the Double-strip pattern. This pattern provides a new aspect to research on optimal deployment patterns. Our work is the first to propose an asymptotically optimal deployment pattern to achieve four-connectivity and full coverage for WSNs. Our work also provides insights on how optimal patterns evolve and how to search for them.

Sensors may fail due to various reasons such as heat, malicious activity, environmental hazards, extended use, and lack of power. As more and more sensors fail, certain desired properties such as barrier coverage will diminish and eventually fall below a desired level. In such a case, the network will have to be repaired. It is therefore desirable to have mechanisms to monitor network properties. In this article, we are interested in measuring the quality of barrier coverage, which is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. In the literature, researchers only consider whether or not a sensor network provides barrier coverage. This is equivalent to measuring its quality as either 0 or 1. We believe quality of barrier coverage is not binary and propose a metric for measuring it. If the measured quality is short of a desired value, we further identify all local regions that need to be repaired. The identified regions are minimal in the sense that if one of them is not repaired then the resulting network will still be short of quality. We also discuss how to actually repair a region.

The IEEE 802.11 standards support the peer-to-peer mode Independent Basic Service Set (IBSS), which is an ad hoc network with all its stations within each other's transmission range. In an IBSS, it is important that all stations are synchronized to a common clock. Synchronization is essential for the MAC layer power management. Also, if frequency hopping spread spectrum is used in the physical layer, synchronization is needed to ensure that all stations "hop" at the same time. This paper evaluates the synchronization mechanism as specified in the IEEE 802.11 standards. Through rigorous analysis, it is shown that when the number of stations in an IBSS is not very small, there is a non-negligible probability that stations may get out of synchronization. The more stations, the higher probability of asynchronism. In this sense, the current IEEE 802.11 synchronization algorithm does not scale; it cannot support a large-scale IBSS.To alleviate the asynchronism problem, this paper proposes a simple remedy to the 802.11 algorithm. The resulting algorithm enjoys many nice properties--it is compatible, scalable, effective, mobility-friendly and simple. We are able to exceed the industry expectation of time accuracy (maximum clock offset under 12 µs) without any change of beacon format.