Expander graph based key distribution mechanisms in wireless sensor networks

Secure communications between large number of sensor nodes that are randomly scattered over a hostile territory, necessitate efficient key distribution schemes. However, due to limited resources at sensor nodes such schemes cannot be based on post deployment computations. Instead, pairwise (symmetric) keys are required to be pre-distributed by assigning a list of keys, (a.k.a. key-chain), to each sensor node. If a pair of nodes does not have a common key after deployment then they must find a key-path with secured links. The objective is to minimize the keychain size while (i) maximizing pairwise key sharing probability and resilience, and (ii) minimizing average key-path length. This paper presents a deterministic key distribution scheme based on Expander Graphs. It shows how to map the parameters (e.g., degree, expansion, and diameter) of a Ramanujan Expander Graph to the desired properties of a key distribution scheme for a physical network topology.

Design and analysis of key management schemes for distributed wireless sensor networks

Secure communications in distributed Wireless Sensor Networks (WSN) operating under adversarial conditions necessitate efficient key management schemes. In the absence of a priori knowledge of post-deployment network configuration and due to limited resources at sensor nodes, key management schemes cannot be based on post-deployment computations. Instead, a list of keys, called a key-chain, is distributed to each sensor node before the deployment. For secure communication, either two nodes should have a key in common in their key-chains, or they should establish a key through a secure-path on which every link is secured with a key. We first provide a comparative survey of well known key management solutions for WSN. Probabilistic, deterministic and hybrid key management solutions are presented, and they are compared based on their security properties and re-source usage. We provide a taxonomy of solutions, and identify trade-offs in them to conclude that there is no one size-fits-all solution. Second, we design and analyze deterministic and hybrid techniques to distribute pair-wise keys to sensor nodes before the deployment. We present novel deterministic and hybrid approaches based on combinatorial design theory and graph theory for deciding how many and which keys to assign to each key-chain before the sensor network deployment. Performance and security of the proposed schemes are studied both analytically and computationally. Third, we address the key establishment problem in WSN which requires key agreement algorithms without authentication are executed over a secure-path. The length of the secure-path impacts the power consumption and the initialization delay for a WSN before it becomes operational. We formulate the key establishment problem as a constrained bi-objective optimization problem, break it into two sub-problems, and show that they are both NP-Hard and MAX-SNP-Hard. Having established inapproximability results, we focus on addressing the authentication problem that prevents key agreement algorithms to be used directly over a wireless link. We present a fully distributed algorithm where each pair of nodes can establish a key with authentication by using their neighbors as the witnesses.

An analytical model for performance evaluation of multimedia applications over EDCA in an IEEE 802.11e WLAN

We extend the modeling heuristic of (Harsha et al. 2006. In IEEE IWQoS 06, pp 178 - 187) to evaluate the performance of an IEEE 802.11e infrastructure network carrying packet telephone calls, streaming video sessions and TCP controlled file downloads, using Enhanced Distributed Channel Access (EDCA). We identify the time boundaries of activities on the channel (called channel slot boundaries) and derive a Markov Renewal Process of the contending nodes on these epochs. This is achieved by the use of attempt probabilities of the contending nodes as those obtained from the saturation fixed point analysis of (Ramaiyan et al. 2005. In Proceedings ACM Sigmetrics, `05. Journal version accepted for publication in IEEE TON). Regenerative analysis on this MRP yields the desired steady state performance measures. We then use the MRP model to develop an effective bandwidth approach for obtaining a bound on the size of the buffer required at the video queue of the AP, such that the streaming video packet loss probability is kept to less than 1%. The results obtained match well with simulations using the network simulator, ns-2. We find that, with the default IEEE 802.11e EDCA parameters for access categories AC 1, AC 2 and AC 3, the voice call capacity decreases if even one streaming video session and one TCP file download are initiated by some wireless station. Subsequently, reducing the voice calls increases the video downlink stream throughput by 0.38 Mbps and file download capacity by 0.14 Mbps, for every voice call (for the 11 Mbps PHY). We find that a buffer size of 75KB is sufficient to ensure that the video packet loss probability at the QAP is within 1%.

Analytical models for capacity estimation of IEEE 802.11 WLANs using DCF for internet applications

We provide analytical models for capacity evaluation of an infrastructure IEEE 802.11 based network carrying TCP controlled file downloads or full-duplex packet telephone calls. In each case the analytical models utilize the attempt probabilities from a well known fixed-point based saturation analysis. For TCP controlled file downloads, following Bruno et al. (In Networking '04, LNCS 2042, pp. 626-637), we model the number of wireless stations (STAs) with ACKs as a Markov renewal process embedded at packet success instants. In our work, analysis of the evolution between the embedded instants is done by using saturation analysis to provide state dependent attempt probabilities. We show that in spite of its simplicity, our model works well, by comparing various simulated quantities, such as collision probability, with values predicted from our model. Next we consider N constant bit rate VoIP calls terminating at N STAs. We model the number of STAs that have an up-link voice packet as a Markov renewal process embedded at so called channel slot boundaries. Analysis of the evolution over a channel slot is done using saturation analysis as before. We find that again the AP is the bottleneck, and the system can support (in the sense of a bound on the probability of delay exceeding a given value) a number of calls less than that at which the arrival rate into the AP exceeds the average service rate applied to the AP. Finally, we extend the analytical model for VoIP calls to determine the call capacity of an 802.11b WLAN in a situation where VoIP calls originate from two different types of coders. We consider N-1 calls originating from Type 1 codecs and N-2 calls originating from Type 2 codecs. For G711 and G729 voice coders, we show that the analytical model again provides accurate results in comparison with simulations.

Online association policies in IEEE 802.11 WLANs

In this paper, we study the performance of client-Access Point (AP) association policies in IEEE 802.11 based WLANs. In many scenarios, clients have a choice of APs with whom they can associate. We are interested in finding association policies which lead to optimal system performance. More specifically, we study the stability of different association policies as a function of the spatial distribution of arriving clients. We find for each policy the range of client arrival rates for which the system is stable. For small networks, we use Lyapunov function methods to formally establish the stability or instability of certain policies in specific scenarios. The RAT heuristic policy introduced in our prior work is shown to have very good stability properties when compared to several other natural policies. We also validate our analytical results by detailed simulation employing the IEEE 802.11 MAC.

OPSM - Opportunistic Power Save mode for Infrastructure IEEE 802.11 WLAN

We focus on the energy spent in radio communication by the stations (STAs) in an IEEE 802.11 infrastructure WLAN. All the STAs are engaged in web browsing, which is characterized by a short file downloads over TCP, with short duration of inactivity or think time in between two file downloads. Under this traffic, Static PSM (SPSM) performs better than CAM, since the STAs in SPSM can switch to low power state (sleep) during think times while in CAM they have to be in the active state all the time. In spite of this gain, performance of SPSM degrades due to congestion, as the number of STAs associated with the access point (AP) increases. To address this problem, we propose an algorithm, which we call opportunistic PSM (OPSM). We show through simulations that OPSM performs better than SPSM under the aforementioned TCP traffic. The performance gain achieved by OPSM over SPSM increases as the mean file size requested by the STAs or the number of STAs associated with the AP increases. We implemented OPSM in NS-2.33, and to compare the performance of OPSM and SPSM, we evaluate the number of file downloads that can be completed with a given battery capacity and the average time taken to download a file.

Experimental validation of analytical performance models for IEEE 802.11 networks

We consider the simplest IEEE 802.11 WLAN networks for which analytical models are available and seek to provide an experimental validation of these models. Our experiments include the following cases: (i) two nodes with saturated queues, sending fixed-length UDP packets to each other, and (ii) a TCP-controlled transfer between two nodes. Our experiments are based entirely on Aruba AP-70 access points operating under Linux. We report our observations on certain non-standard behavior of the devices. In cases where the devices adhere to the standards, we find that the results from the analytical models estimate the experimental data with a mean error of 3-5%.

Network Coding for TCP Throughput Enhancement over a Multi-Hop wireless Network

The poor performance of TCP over multi-hop wireless networks is well known. In this paper we explore to what extent network coding can help to improve the throughput performance of TCP controlled bulk transfers over a chain topology multi-hop wireless network. The nodes use a CSMA/ CA mechanism, such as IEEE 802.11’s DCF, to perform distributed packet scheduling. The reverse flowing TCP ACKs are sought to be X-ORed with forward flowing TCP data packets. We find that, without any modification to theMAC protocol, the gain from network coding is negligible. The inherent coordination problem of carrier sensing based random access in multi-hop wireless networks dominates the performance. We provide a theoretical analysis that yields a throughput bound with network coding. We then propose a distributed modification of the IEEE 802.11 DCF, based on tuning the back-off mechanism using a feedback approach. Simulation studies show that the proposed mechanism when combined with network coding, improves the performance of a TCP session by more than 100%.

An Empirical Analysis of Heterogeneity in IEEE 802.11 MAC Protocol Implementations and its Implications

Wireless LAN (WLAN) market consists of IEEE 802.11 MAC standard conformant devices (e.g., access points (APs), client adapters) from multiple vendors. Certain third party certifications such as those specified by the Wi-Fi alliance have been widely used by vendors to ensure basic conformance to the 802.11 standard, thus leading to the expectation that the available devices exhibit identical MAC level behavior. In this paper, however, we present what we believe to be the first ever set of experimental results that highlight the fact that WLAN devices from different vendors in the market can have heterogeneous MAC level behavior. Specifically, we demonstrate with examples and data that in certain cases, devices may not be conformant with the 802.11 standard while in other cases, they may differ in significant details that are not a part of mandatory specifications of the standard. We argue that heterogeneous MAC implementations can adversely impact WLAN operations leading to unfair bandwidth allocation, potential break-down of related MAC functionality and difficulties in provisioning the capacity of a WLAN. However, on the positive side, MAC level heterogeneity can be useful in applications such as vendor/model level device fingerprinting.

Frequency diversity measurements at 2.4 GHz for wireless sensor networks deployed in tunnels

Wireless Sensor Networks (WSNs) which utilise IEEE 802.15.4 technology operate primarily in the 2.4 GHz globally compatible ISM band. However, the wireless propagation channel in this crowded band is notoriously variable and unpredictable, and it has a significant impact on the coverage range and quality of the radio links between the wireless nodes. Therefore, the use of Frequency Diversity (FD) has potential to ameliorate this situation. In this paper, the possible benefits of using FD in a tunnel environment have been quantified by performing accurate propagation measurements using modified and calibrated off-the-shelf 802.15.4 based sensor motes in the disused Aldwych underground railway tunnel. The objective of this investigation is to characterise the performance of FD in this confined environment. Cross correlation coefficients are calculated from samples of the received power on a number of frequency channels gathered during the field measurements. The low measured values of the cross correlation coefficients indicate that applying FD at 2.4 GHz will improve link performance in a WSN deployed in a tunnel. This finding closely matches results obtained by running a computational simulation of the tunnel radio propagation using a 2D Finite-Difference Time-Domain (FDTD) method. ©2009 IEEE.

A condition monitoring platform using COTS wireless sensor networks - Lessons and experience

Developments in Micro-Electro-Mechanical Systems (MEMS), wireless communication systems and ad-hoc networking have created new dimensions to improve asset management not only during the operational phase but throughout an asset's lifecycle based on using improved quality of information obtained with respect to two key aspects of an asset: its location and condition. In this paper, we present our experience as well as lessons learnt from building a prototype condition monitoring platform to demonstrate and to evaluate the use of COTS wireless sensor networks to develop a prototype condition monitoring platform with the aim of improving asset management by providing accurate and real-time information. © 2010 IEEE.

Practical wireless sensor networks power consumption metrics for building energy management applications

The power consumption of wireless sensor networks (WSN) module is an important practical concern in building energy management (BEM) system deployments. A set of metrics are created to assess the power profiles of WSN in real world condition. The aim of this work is to understand and eventually eliminate the uncertainties in WSN power consumption during long term deployments and the compatibility with existing and emerging energy harvesting technologies. This paper investigates the key metrics in data processing, wireless data transmission, data sensing and duty cycle parameter to understand the system power profile from a practical deployment prospective. Based on the proposed analysis, the impacts of individual metric on power consumption in a typical BEM application are presented and the subsequent low power solutions are investigated.

Temporal variations of IEEE 802.11b signal strengths in an in-building environment

Recent popularity of the IEEE 802.11b Wireless Local Area Networks (WLANs) in a host of current-day applications has instigated a suite of research challenges. The 802.11b WLANs are highly reliable and wide spread. In this work, we study the temporal characteristics of RSSI in the real-working environment by conducting a controlled set of experiments. Our results indicate that a significant variability in the RSSI can occur over time. Some of this variability in the RSSI may be due to systematic causes while the other component can be expressed as stochastic noise. We present an analysis of both these aspects of RSSI. We treat the moving average of the RSSI as the systematic causes and the noise as the stochastic causes. We give a reasonable estimate for the moving average to compute the noise accurately. We attribute the changes in the environment such as the movement of people and the noise associated with the NIC circuitry and the network access point as causes for this variability. We find that the results of our analysis are of primary importance to active research areas such as location determination of users in a WLAN. The techniques used in some of the RF-based WLAN location determination systems, exploit the characteristics of the RSSI presented in this work to infer the location of a wireless client in a WLAN. Thus our results form the building blocks for other users of the exact characteristics of the RSSI.

Performance analysis of an improved power-saving medium access protocol for IEEE 802.11 point coordination function WLAN

Wireless enabled portable devices must operate with the highest possible energy efficiency while still maintaining a minimum level and quality of service to meet the user's expectations. The authors analyse the performance of a new pointer-based medium access control protocol that was designed to significantly improve the energy efficiency of user terminals in wireless local area networks. The new protocol, pointer controlled slot allocation and resynchronisation protocol (PCSAR), is based on the existing IEEE 802.11 point coordination function (PCF) standard. PCSAR reduces energy consumption by removing the need for power saving stations to remain awake and listen to the channel. Using OPNET, simulations were performed under symmetric channel loading conditions to compare the performance of PCSAR with the infrastructure power saving mode of IEEE 802.11, PCF-PS. The simulation results demonstrate a significant improvement in energy efficiency without significant reduction in performance when using PCSAR. For a wireless network consisting of an access point and 8 stations in power saving mode, the energy saving was up to 31% while using PCSAR instead of PCF-PS, depending upon frame error rate and load. The results also show that PCSAR offers significantly reduced uplink access delay over PCF-PS while modestly improving uplink throughput.