Abstract Location‐related mobile social network services are popular nowadays, and their methods to obtain end users’ location information are based on people's self‐report location claims, using mobile devices to check positions and send them back to the service providers. However, this mechanism has a serious vulnerability that makes malicious users be able to access restricted resource by transmitting fake locations. Both academic and industrial researchers are recently aware of this problem's importance since the commercialized trend of location‐related mobile social network services. To address this issue, we propose mobile phone‐based physical‐social location, a mobile phone‐based location proof system to verify users’ location claims and defend various fake location information. Our core idea is that a user's location claim can be proved by a set of selective physical encountered people serving as “witnesses” who are co‐located with him/her in that area. The system is composed of proof generation and verification. In the proof generation phase, we leverage a certain number of co‐located people to generate certificates as location proofs during their encounters via bluetooth interface. In the verification phase, we propose an efficient verification scheme to make our system accurate and adaptive. We have implemented the MPSL system using real world Nokia N82 (Nokia, Espoo, Finland) phones. Our experimental results show that our mobile phone‐based system can achieve high verification accuracy and good performance. Copyright © 2014 John Wiley & Sons, Ltd.

In this paper, we propose E-Shadow, a distributed mobile phone-based local social networking system. E-Shadow has two main components: (1) Local profiles. They enable E-Shadow users to record and share their names, interests, and other information with fine-grained privacy controls. (2) Mobile phone based local social interaction tools. E-Shadow provides mobile phone software that enables rich social interactions. The software maps proximate users’ local profiles to their human owners and enables user communication and content sharing. We have designed and implemented E-Shadow on mobile phones. In our E-Shadow system, we allow users to perform dynamic and layered information publishing, making use of interpersonal relevance in space and time. Our system also provides a mechanism to help users perform direction-driven localization of an E-Shadow and match it with its owner. Experiments on real world Windows Mobile phones and large-scale simulations show that our system disseminates information efficiently and helps receivers find the direction of a specific E-Shadow with accuracy. We believe our E-Shadow concept and system can lead to a more tightly-knit temporary community in one’s physical vicinity.

In this article, we address a new unexplored problem: what are the optimal patterns to achieve connected coverage in wireless networks with directional antennas. As their name implies, directional antennas can focus their transmission energy in a certain direction. This feature leads to lower cross-interference and larger communication distance. It has been shown that, with proper scheduling mechanisms, directional antennas may substantially improve networking performance in wireless networks. In this article, we propose a set of deployment patterns to achieve full coverage and up to 2-connectivity under two different antenna models, namely the sector model and the knob model. These patterns are optimal under most combinations of communication and sensing ranges. We also introduce with detailed analysis several fundamental theorems and conjectures. Finally, we examine a more realistic physical model, where there might be strong interference and both the sensing range and the communication range might be irregular. The results show that our designed patterns work well even in unstable and fickle physical environments.

In this paper, we propose a new type of incentive-driven and privacy-preserving systems for large-scale message dissemination in mobile networks. To distribute incentives which encourage forwarding behaviors, such as monetary rewards, we want to keep track of the forwarder list. In our algorithms, we rely on a Probabilistic one-ownership forwarding algorithm to record the list, so that the exchanged messages can be kept short and privacy preserving. More specifically, only one hop of forwarder information, instead of the complete list, is recorded, and the information is updated probabilistically following two ownership flipping models, namely, One-Flip and Always-Flip models. We also use a Bluetooth Service Discovery Protocol (SDP) toolkit to enable fast, configuration-free message exchange. Throughout the paper, we use coupon as a typical type of message to illustrate the core ideas. We have implemented the coupon dissemination system in Java ME. Our experiments on real-world mobile phones, such as Nokia and Samsung phones, and large-scale simulations show that our system is efficient in peer-to-peer message distribution and capable of massive deployment. We believe our key methodology can serve as a general framework for facilitating information propagation on mobile phones, where incentives and privacy protection are both essential.

In this paper, we study the optimal deployment pattern problem in wireless sensor networks (WSNs). We propose a new set of patterns, particularly when sensors' communication range ($r_{\rm c}$) is relatively small compared to their sensing range ($r_{\rm s}$), and prove their optimality. In this study, we discover an interesting phenomenon—pattern mutation. To the best of our knowledge, this is the first time that mutation in pattern deployments has been discovered. This phenomenon, which contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern deployment, significantly furthers our understanding of optimal patterns in WSNs.

In this paper, we propose E-Shadow, a distributed mobile phone-based local social networking system. E-Shadow has two main components: (1) Local profiles. They enable EShadow users to record and share their names, interests, and other information with fine-grained privacy controls. (2) Mobile phone based local social interaction tools. E-Shadow provides mobile phone software that enables rich social interactions. The software maps proximate users' local profiles to their human owners and enables user communication and content sharing. We have designed and implemented E-Shadow on mobile phones. In our E-Shadow system, we allow users to perform dynamic and layered information publishing, making use of interpersonal relevance. Our system also provides a mechanism to help users perform direction-driven localization of an E-Shadow and match it with its owner. Experiments on real world Windows Mobile phones and large-scale simulations show that our system disseminates information efficiently and helps receivers find the direction of a specific E-Shadow with accuracy. We believe our E-Shadow concept and system can lead to a more tightly-knit temporary community in one's physical vicinity.

In this paper, we address a new unexplored problem - what are the optimal patterns to achieve connected coverage in wireless networks with directional antennas. As their name implies, directional antennas can focus their transmission energy in a certain direction. This feature leads to lower cross-interference and larger communication distance. It has been shown that with proper scheduling mechanisms, directional antennas may substantially improve networking performance in wireless networks. In this paper, we propose a set of optimal patterns to achieve full coverage and global connectivity under two different antenna models, i.e., the sector model and the knob model. We also introduce with detailed analysis several fundamental theorems and conjectures. Finally, we examine a more realistic physical model, where there might be strong interference, and both the sensing range and the communication range might be irregular. The results show that our designed patterns work well even in unstable and fickle physical environments.

In this paper, we propose P3-coupon, a Prompt and Privacy-preserving electronic coupon distribution system based on a Probabilistic one-ownership forwarding algorithm. In this algorithm, only one hop of forwarder (coupon owner) information instead of the complete forwarder list is recorded to keep the coupon short and privacy-preserving. Such information is updated probabilistically following two ownership flipping models, namely, One-Flip and Always-Flip models. We also use a Bluetooth Service Discovery Protocol (SDP) toolkit to enable fast, configuration-free coupon exchange. We have implemented the system in Java ME. Our experiments on real world mobile phones, such as Nokia and Samsung phones, and large scale simulations show that our system is efficient in peer to peer coupon distribution and capable of massive deployment. We believe our key methodology can serve as a general framework for facilitating information propagation on mobile phones, which requires promptness and privacy protection.

Many key predistribution (KP) protocols have been proposed and are well accepted in randomly deployed wireless sensor networks (WSNs). Being distributed and localized, they are perceived to be scalable as node density and network dimension increase. While it is true in terms of communication/computation overhead, their scalability in terms of security performance is unclear. In this paper, we conduct a detailed study on this issue. In particular, we define a new metric called Resilient Connectivity (RC) to quantify security performance in WSNs. We then conduct a detailed analytical investigation on how KP protocols scale with respect to node density and network dimension in terms of RC in randomly deployed WSNs. Based on our theoretical analysis, we state two scaling laws of KP protocols. Our first scaling law states that KP protocols are not scalable in terms of RC with respect to node density. Our second scaling law states that KP protocols are not scalable in terms of RC with respect to network dimension. In order to deal with the unscalability of the above two scaling laws, we further propose logical and physical group deployment, respectively. We validate our findings further using extensive theoretical analysis and simulations.

In many Wireless Sensor Networks (WSNs), providing end to end secure communications between sensors and the sink is important for secure network management. While there have been many works devoted to hop by hop secure communications, the issue of end to end secure communications is largely ignored. In this paper, we design an end to end secure communication protocol in randomly deployed WSNs. Specifically, our protocol is based on a methodology called differentiated key pre-distribution. The core idea is to distribute different number of keys to different sensors to enhance the resilience of certain links. This feature is leveraged during routing, where nodes route through those links with higher resilience. Using rigorous theoretical analysis, we derive an expression for the quality of end to end secure communications, and use it to determine optimum protocol parameters. Extensive performance evaluation illustrates that our solutions can provide highly secure communications between sensor nodes and the sink in randomly deployed WSNs. We also provide detailed discussion on a potential attack (i.e. biased node capturing attack) to our solutions, and propose several countermeasures to this attack.

In this paper, we study the optimal deployment pattern problem in wireless sensor networks (WSNs). We propose a new set of patterns, particularly when sensors' communication range (rc) is relatively small compared with their sensing range (rs), and prove their optimality among regular patterns. In this study, we discover a surprising and interesting phenomenon-pattern mutation. This phenomenon contradicts the conjecture presented in a previous work that there exists a universal elemental pattern among optimal pattern evolution and that pattern evolution is continuous. For example, we find mutation happens among the patterns for full-coverage and 3-connectivity when rc/rs= 1.0459, among the patterns for full-coverage and 4-connectivity when rc/rs= 1.3903, and among the patterns for full-coverage and 5-connectivity when rc/rs= 1.0406. To the best of our knowledge, this is the first time that mutation in pattern evolution has been discovered. Also, our work further completes the exploration of optimal patterns in WSNs.

Malicious shellcodes are segments of binary code disguised as normal input data. Such shellcodes can be injected into a target process's virtual memory. They overwrite the process's return addresses and hijack control flow. Detecting and filtering out such shellcodes is vital to prevent damage. In this paper, we propose a new malicious shellcode detection methodology in which we take snapshots of the process's virtual memory before input data are consumed, and feed the snapshots to a malicious shellcode detector. These snapshots are used to instantiate a runtime environment that emulates the target process's input data consumption to monitor shellcodes' behaviors. The snapshots can also be used to examine the system calls that shellcodes invoke, these system call parameters, and the process's execution flow. We implement a prototype system in Debian Linux with kernel version 2.6.26. Our extensive experiments with real traces and thousands of malicious shellcodes illustrate our system's performance with low overhead and few false negatives and few false positives.

Low-connectivity and full-coverage three dimensional Wireless Sensor Networks (WSNs) have many real-world applications. By low connectivity, we mean there are at least k disjoint paths between any two sensor nodes in a WSN, where k ≤ 4. In this paper, we design a set of patterns to achieve 1-, 2-, 3- and 4-connectivity and full-coverage, and prove their optimality under any value of the ratio of communication range rcover sensing range rs, among regular lattice deployment patterns. We further investigate the evolutions among all the proposed low-connectivity patterns. Finally, we study the proposed patterns under several practical settings.

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.

In this paper, we study deployment patterns to achieve full coverage andk-connectivity(k≤ 6) under different ratios of the sensor communication range (denoted byRc) to the sensing range (denoted byRs) 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 ofRc/Rs, respectively, and prove the optimality of deployment patterns to achieve 6-connectivity under all ranges ofRc/Rs.

In this paper, we study the problem of constructing full-coverage three dimensional networks with multiple connectivity. We design a set of patterns for full coverage and two representative connectivity requirements, i.e. 14- and 6-connectivity. We prove their optimality under any ratio of the communication range over the sensing range among regular lattice deployment patterns. We also conduct a study on the proposed patterns under practical settings. To our knowledge, our work is the first one that provides deployment patterns with proven optimality that achieve both coverage and connectivity in three dimensional networks.

In this paper, we introduce a new type of coverage for wireless sensor networks, called Directed Coverage (D-coverage). Basically, D-coverage is the coverage provided by a sensor network monitoring an area between two boundaries, through which the intruder attempts to penetrates the area. We also study how to measure the quality of D-coverage. Our first evaluation approach is a projection-based simple approach, while our second approach is a more comprehensive Markov chain based approach. Our evaluation approaches can accurately evaluate the quality and provide good guidelines for sensor network deployment and run-time repair.

Smartphones have been widely used in recent years due to their capabilities of supporting many applications from simple Short Message Service messages to complicated Location-based services. It is challenging for smartphones to enable their end users to manage all applications in all possible use cases to protect privacy or sensitive data. However, the security model for smartphone users is still a two-state model in which they can do anything or absolutely nothing, and it is no longer suitable. In this paper, we propose DiffUser, a differentiated user access control model to enhance smartphone security and user privacy. DiffUser classifies smartphone users based on certain sets of user access privileges. We implement a prototype of DiffUser on real-world T-Mobile G1 smartphones. The evaluation results show that our system is lightweight and flexible.

Low-connectivity and full-coverage three dimensional Wireless Sensor Networks (WSNs) have many real-world applications. By low connectivity, we mean there are at least k disjoint paths between any two sensor nodes in a WSN, where k ≤ 4. In this paper, we design a set of patterns for these networks. In particular, we design and prove the optimality of 1- and 2-connectivity patterns under any value of the ratio of communication range rc over sensing range rs, among regular lattice deployment patterns. We further propose a set of patterns to achieve 3- and 4-connectivity patterns and investigate the evolutions among all the proposed low-connectivity patterns. Finally, we study the proposed patterns under several practical settings.

The current 802.11i standard can provide data confidentiality, integrity and mutual authentication in enterprise Wireless Local Area Networks (WLANs). However, secure communication can only be provided after successful authentication and a robust security network association is established. In general, the wireless link layer is not protected by the current standard in WLANs, which leads to many possible attacks, especially in public open-access wireless networks. We argue that regardless of the type of network under consideration, link-layer protection and data confidentiality are of great importance in wireless applications. In this paper, we first identify and analyze the security issues ignored by the current 802.11 security standard. Then we propose our solution to patch the current 802.11i standard and address all those issues with a new dummy authentication key-establishment algorithm. Dummy means no real authentication for a user. In dummy authentication, we apply public-key cryptography's key-establishment technique to the 802.11 MAC protocol. Our solution can provide link-layer data encryption in open-access wireless networks, separate session encryption keys for different users, and protection for important frames such as management and null data frames as well as Extensible Authentication Protocol (EAP) messages.

Securely authenticating a human user without assistance from any auxiliary device in the presence of powerful passive adversaries is an important and challenging problem. Passive adversaries are those that can passively monitor, intercept, and analyze every part of the authentication procedure, except for an initial secret shared between the user and the server. In this paper, we propose a new secure authentication scheme called predicate-based authentication service (PAS). In this scheme, for the first time, the concept of a predicate is introduced for authentication. We conduct analysis on the proposed scheme and implement its prototype system. Our analytical data and experimental data illustrate that the PAS scheme can simultaneously achieve a desired level of security and user friendliness.

Regression or least squares fitting is an important problem in statistics, data mining and many other applications. In recent years, basis functions derived from the underlying geometry of data, primarily Laplacian eigenfunctions, have attracted much interest. In this paper, we present a new framework based on adaptive Laplacian eigenfunctions and show the benefit of using a time-varying basis in regression analysis.

We study the issue of optimal deployment to achieve four connectivity and full coverage for wireless sensor networks (WSNs) under different ratios of sensors' communication range (denoted by rc) to their sensing range (denoted by rs). We propose a "Diamond" pattern, which can be viewed as a series of different evolving patterns. When rc/rsges radic3, the Diamond pattern coincides with the well-known triangle lattice pattern; when rc/rsges radic2, it degenerates to a "Square" pattern. We prove the Diamond pattern to be asymptotically optimal when rc/rsges radic2- Our work is the first to propose an asymptotically optimal deployment pattern to achieve four connectivity and full coverage for WSNs. We hope our work will provide some insights on how optimal patterns evolve and how to search for them.

In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs. With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k≤6) is complete, for the first time.

In this paper, we study the issue of sensor network deployment using limited mobility sensors. By limited mobility, we mean that the maximum distance that sensors are capable of moving to is limited. Given an initial deployment of limited mobility sensors in a field clustered into multiple regions, our deployment problem is to determine a movement plan for the sensors to minimize the variance in number of sensors among the regions and simultaneously minimize the sensor movements. Our methodology to solve this problem is to transfer the nonlinear variance/movement minimization problem into a linear optimization problem through appropriate weight assignments to regions. In this methodology, the regions are assigned weights corresponding to the number of sensors needed. During sensor movements across regions, larger weight regions are given higher priority compared to smaller weight regions, while simultaneously ensuring a minimum number of sensor movements. Following the above methodology, we propose a set of algorithms to our deployment problem. Our first algorithm is the optimal maximum flow-based (OMF) centralized algorithm. Here, the optimal movement plan for sensors is obtained based on determining the minimum cost maximum weighted flow to the regions in the network. We then propose the simple peak-pit-based distributed (SPP) algorithm that uses local requests and responses for sensor movements. Using extensive simulations, we demonstrate the effectiveness of our algorithms from the perspective of variance minimization, number of sensor movements, and messaging overhead under different initial deployment scenarios.

An important phase of sensor networks operation is deployment of sensors in the field of interest. Critical goals during sensor networks deployment include coverage, connectivity, load balancing, etc. A class of work has recently appeared, where mobility in sensors is leveraged to meet deployment objectives. In this paper, we study deployment of sensor networks using mobile sensors. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. We call such sensors as flip-based sensors. Given an initial deployment of flip-based sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage and minimize the number of flips. We propose a minimum-cost maximum-flow-based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors due to the limitations on sensor mobility

Abstract—Many wireless sensor network (WSN) applications demand secure communications. The random key predistribution ðRKPÞ protocol has been well accepted in achieving secure communications in WSNs. A host of key management protocols have been proposed based on the RKP protocol. However, due to the randomness in key distribution and strong constraint in key path construction, the RKP-based protocols can only be applied in highly dense networks, which are not always feasible in practice. In this paper, we propose a methodology called network decoupling to address this problem. With this methodology, a WSN is decoupled into a logical keysharing network and a physical neighborhood network, which significantly releases the constraint in key path construction of the RKP protocol. We design two new key management protocols, that is, RKP-DE and RKP-DEA, as well as a set of link and path dependency elimination rules in decoupled sensor networks. Our analytical and simulation data demonstrate the performance enhancement of our solutions from the perspective of connectivity and resilience and its applicability in nonhighly dense sensor networks. Index Terms—Wireless sensor networks, random key predistribution, network decoupling. 1

Secure communications are highly demanded by many wireless sensor network (WSN) applications. The random key pre-distribution (RKP) scheme has become well accepted in achieving secure communications in WSNs. However, due to its randomness in key distribution and strong constraint in key path construction, the RKP scheme can only be applied in highly dense networks, which are not always feasible in practice. In this paper, we propose a methodology called network decoupling to solve this problem. With this methodology, a wireless sensor network is decoupled into a logical key-sharing network and a physical neighborhood network, which significantly releases the constraint in key path construction of the RKP scheme. We design a secure neighbor establishment protocol (called RKP-DE) as well as a set of link and path dependency elimination rules in decoupled wireless sensor networks. Our analytical and simulation data demonstrate the performance enhancement of our solution and its applicability in non-highly dense wireless sensor networks

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of rc/rs, where rc is the communication radius, and rs is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when rc/rs < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.

This paper proposes a dynamic geographic hash table for data-centric storage (DCS) in sensor networks. In DCS systems, data storage locations are determined by data name. The storage locations are obtained through the use of a geographic hash table (GHT) that maps data names to geographic locations. Traditional DCS systems use a static hash function for this purpose, resulting in a static set of nodes serving the network throughout its lifetime. Hence, these nodes may experience unbalanced resource utilization problems and the network will not be capable of dealing with network dynamics such as new sensor deployments or runtime sensor failures. We address these problems by proposing a dynamic GHT solution that relies on two schemes: 1) a temporal-based geographic hash table to achieve overall load balancing among sensor nodes over time; and 2) a location selection scheme based on node contribution potential to proactively adapt the system to network dynamics. Our performance evaluations show that the dynamic GHT can alleviate the resource utilization problem of DCS systems and can prolong the network lifetime significantly

In this paper, we study the issue of mobility based sensor networks deployment. The distinguishing feature of our work is that the sensors in our model have limited mobilities. More specifically, the mobility in the sensors we consider is restricted to a flip, where the distance of the flip is bounded. Given an initial deployment of sensors in a field, our problem is to determine a movement plan for the sensors in order to maximize the sensor network coverage, and minimize the number of flips. We propose a minimum-cost maximum-flow based solution to this problem. We prove that our solution optimizes both the coverage and the number of flips. We also study the sensitivity of coverage and the number of flips to flip distance under different initial deployment distributions of sensors. We observe that increased flip distance achieves better coverage, and reduces the number of flips required per unit increase in coverage. However, such improvements are constrained by initial deployment distributions of sensors, due to the limitations on sensor mobility

An interest-based clustering peer-to-peer network (ICN) architecture is introduced in this paper. ICN uses a lot of Freenet mechanisms and is based on cache management. ICN is self-organizing, fully distributed, scalable, and logically hierarchical. In ICN, the upper level is bound by de Bruijn graph. Nodes in the lower level self-cluster based on interest. Through analysis and simulation, ICN shows good fault-tolerance, efficient data retrieval and resource usage as well as low overhead traffic.