Analytical and quantitative characterization of wireless sensor networks.

In this thesis we characterize key properties of wireless sensor networks (WSN) by analytical and quantitative methods. These include the link-layer bit error rate (BER) process, network lifetime and topology. For the analysis of the BER process, we collected a large set of packet traces over IEEE 802.15.4 links. Our packet traces distinguish themselves from other data sets in that they record channel state information (CSI) as well as full and partial packet erasures. A channel model, which is conditioned on observed CSI, is developed. This conditional model reduces the variance of the BER's distribution by one order of magnitude. Packet traces are also analyzed to determine memory length of bit errors. Correlation analysis of bit and symbol level traces reveals that memory length of errors in all traces is 2 bits and 2 symbols, respectively. For packet-level traces consisting of BER measurements of individual packets the traditional correlogram based analysis fails and so we introduce relative mutual information (RMI) as a more robust method for measuring channel memory. RMI based analysis of packet traces shows that memory length of the BER ranges from 0 to 2sec. The research on the network lifetime problem proposes joint minimization of mean and variance of sensor power consumption rates as an alternative to the minimax formulation of the lifetime problem in WSN. This proposed statistical optimization objective better fits the vision of WSNs consisting of large numbers of inexpensive, redundant, disposable sensors than the minimax formulation which focuses on the top power consuming node. We formulate this problem in quadratic program (QP) form. To avoid scalability issues of using a QP, an approximate dynamic program (DP) formulation of lower complexity rooted in operational rate-distortion theory is developed. For a randomly generated WSN of 100 nodes DP exhibits upto 44% reduction in variance at the cost of 19% increase in its mean, with many intermediate operating points of higher benefit/cost ratios to choose from. The research on topological characteristics of WSNs explores the possibility of building WSNs with small-world topologies that combine desirable properties of Euclidean/lattice graphs with those of random graphs. An analytical model is developed to explain the phase difference in characteristic path length and clustering coefficient in lattice graphs when shortcut links of limited range are used. We test and implement a software based system for commercial-off-the-shelf motes that increases communication range of links in WSNs using cooperative communication and diversity combining. A trace based implementation demonstrates proof-of-concept of its ability to reduce the fraction of packets with errors on a channel from 20% down to 1% and reduce the BER of packets that cannot be corrected. This is followed by an implementation on the Crossbow Imote2 sensor mote. Results from the mote based implementation show an increase in packet reception rate from 22--30% to 73--76%. Finally, we develop a centrality measure to identify well connected clusters of central nodes for the placement of network resources. For mesh network topologies that are characteristic of WSNs, eigenvector centrality (EVC) consistently fails to identify more than a single, arbitrarily located cluster of nodes as the most central. We introduce principal component centrality (PCC), a node centrality inspired by the Karhunen Loeve transform/principal component analysis. We demonstrate PCC's ability to identify a larger number of central hub nodes than EVC, depending on the number of features used in its computation.