.4; .l is. 2x . . h :1. 1...! . in BVFEHflWY :32. 2,. .‘r... 5.. \l 3.. fanny. .2. V ARI - . . ... n I} . $4.33 5. .. , 1 s i .mx‘ué‘weuu £1.32!!! 1 " ‘ II...“ III.- airpkmlj...¥ Its-”:5.“ .g I. l :t! . ct. . tiltitazatalvl v..‘.:lk:.. 2.51.1)..5. {i3 |I : u.» p ,algb- L... .. i.1..r..l....u...u..fl - ..:..2......§... iv...» uluflnwmufll’l‘lr. .... 31 . i unfizzhmpflhfl if... raw“ f n I. 3.3.x .ill irlié. :I 9351.33]; «9.! I. 72‘ If”? K 5“. l,..iE~"?_ARY Michigan State I University This is to certify that the dissertation entitled ANALYTICAL AND QUANTITATIVE CHARACTERIZATION OF WIRELESS SENSOR NETWORKS presented by MUHAMMAD USMAN ILYAS has been accepted towards fulfillment of the requirements for the Doctoral degree in Electrical Engineering flan/4 fl/é /Major VProfessor’ 5 Signature IZI/lé l/Zboct Date MSU is an Affirmative Action/Equal Opportunity Employer PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DAIEDUE DAIEDUE DAIEDUE 5/08 K:IProj/Acc&Pres/ClRC/DateDue.indd ANALYTICAL AND QUANTITATIVE CHARACTERIZATION OF ' WIRELESS SENSOR NETWORKS By Muhammad Usman Ilyas A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Electrical Engineering 2009 ABSTRACT ANALYTICAL AND QUANTITATIVE CHARACTERIZATION OF WIRELESS SENSOR NETWORKS By Muhammad Usman Ilyas 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 80215.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 2.360. 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 Eu- clidean / 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 im- plement a software based system for commercial-off-the—shelf motes that increases communication range of links in WSNs using cooperative communication and diver- sity 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 Loéve 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. COPYRIGHT Copyright by Muhammad Usman Ilyas 2009 DEDICATION To my wife, Ayesha and my daughter, Haadiya. ACKNOWLEDGMENT I would like to acknowledge my advisor Professor Hayder Radha for his years of support through the Ph.D. program, for his professional mentoring and counsel. I would also like to thank Professor Subir K. Biswas, Professor Tongtong Li and Pro— fessor Philip K. McKinley for the guidance and valuable feedback they provided as members of my PhD. program committee. I would like to acknowledge the Higher Education Commission of the government of Pakistan, the National Science Foundation and Michigan State University for gen- erously providing funding at different stages during my Ph.D. program. Many thanks to my colleagues at the WAVES lab Khayam, Shirish, Kiran, Sauleh, Sohraab, N ima, Rarni, Yongju, Moonseong, Ahmed and Aqeel for letting me bounce off ideas, many, many technical discussions and their company on our coffee rounds & all-nighters. I am also grateful to Khawar, Awais, Aparna, Keyur and Zubair for their friendships. None of this would have been possible without the constant support and encour- agement of my wife Ayesha. I would like to acknowledge Ayesha’s parents without whose active support and assistance I would not be at MSU. I am grateful to my parents whose years of investment in my education allowed me to pursue graduate studies. Finally, I want to acknowledge my lovely daughter Haadiya for being a reality check and bring balance merely by her presence. Muhammad Usman Ilyas vi As the area of your knowledge grows, so does the periphery of your ignorance. Neil deGrasse Tyson vii TABLE OF CONTENTS List of Tables ................................. List of Figures ................................ Introduction 1.1 Organization ............................... 1.2 Overview of Contributions ........................ Network Channel Capacity of IEEE 80215.4 Wireless Sensor Net- works Under Reachback 2.1 Introduction ................................ 2.2 System Model ............................... 2.2.1 Wireless Networking Standards for VVSNs ........... 2.2.2 Source & Channel Coding .................... 2.2.3 Power Consumption Model .................... 2.3 Channel Model .............................. 2.3.1 1-H0p Communication ...................... 2.3.2 Overlay Network Communication ................ 2.3.3 Sensor-To—Base Station Capacity ................ 2.4 Results and Analysis ........................... CSI Driven Model of BER Process on IEEE 802.15.4 Links 3.1 Introduction ................................ 3.1.1 Previous Work ........................ ' . . 3.2 Trace Collection Setup .......................... 3.2.1 Experimental Setup ........................ 3.2.2 Packet Payload .......................... 3.2.3 Trace Generation ......................... 3.2.4 Channel State Information .................... 3.2.5 Spectral and Environmental Diversity .............. 3.3 Correlation Analysis of CSI Measures .................. 3.4 CSI Driven BER Model ......................... 3.5 Model Evaluation ............................. 3.5.1 Variance Reduction ........................ 3.5.2 Dependence On Deployment Environment ........... 3.6 Conclusions ................................ xii t0 O1QDQDN03 1 17 18 19 24 27 28 33 34 35 37 37 38 39 39 44 45 50 52 52 53 56 4 Memory Properties of the Link-level BER Process in IEEE 802.15.4 Links 58 4.1 Introduction ................................ 59 4.2 Memory Length Measurement By Correlation Analysis ........ 61 4.2.1 Correlation Function ....................... 61 4.2.2 Correlograms of Bit and Symbol-level Traces .......... 64 4.2.3 Correlograms of Packet-level Traces ............... 64 4.3 Hurst Analysis of Packet-level BER Process .............. 67 4.3.1 Observations For MC Trace Set ................. 69 4.3.2 Observations For ME Trace Set ................. 71 4.4 Memory Length Measurement By Relative Mutual Information . . . . 71 4.4.1 Shannon Information Measures ................. 71 4.4.2 Description: Relative Mutual Information ........... 72 4.4.3 Discussion ............................. 76 4.5 Conclusions ................................ 78 5 A Statistical Measure Of Network Lifetime For Wireless Sensor Net- works 80 5.1 Introduction ................................ 81 5.2 Previous Work .............................. 82 5.3 Novelty Of Approach ........................... 83 5.4 Network Model .............................. 85 5.5 Quadratic Program Formulation ..................... 86 5.6 Results ................................... 91 5.7 Conclusions ................................ 92 6 A Dynamic Programming Approach to Maximizing Lifetime of Sen- sor Networks 95 6.1 Introduction ................................ 96 6.2 Previous Work .............................. 98 6.3 Network Model .............................. 99 6.3.1 Device Model ........................... 99 6.3.2 Link Model ............................ 100 6.4 Problem Formulation ........................... 102 6.5 Route Discovery .............................. 104 6.5.1 Bottleneck Edge Disjoint Paths ................. 106 6.5.2 Bottleneck Node Disjoint Paths ................. 106 6.5.3 Edge Disjoint Paths ....................... 106 6.5.4 Node Disjoint Paths ....................... 108 6.6 Dynamic Programming .......................... 108 6.6.1 Theoretical Background ..................... 109 , 6.6.2 Dynamic Programming Algorithm ................ 110 6.6.3 Computational Complexity of Finding Optimal Solution . . . 114 6.7 Performance Analysis ........................... 115 ix 6.7.1 Mean-Variance Trade-off ..................... 116 6.7.2 Spatial Redistribution of Energy ................. 119 6.8 Conclusions ................................ 122 Mean-Field Solution of Small-World Wireless Sensor Network Mod- els With Range Limited Shortcuts 127 7.1 Introduction ................................ 128 7.2 Background: Small-World Networks ................... 129 7.2.1 Characteristic Path Length ................... 131 7.2.2 Clustering Coefficient ....................... 131 7.2.3 Small World, Geometric and Random Graphs ......... 132 7.3 Small-World Topology Construction Methods for Wireless Networks . 133 7.3.1 Hybrid Sensor Network ...................... 133 7.3.2 Multi-radio Network ....................... 133 7.3.3 Receiver Side Cooperation .................... 134 7.4 Mean Field Analysis of Small-World W'ireless Networks ........ 135 7.4.1 Clustering Coefficient ....................... 135 7.4.2 Characteristic Path Length ................... 139 7.5 Observations ................................ 148 7.6 Conclusions ................................ 151 Enabling Cooperative Communication and Diversity Combination in IEEE 802.15.4 Wireless Networks Using Off-the—shelf Sensor Mote3157 8.1 Introduction ................................ 158 8.2 Related Work ............................... 161 8.3 SIMO Diversity Combining Techniques ................. 163 8.3.1 Selection Diversity ........................ 164 8.3.2 Equal Gain Diversity ....................... 166 8.3.3 Maximal Ratio Diversity ..................... 167 8.4 gPMSS Protocol ............................. 168 8.4.1 gPMSS Cluster Creation ..................... 169 8.4.2 Error-free Reception by at Least One Recipient ........ 171 8.4.3 Erroneous Reception by All Recipients ............. 172 8.5 Trace Based Proof of Concept ...................... 173 8.5.1 Experimental Setup ........................ 173 Packet Payload .......................... 174 Tiace Generation ......................... 175 8.5.2 Channel State Information .................... 176 8.5.3 Implementation Results ..................... 176 PER and PLR Analysis ..................... 178 BER Analysis ........................... 180 8.6 gPMSS Protocol Implementation .................... 181 8.7 Results and Analysis ........................... 183 8.7.1 Packet Reception Rate ...................... 183 x 8.7.2 Energy Per Packet ........................ 184 8.7.3 Packet Transmission Attempts .................. 188 8.8 Conclusions ................................ 189 9 Principal Component Centrality as a Measure of Node Centrality in Communication Networks 191 9.1 Introduction ................................ 192 9.2 Background ................................ 194 9.2.1 Degree Centrality ......................... 195 9.2.2 Closeness Centrality ....................... 195 9.2.3 Betweenness Centrality ...................... 196 9.2.4 Eigenvector Centrality ...................... 196 9.2.5 The Need for a New Centrality Measure ............ 198 9.3 Principal Component Centrality ..................... 200 9.4 Evaluation ................................. 203 9.4.1 Interpretation of Eigenvalues ................... 203 9.4.2 Interpretation of Eigenvectors .................. 205 9.4.3 Graphical Interpretation of PCC ................ 208 9.4.4 Effect of Number of Features on PCC .............. 211 9.5 Conclusions ................................ 212 10 Conclusions 214 10.1 Channel Modeling ............................. 215 10.2 Network Lifetime ............................. 216 10.3 WSN Topology .............................. 218 Bibliography ..................................................... 221 xi 2.1 3.1 3.2 3.3 3.4 3.6 6.1 6.2 8.1 8.2 8.3 LIST OF TABLES Tabular listing of relevant features of the three wireless networking technologies under consideration for use in WSNs ............ Traffic information and statistics collected in various studies. . . . . . State space variables, symbols and values. ............... Collection environments of various traces in the ME trace set. Error rates in trace sets. ......................... Cross correlation of different random processes. ............ Expected value of variance when using different combinations of R831 and LQI as CSI ............................... Symbols and notation. .......................... MLE parameters of marginal histograms generated from applying DPA with BED, BND, ED and ND route discovery algorithms to 100 ran- domly generated network topologies. .................. Packet counts ................................ PRR of individual nodes without gPMSS, PRR with gPMSS protocol, PRR gain for individual receivers R1, R2 and R3 due to selection diversity, and the PRR gain due to diversity combining ......... Energy consumed by transmissions at transmitter and receiver side per error-free received packet. Columns (1) and (2) correspond to the baseline scenario using only retransmissions. Columns (3) and (4) correspond to the case when only selection diversity is used by receivers. Columns (5) and (6) corresponds to the case where a full implementation of gPMSS is used that employs diversity combining (equal gain or maximal—ratio) in addition with selection diversity. xii 11 36 184 185 186 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 LIST OF FIGURES Physical layout & network topology of WSN ............... 8 Relationship between 6DEC—CL’ 6DEC—0Ni dDEC—ON—EZE and 6DEC—ON—S2BS .......................... 14 Slepian—VVolf coding in cluster—level communication. .......... 14 End-to—End channel between a transmitter and receiver on a multihop wireless network. ............................. 19 E PS spent across the network for varying degrees of spatial correlation and number of CLHs ............................ 29 E PS spent across the network for varying degrees of spatial correlation and number of CLHs ............................ 30 E PS spent across the network for varying degrees of spatial correlation and number of CLHs ............................ 31 Equipment setup for trace collection. .................. 40 CC2420 MAC frame format used for experiments. ........... 40 Office deployment environment. ..................... 41 Residential deployment environment. .................. 41 IEEE 802.11b and IEEE 802.15.4 channels in the ISM band. ..... 47 PDF of B conditioned on A and (I) = 1, 2 ................. 50 PDF of B conditioned on P and (I) = 1,2. ............... 51 Values of b for various (A, p) ........................ 52 xiii 3.9 The PDFs of the BER obtained from the actual traces for various LQI measurements at an RSSI of 88dBm, pB(B[A, p = 88dBm, d) = 1, 2). . 53 3.10 The PDFs of the BER for the same range of LQI measurements at RSSI of 88dBm as modeled by a discretized exponential PDF, 6303])“ p = 88dBm, a = 1,2). ............................. 54 3.11 Histogram of KDD values for a) Model from ‘Residential’ trace set and ‘Lab’ traces and b) Model from ‘Hallway’ trace set and ‘Outdoor’ traces. 57 4.1 Auto—correlation functions for bit level traces of the MC and ME trace sets. .................................... 62 4.2 Auto-correlation functions for symbol level traces of the MC and ME trace sets. ................................. 63 4.3 Auto-correlation functions for traces of the MC trace sets. ...... 66 4.4 Auto-correlation functions for traces of the ME trace sets. ...... 67 4.5 BER process of trace RIC—25 after filtering by 600 point averaging filter. 68 4.6 Plots of estimates of the Hurst parameter obtained using various tech— niques along with their average BERs, PERs and PLRs. ....... 70 4.7 For traces MC-ll, RIC—12, MC-13, MC—14 and MC-15 each subfig- ure, (from top to bottom): [Top] RAJ I B(1,m) of BER process ob- served in MO traces for lag m varying from 1 through 40. [Middle] ARM I B(1, m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of (i, the increments in RM I B(1, m). ............................... 73 4.8 For traces l\=IC-16, RIC-17, MC-18, MC-19 and MC—20 each subfig- ure, (from top to bottom): [Top] RM I B(1,m) of BER process ob- served in MC traces for lag m varying from 1 through 40. [Middle] ARM I B(1, m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of (5, the increments in RMIB(1,m). ............................... 74 4.9 For traces MC-21, MC—22, MC-23, MC—24, MC-25 and MC-26 each subfigure, (from top to bottom): [Top] RM I B(1, m) of BER process observed in MO traces for lag m varying from 1 through 40. [Middle] ARM I 3(1, m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of (5, the increments in RMIB(1,m). ............................... 75 xiv 4.10 For traces ME-l, ME—2, .\«IE-3, ME-4, ME-5 and ME-6 each subfig- 4.11 5.1 5.2 5.3 5.4 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 ure, (from top to bottom): [Top] RM I B(1,m) of BER process ob- served in MC traces for lag m varying from 1 through 40. [Middle] ARM 13(1, m) of BER process for the same channel traces. [Bottom] The memory length 1MB plotted as a function of (5, the increments in RA/{IB(1,m) ................................ For traces ME-7, l\IE-8, ME-9, l\'IE-10, ME—ll and ME—12 each sub- figure, (from top to bottom): [Top] RAMBO, m) of BER process ob- served in MC traces for lag m varying from 1 through 40. [Middle] ARA! 13(1, m) of BER process for the same channel traces. [Bottom] The memory length A! B plotted as a function of (5, the increments in RAJIB(1,772.) ................................ The law of conservation of flow requires that the sum of incoming flows qj z' and data Q,- generated at node n,- must equal the sum of all 9 outgoing flows (1.1-k. ............................ Tradeoff of Var[P] versus E [P] for a network with N = 10 ....... Tradeoff of Var[P] versus E [P] for a network with N = 15 ....... Tradeoff of Var[P] versus E [P] for a network with N = 20 ....... Paths from n99 to no. .......................... N lists of routes sorted in ascending order of path energies. . . . . . . Selection of next optimal point in the l\=’IV—plane by DPA ........ Mean-Variance tradeoffs offered by BED, BND, ED and ND paths. Plots of percent decrease in variance against percent increase in mean. Marginal histograms of percent increase )1 A ll E for the scatter plots in figures 6.5a through 6.5d .......................... Marginal histograms of percent decrease #A0'2 for the scatter plots in E figures 6.5a through 6.5d .......................... Diffusion plot of energy consumption rates averaged over all 100 net— works under SPF routing. ........................ Differential diffusion plots of energy consumption rates averaged over 100 networks using BED paths and DPA ................. XV 78 87 92 93 94 109 111 114 120 121 122 124 6.10 Differential diffusion plots of energy consumption rates averaged over 100 networks using BND paths and DPA ................. 124 6.11 Differential diffusion plots of energy consumption rates averaged over 100 networks using ED paths and DPA. ................ 125 6.12 Differential diffusion plots of energy consumption rates averaged over 100 networks using ND paths and DPA. ................ 125 7.1 Illustrated examples for three different classes of graphs; a) Geometric graph, b) Random graph, and c) Small world graph ........... 131 7.2 Overlapping communication regions of two communicating sensor nodes in a WSN .................................. 137 7.3 Geometry of WSN deployment and regions within it with respect to an individual sensor a,- ........................... 141 7.4 Plots of clustering coefficient C [left] and characteristic path length L, [right] as functions of ,u. for different values of R. Network parameters that remain fixed are A = 10000, kglobal = 4, p = 10, g = 3 and nc = 1.148 7.5 Plots clustering coefficient C [left] and characteristic path length L, [right] as a function of ,a for different. ratios of global scale link to local scale link communication range 5. Network parameters remain fixed at A = 10000, kglobal = 4, ,0 = 10, ”C = 1 and R = 4 .......... 149 7.6 Plots clustering coefficient C [left] and characteristic path length L, [right] as a function of ,u for different values of kglobal' Network pa- rameters remain fixed at A = 10000, p = 10, E = 3, R = 3 and nc = 3. 150 7.7 Graphical representation of integration term of d(F(v)) ......... 155 8.1 Application of generalized gPMSS in a wireless sensor network with mesh topology. Path from transmitter T to receiver R1 marks the mul— tihop path that would be taken in a network without gPMSS. Dashed line links between T and receivers R1, R2 and R3 denote the longer range but high loss links that are used under Generalized gPMSS. . . 160 8.2 Illustration of logical functioning of selection diversity. ........ 168 8.3 Illustration of logical functioning of equal gain diversity ......... 168 8.4 Illustration of logical functioning of maximal-ratio gain diversity. . . . 169 8.5 gPMSS protocol operations. ....................... 170 xvi 8.6 8.7 8.8 8.9 8.10 8.11 8.12 8.13 8.14 9.1 9.2 9.3 9.4 9.5 Equipment setup for trace collection. .................. CC2420 MAC frame format used for experiments. ........... PDF of BER experienced by receivers R1, R2 and R3 (p 308 = 0) is cropped out for better view of non—zero range. ............. PDF of LQI experienced by receivers R1, R2 and R3 .......... PDF of RSSI experienced by receivers R1, R2 and R3. ........ PER, PLR and PER+PLR experienced by receivers R1, R2 and R3 without gPMSS diversity combining and with selection, equal gain, and maximal ratio diversity combining .................. Histogram of BERs observed by receivers R1, R2 and R3 without gPMSS diversity combining and with selection, equal gain, and maxi- mal ratio diversity combining. ...................... The energy in )aJ consumed by transmitter and receivers per success- fully delivered packet ............................ Maximum number of transmission attempts m versus delivery guaran- tee g(%) ................................... This figure shows a graph on the lower plane, overlayed with another plane of the interpolated surface plot of node centrality scores. The centrality planes typically exhibit a number of peaks or local maxima. A spatial graph of 200 nodes. Node colors are indicative of the range in which their EVC falls .......................... [Top] Histogram of eigenvalues of adjacency matrix and Laplacian ma- trix A of network in figure 9.2; [Bottom] Cumulative sum of the se- quence of eigenvalues of adjacency matrix and Laplacian matrix of network in figure 9.2 when sorted in descending order of magnitudes. In both figures the lines plotted in red color are averages of 50 networks generated randomly with the same parameters. ............ Reconstructed topologies of the graph from figure 9.2 using only the first 1, 2, 3, 5, 10, 15, 50 and all 200 eigenvectors. ........... Spectral drawing of graph in three dimensions using entries of x1, x2, and X3 for the three coordinate axes. Nodes are colored according to their C15 FCC ............................... xvii 173 174 177 178 179 180 181 185 188 193 197 200 201 205 9.6 9.7 9.8 9.9 9.10 PCC of nodes in network of figure 9.2 when computed using first (a) l and (b) 2 eigenvectors. The histograms accompanying each graph plot show the distribution of PCC of their nodes. The lineplot in the histogram represents the average PCC histograms of 50 randomly generated networks with the same parameters as the network in figure 9.2 ...................................... PCC of nodes in network of figure 9.2 when computed using first (a) 3 and (b) 5 eigenvectors. The histograms accompanying each graph plot show the distribution of PCC of their nodes. The lineplot in the histogram represents the average PCC histograms of 50 randomly generated networks with the same parameters as the network in figure 9.2 ...................................... PCC of nodes in network of figure 9.2 when computed using first (a) 10 and (b) 15 eigenvectors. The histograms accompanying each graph plot Show the distribution of PCC of their nodes. The lineplot in the histogram represents the average PCC histograms of 50 randomly generated networks with the same parameters as the network in figure 9.2 ...................................... PCC of nodes in network of figure 9.2 when computed using first (a) 50 and (b) all 200 eigenvectors. The histograms accompanying each graph plot show the distribution of PCC of their nodes ......... Plot of phase angles (1) (in radians) of PCC vectors with the EVC vector for the graph in figures 9.6, 9.7, 9.8 and 9.9. .............. xviii 207 208 209 Chapter 1 Introduction 1.1 Organization This research characterizes, analytically and quantitatively, the bit error rate (BER) process, the network lifetime and the topological preperties of wireless sensor net- works (WSN) [2], [59]. The following section describes the contributions made in this dissertation. 1.2 Overview of Contributions Chapter 2 provides an analytical model for the end-to-end capacity between nodes in a W SN and the base station. This study distinguishes itself from previous studies of wireless network capacity in that it assumes a many-to—one data flow (in place of an all-to-all flow) producing what is called the funneling or reachback effect. The model also takes into account in-network data fusion/ compression. We consider scenarios in which there is a) no compression, b) opportunistic compression and c) perfect com- pression. The model shows that the distribution of power consumption rates of nodes is skewed due to the uneven traffic load flowing through nodes. Power consumption is lessened in systems in which sensor measurements are highly correlated and take advantage of it by employing aggressive data compression like Slepian-Wolf coding [114]. Chapters 3 and 4 relate to modeling of the BER process in IEEE 802.15.4 chan- nels low-rate wireless personal area networks (LR-VV PAN). Chapter 3 describes the experimental setup used to collect a large set of residual packet traces. These traces distinguish themselves from traces collected by other studies in that they also cap- I3111‘e channel state information (CSI) measurements alongside every packet and events such as packet losses and truncated packets. The traces are used to establish the de- 31‘ 66 of correlation between CSI measurements and the BER process that packets are subjected to. After establishing the usefulness of CSI for estimating BER, we develop CSI-driven models of the BER process for sets of traces collected in different environments. Divergence measures between the models derived from different traces show that there is very small average divergence between different models leading to a CSI-driven BER model that is independent of physical environment. Thus CSI measurements of traffic received over a particular link can be used to estimate the BER and assign it a link cost. Chapter 4 analyzes the memory properties of errors in the traces. Correlation based analysis on bit and symbol level traces reveals a constant memory length of 2 bits and 2 symbols, respectively. Furthermore, we high- light the inability of correlation analysis to provide a clear measure of memory length of the BER process when a channel is subjected to periodic interference and arbi- trary selection of a significance threshold for the correlation function. To address this shortcoming of the correlation function based analysis we introduce relative mutual information (RMI) [56], a normalized form of Shannon’s mutual information (MI) [32] that provides a more robust means of measuring memory length. Chapters 5 and 6 contain our work on the network lifetime problem in WSNs. The lifetime of a WSN is typically defined as the time until the first node runs out of power. The corresponding optimization problem can formulated as a minimax linear program (LP) ([18]). However, the vision of the future of WSN calls for a network consisting of a very large number of devices that are inexpensive and redundant. The fact that WSN applications by their very nature impose a many-to-one data flow that produces a funneling effect (see Milgram [82]) leads to large variations in the Power consumption rates in nodes. Chapter 5 proposes the redistribution of traffic rOuted to a VVSN’s base station by the joint minimization of the mean and variance 0f power consumption rates. Such a statistical objective function cannot be held hOstage by the life of an individual sensor but takes a more global view of network lifGtime. This chapter provides a formulation of the optimization problem in the 3 form of a quadratic program (QP) ([18]). The quadratic nature of the optimization problem puts restrictions on the scalability of the QP approach. Chapter 6 provides an approximate formulation of the lifetime problem in the form of a dynamic program (DP) ([18]). Experiments show that in W SN as large as 100 nodes there is a visible difference in the rate of reduction of variance and rate of increase increase in mean of power consumption rates as shorter routes are traded-off in favor of routes that are less efficient in the greedy, shortest-path—first (SPF) sense. Chapters 7, 8 and 9 describe topological properties of WSNs, particularly the small-world effect. Chapter 7 describes the place small-worlds networks [128] oc- cupy on the spectrum of networks with node connections varying between order and randomness. In this chapter we describe the potential benefits of having wireless networks with small-world topologies and previous approaches to achieve this goal. Small-world networks are characterized by a phase difference between the drops in characteristic path length and clustering coefficient of networks as the fraction of links in the network that are shortcuts is increased. Prior models of characteristic path length and clustering coefficient in various types of graphs did not consider the addition of range limited links. This chapter presents analytical models for both these quantities for graph topologies that are subject to the constraints of wireless networks. The model developed in this chapter can be parameterized to accommo— date any of the existing approaches to building small—worlds in WSNs. Chapter 8 describes a method based on single-input multiple-output (SIMO) principles, called the generalized ‘Poor-Man’s-SIMO-System’ (gPMSS), a practical implementation of Shortcut links in WSNs by leveraging cooperative communication and diversity combi- nation principles. The diversity combining methods explored include selection diver- Sity, equal gain and maximal-ratio gain diversity combining, where the weight factors Used in maximal-ratio combining are provided by the CSI-driven channel model of the BER developed earlier in chapter 3. gPMSS enables the construction of small- 4 world networks in wireless networks by alternative means. Its chief advantage over existing approaches lies in the fact that it is not based on any modifications to the hardware of sensor motes. Proof of concept is provided by performing detailed anal- ysis on a set of wireless channel packet error traces and also implemented on the Crossbow Imote2 sensor mote. The work on gPMSS is also relevant to the research on the network lifetime problem. Chapter 9 attempts to identify the most central nodes/regions in a wireless network. It highlights the problems demonstrates the shortcoming of pre-existing centrality measures (degree, closeness, betweenness and eigenvector centrality). A new measure of node centrality called principal component centrality (PCC) is proposed which addresses the shortcoming of eigenvector central- ity in identifying well connected hubs within graphs characteristic of wireless mobile ad-hoc networks and WSNs. The hubs in a network identified by PCC can be used for the placement of shared network resources, e. g. endpoints of shortcut links. Finally, chapter 10 concludes this dissertation by summing up our finding. Chapter 2 Network Channel Capacity of IEEE 802.15.4 Wireless Sensor Networks Under Reachback 2.1 Introduction Over the past several years different assumptions have been made about the structure and capabilities of wireless sensor networks (WSN) and the devices they are consti- tuted of. In [43] Gupta and Kumar studied the scalability of wireless networks with randomly chosen source destination pairs. Their conclusions offer two solutions to the scalability problem; 1) Design smaller networks, or 2) localize communication by clus- tering nodes. The idea of a WSN consisting of homogeneous devices gradually gave way to that of a network consisting of a homogeneous mix of nodes with non-uniform device capabilities. In this newly emerged view of W SNs, sensors are grouped into clusters. Each cluster of sensor nodes elects from among its members a clusterhead I10de (CLH) that acts as a gateway for all incoming and outgoing communications. Consequently, WSNs can be thought of as hierarchical networks with 5 levels. However, since most previous work on WSNS distinguishes only between two roles for devices, sensors and CLHs, we assume a two-level hierarchy with s = 2. This assumption is also supported by the IEEE 802.15.4 low rate-wireless personal area networks (LR-VVPAN) draft standard. The standard refers to a hardware device with ITlOre resources with a more complex implementation as a full function device (FFD) and a device with fewer resources and a simpler, less expensive implementation as a r educed function device (RFD). For the remainder of this chapter we will assume a VVSN built out of devices compliant with the IEEE 802.15.4 physical layer (PHY)/ Inedium access control (MAC) specifications. Level 1, the lower level, refers to the network formed by a CLH and its associated Sensors. Typically, all devices within a cluster are capable of communicating with ea~Ch other directly. Therefore, communication between sensors and their CLH are a'SSurned to take place over a single hop. We will use the terms cluster, intra-cluster or Cluster-level communication interchangeably to refer to the exchange of messages 7 10 x1 x x x O 2 4 6 8 10 Figure 2.1: Physical layout & network topology of W SN. between nodes belonging to the same cluster. Communication within a particular Cluster proceeds at a common frequency, i.e. there is a potential for interference between transmissions of different sensors of a cluster. Different clusters may or may not use differing frequencies. l\"‘Ioreover, the network topology within a cluster is r eStricted to a star topology with the CLH at the center. Level 2, the upper layer, refers to the network formed by the CLHs of all clusters in the WSN and the base station. We will also refer to this network as the overlay net- WOrk (ON). We assume that the CLHs participating in the ON are capable of routing and relaying their own and other clusters’ packets towards the base station. More- Over, since the most widely used WSN routing algorithms like destination-sequenced disfiance vector (DSDV) [99], directed source routing (DSR) [61], ad—hoc on-demand distance vector (AODV) [100], directed diffusion [58] etc., are different. forms of short- 8 est path routing algorithms, we assume that at any given time the routes from CLHs to base station in the ON form a tree rooted at the base station. We are discounting the possibility of using bifurcated routing, i.e. multiple paths from source to desti- nation. We will use the terms overlay, overlay network or CLH-level communication interchangeably to refer to the exchange of messages between nodes belonging to the ON. Moreover, it is assumed that message exchanges between CLHs in the ON take place at one frequency, i.e. like sensors in a cluster, CLHs in the ON have the potential to produce interference for each other. However, this frequency channel is assumed to be free of interference from cluster-level communication. Moreover, the topology of the ON is a mesh topology. As 2.1 shows, as traffic generated by the CLHs situated farther away approaches the base station, the expected volume of traffic carried by a link increases. This leads to a capacity bottleneck around the base station that subsequently limits the rate at which CLHs, and ultimately sensors, can inject data into the network. This is Called the reachback problem [9]. Thus source coding is used to alleviate the effects of the reachback channel. Besides entropy coding methods, a very popular compression nlethod in WSNs is Slepian-VVolf coding [114] which assumes prior knowledge of the degree of correlation between sensors. 2 . 2 System Model 2~2.1 Wireless Networking Standards for WSNs In Our attempt to formulate a generalized expression for the end-to-end capacity of a Channel between an arbitrary sensor and the base station we remain open to the pos- Sibility of a number of different wireless networking technologies. Besides proprietary radio interfaces, the most commonly encountered standardized wireless networking technologies found in early implementations of WSNs are the IEEE 802.11x wireless local area network (WLAN) standard [51], the IEEE 802.15.1/ Bluetooth standard [4] and the IEEE 802.15.4 standard [5]. The distinguishing features of these three net- working standards are many. Table 2.1 lists only the features that we were concerned with in our work, i.e. the operating frequencies and the types of MAC protocols. As we will show in a later section, our interpretation of how the end-to-end capac- ity of a wireless channel can be computed requires us to assume a pathloss model to model the physical channel. Pathlosses depend on numerous environmental factors whose effects are generally too complicated to predict. Two parameters that influ- ence pathlosses in a major way are the frequency and transmitter-receiver separation. We assume that all transmissions are taking place in the 2.4 — 2.4835GHz industrial scientific and medical (ISM) band which is used in all three wireless networking stan- dards under consideration. This will allow us to use a single pathloss model that will be applicable to all three networking standards under consideration. Therefore, our end-to—end channel capacity expression will not be applicable to WSNs using IEEE 802.15.4 networks operating in the 868—868.6M H z or 902—928M H 2 bands. In addi- tiOn, we are allowing for both collision avoiding carrier sense medium access/ collision aVOidance (CSMA/ CA) and collision—free time division multiple access(TDMA), type IVIAC protocols. The choice of the MAC protocol mode will affect parameters in the model. Let N be the total number of sensors in a WSN of M clusters. Let Cit/2' E {1, 2,3, . . . , M} denote an individual cluster consisting of one CLH and N,- sensors (therefore; N = 2911 Ni): Sensors are addressed using a 2-dimensional address SCheme in which the ith cluster’s jth sensor node is labeled ni(j)Vi E {1, 2, 3, . . . , M}, VJ E {1,2,3, . . . ,Ni}, with viz-(0) denoting its CLH, and n0(0) denoting the base StEltion. We also define a frequency function f (n,- (j )) that returns the frequency at ‘which the device passed in the argument communicates within a cluster. This way 10 Table 2.1: Tabular listing of relevant features of the three wireless networking tech- nologies under consideration for use in W SNs. Feature IEEE 802.15.4 IEEE 802.11b IEEE 802.15.1/ Bluetooth Frequencies 2.4-2.4835 GHz 2.4-2.4835 GHz 1. W 2. 992—9218544459 3. 2.4-2.4835GHz A-lACtype Polling 1. TDMA in GT8 1. CSMA/CA in , DCF 2. CSMA/CA in CTS 2. Polling in PCF Topologies Meshed Star Star Star/Meshed Star (DCF) /Meshed (Piconet) Star (PCF) \ 11 f (712(0)) denotes the intra—cluster communication frequency of cluster Ci- We use fi‘v’i E {1, 2, 3, . . . ,M} as a shortened form to denote the cluster frequencies of all M clusters. Similarly, we abbreviate f (n0(0)) by f0 to denote the frequency used by CLHs for communicating in the ON. The probability of n k(l) making an interfering transmission at the same time as n.,-(j) is making its transmission is denoted by an (l) ("i(j))- We also define a frequency indicator function in equation 2.1; 0; f (ndflHWUi) . (2.1) I ('rti(j),nk(l)) = f 1; f (712:ij = f (7119(1)) \Nith the definitions of symbols describing the network in place we now come to the terms that will quantize the channel conditions, i.e. capacity and probability of error terms. First off we define the probability of a bit error or the bit error rate (BER) denoted by p. The 802.15.4 standard uses binary phase shift keying (BPSK) Illodulation at 20 and 40kbps and offset-quaternary phase shift keying (O—QPSK) mOdulation at 250kbps. Both BPSK and QPSK modulators make hard decisions ba-Sed on the received symbol and output either a ’0’ or a ’1’. Therefore, assuming an additive white Gaussian noise (AWGN) channel both BPSK and QPSK receivers Can be modeled by binary symmetric channel (BSC) with probability of error p. p is defined as the fraction of transmitted bits that are received without errors. Hence, this term models the channel between the Physical layers of the 081 model transmitter and receiver. _ # of bits received without errors (2 2) # of bits transmitted ' Frames in 802.15.4 are protected only by a 16 bit frame check sequence (FCS) With no error correction capability. This implies that whenever even a single bit in an entire frame is received in error the receiver discards the entire frame. Packetization 12 affects net throughput. We denote the fraction of transmitted bits that are received without errors by 6. 6 will be referred to as the packet error rate (PER). Since packets are either received correctly and forwarded to the next higher layer or discarded due to F CS failure, the PER is equivalent to the probability of error 6 of a binary erasure channel (BEC). A BBC is used to model the channel between the MAC Layers of the 081 model transmitter and receiver. _ #z of packets received without errors — # of packets transmitted a (2.3) Finally, since we are assuming the use of Slepian-VVolf coding we have take into account the dependencies that introduced in data streams. As a result of these dependencies packets that will be received error free will at times not be decodable due to losses in transmissions from other sources. As a result, packets that are received free of errors can end up being undecodable due errors in another transmission it (hipends on. Therefore, we define the PER with SIepian—VVolf coding as the fraction Of transmitted packets that are decodable by the receiver denoted by 6 D EC' # of decodable packets received " = 2.4 ODEC # of packets transmitted ( ) p, 6 and (5 D EC for links within a cluster are denoted by pCL’ 6C L and (5 D EC—C L' Sirnilarly, the corresponding quantities for links on the ON are abbreviated by pON’ 50 N and 6 D EC—O N: Since, the ON channel between an arbitrary CLH and the baSe station may comprise of multiple hops we need to define additional quantities for the end-to—end channel in the ON pON—E2Ei 60N—E2E and 5DEC—ON-E2E' FiIlally, the channel formed between each individual sensor and the base station IS Characterized by a combination of the above computed values and denoted by pON—S2BS’ 60N—S2BS and 6DEC—ON—S2BS' To clarify, figure 2.2 shows the relationship between 5DEC—CLi (Sosa—0N: 5DEC—ON—E2E 13 6 6DEC—CL DEC—ON—E2E 6DEC—ON—S2BS * Base station I Clusterhead . Sensor Figure 2.2: Relationship between 6DEC—CL3 (EDEC—ON’ éDEC—ON-E2E and 5DEC-0N—S2Bs- H(X1|X2) H(X3|X2, X1) 0 O O --- O \ H(Xn|Xn-1, ,X1) H(X1) V Figure 2.3: Slepian-Wolf coding in cluster-level communication. and 5DEC-ON—SQBS' 14 2.2.2 Source &: Channel Coding \Ne consider three options for source coding; 1) No source coding, 2) opportunistic compression [71], and 3) Slepian- Wolf coding. The first option does not perform any compression at all. Data is merely collected at each CLH, concatenated, packe- tized and routed to the base station. Opportunistic Compression assumes correlation between different sensor readings. Each CLH compresses data it receives from down- stream based on other data available to it from other sources. Slepian-Wolf coding was first proposed by Slepian and Wolf in [114]. However, we make some simplifying assumptions about Slepian-Wolf coding as it applies to W SNs. These assumptions have been taken from Marco and Neuhoff in [80] and [81]. Slepian—Wolf coding also ex- plOits the spatial correlation of sensor readings in neighboring sensors and is employed as a. means to compress data before transmitting it to the base station. Slepian-Wolf COding is based on equation 2.5. However, Slepian-Wolf assumes that the degree Of correlation is known prior to transmission, whereas opportunistic compression as- Sumes no prior knowledge. Consider a cluster i as in figure 2.3 consisting of N, sensors and a CLH in which the first sensor 711(1) produces reading X Ilifl)’ the second sensor 712' (2) produces reading X , 2 and so on. ”A ) (2.5) The size of all N,- sensor readings after lossless compression is lower-bounded by t1leir joint entropy. As an example, Slepian-Wolf coding within a cluster proceeds as fOllows. 1. Sensors transmit their readings to their CLH. For the purpose of simplifying 15 analytical expressions, let us assume that the transmissions to the CLH are scheduled in the ascending order of sensor nodes’ ID numbers. 2- The first transmission Xn'(1) by nz-(l) is not compressed (see first term on 2, left-hand side of ( 1)) 3. The second sensor nl-(2) compresses its sensor reading to H (Xni(2)[Xni(1)) based on the side information of n,- (1)’s transmission of size H (X (1)). There- ft rni f a 't d ‘ 1 't I t»- -. t: 't at (X . . ore, 1e ] no e in cus er 2 ransnn s IS '1 a as H ni(9)IXni(]‘1) "Xn-(1)) bits. This way the total volume of all transmissions approaches 2 the joint entropy as shown in (1) and also depicted in figure 2.3. However, this coding scheme has one major disadvantage. While the savings in transmissions can be substantial, depending on the spatial distribution of the phenomena being sensed, the failure of the CLH to receive the kth transmission results in its inability to reconstruct all subsequent transmissions k + 1 through N,- for that round. The high sensitivity of a receiver’s ability to decode packets to packet losses, and the fact that bit and packet error rates in single hop wireless networks are Orders of magnitude higher than those in multi-hop wired networks makes the use of IV'IAC layer channel codes imperative. Even without any dependencies between data Streams the BERs of end-to-end channels representative of multi-hop paths in wireless n(itworks can often times be large enough to impose unrealistically large overheads On end-to—end channel codes. The PERs of various links will depend on the size of packets. When Opportunistic Compression or Slepian-Wolf coding are employed that will depend on the degree of COrrelation in data readings. To model the lossless compression of data and determine the message sizes Lm (n, ( j )) we use the model proposed by Pattern, Krishnamachari a11d Govindan in [97]. The use of Slepian-Wolf coding forces an order on the devices in the WSN which is also described in detail in [97]. The number assigned to a particular 16 device ni(j) in this order is returned by the order function O(-) which returns a value in the range 1 S O (ni(j)) S N. 2.2.3 Power Consumption Model The total energy E (n,(j)) consumed in mote ni(j) in equation 2.6 is modeled as the sum of energies consumed in communication ET X (n,- (J)) and processing EPR (7120))- E ("Nil = ECOMM (MUD + EPR (”Mil - (2-6) ECO M M (ni(j)) in equation 2.7 can be further broken down into energy con- sumed in transmission ET X (ni(j)) and reception E R X (nZ-(j)). ECOMM (in (1')) = ETX (”103) + ERX W31) - (2-7) The total energy spent by all devices in a network divided by the uncompressed number of bits of data communicated to the base station yields the energy per symbol (EPS) of the network configuration in equation 2.8. Ni 2531 531:1 Enifj) N,- ' 2,1312,le "19(0) =1f (f (nail) ,f (Tl/ill)» KOPTX—amp"lTX-a72.t"lRX—a'n.t PLO X (d(”z‘(j(]6nk(l)))2 (79210.2 (2.9) Here, PTX—a-mp (typically 17an for IEEE 802.15.4 compliant devices) is the Signal power at the transmitter after amplification before it is passed to the antenna, "TX—ant is the transmitter antenna efficiency. 77 R X—ant is the receiver antenna Efficiency and K, PLO, and K0 are environmental parameters that depends on the Operating environment (see [86]). Since we are assuming that a WSN consists of de- vices with identical radio interfaces transmitting at a fixed power we consider these terms to be constant across the entire network. We also define two reference param- eters fc and do for this pathloss model. For the sets of parameters provided in [86], f c is set to 5GHz and do is set to 1m. This leaves the expression dependent on the transmission frequency f and the distance between devices 72.,(3') and n k(l) that is rGturned by the distance function d (n,(j), nk(l)). In order to obtain the BER for a DMC we need an expression for the signal-to- interference 8 noise ratio (SINR). The general expression for the SINR is given in equation 2.10. Using the expression for the pathloss model described above we can arrive at an expression for the SINR in the terms of known quantities. PTX SINR = , (2.10) PA 'I' Z Pint where PT X is the power of the received signal for which the SIN R is being com- puted and Pint is the power of interfering signals caused by undesired concurrent transmissions elsewhere in the network. P A is the ambient noise power of interfer- 20 ence produced by sources that are not part of the WSN and are not modeled by any terms in Pint: Sources of ambient noise power may include but are not limited to other networks that are co—located with the WSN under consideration [136] or devices or appliances (microwave ovens, cordless phones) that operate in the same frequency band. Since at the cluster-level all transmissions are directed from sensors to their respective CLH, the term S I NR (til-(j) —-> n All» represents the SINR of the transmission from nZ-(j) to n k(l). In the general case, all sensors and CLHs can be considered potential sources of interference. Obviously, we assign qni (j) (712(3)) 2 0. The interference power 23 Pint in equation 2.10 is the sum of all other signals that are received originating from sources other than n11 ( j). This term is computed by Summing the interference power of all sensors. In order for nk(l) to contribute to the power of the interference signal for a transmission originating from n,,-(j), nk(l) must be 1) operating in the same frequency band and 2) transmitting at the same time as n.z'(j). Transmitters operating at different frequencies make effectively no contribution to interference. Therefore, the indicator function defined earlier is used. The probability that a sensor will produce an interfering signal at the same time as 712(3) transmits is accounted for by multiplying the term further by anm (”2'ij SINR (711(7) —-) 7tk(l)) If (n,(j),nk(l)P (n,,j(j) —> nk(l))) PA + 2:2le 23:0 Ifrnaj). ff'nnifillllqnmm)(WUNP (nme) a nae)’ (2.11) Then equation 2.11 is the final expression for SINR(ni(j) —) nk(l)). In the Ilext step we use the SINR and Q-function to obtain the probability of error for a BSC. The use of the Q—function to arrive at the BER using the SINR is described 21 by Rappaport in [104]. If Q(a: =\/12_7? ffo. eIZLdu, then the probability of receiving a bit error at nA(l) in a transmission originating at nZ-(j) is called the bit error rate (BER) p(n. -]( ) ——> nA(l)). IEEE 802.15.4 uses two different modulation techniques. 802.15.4 uses Binary Phase-Shift Keying (BPSK) at the 20 and 40hbps data rates in the 868 — 868.6MHz and 902 — 928MHz bands, respectively. At 250kbps in the 2.400 — 2.4835GHz band it uses offset-quadrature phase-shift keying (O-QPSK). In either case the BER is obtained by using the Q—function. Equation 2.12 shows the relationship between SIN R and BER for a QPSK receiver. Equation 2.13 is the corresponding equation for a BPSK receiver. This can be thought of as the probability Of error in a binary symmetric channel (BSC). The corresponding channel capacity in terms of the BER is obtained from equation 2.14, where Hb(-) is a function that returns the entropy of a Bernoulli random variable with the parameter provided in the argument. p(n,'(j) —+ nA(l =Q(\/ZSIR( we )—> nA(z))) _u (2.12) = ))_/00 e Ydu. W27? \/2SINR(nl-(j)——>nA(l)) p(n,~(j) ——> nA.(l)) =Q(n(\/SINR ,(j )—+ nA(l))) _u (2.13) = —/00 e gdu fl? \/SINR(nl-(j)——>nA.(l)) CBERln Z-j()——>nA.(l))=1-—Hb(n i(j)—+nA(l)) (2.14) From the BER we now determine expression 2.17 for obtaining the probability of a packet loss or the packet error rate (PER) 6 (‘71.,(3') —+ nA(l)) for a transmission fI‘om n ,(j) to nA(l). The PER corresponds to the probability of error of a binary eI‘asure channel (BEC). We assume that witl'iout channel coding a received packet is discarded if a single bit is in error, a valid assumption considering our choice of wireless 22 standards. L h is the per sample header size in bits. The size of the sample making up the message depends, of course, on the entropy reduction method employed. When no source coding is used Lm (n3(t)) is simply [ H (X 7115(0)] , where H () is the entropy function. When opportunistic compression is used the size of a message originating at n3(t) is Lm(n3(t)) is H [H (Xn5(t)|Xn5-(1)"'"X715(t——1))-|' Fiom 2.15 we trivially obtain expression 2.16 for the channel capacity C p E R (n2(j) —> nA(l)) in terms of 6 (72.10) ——> nA(l)). Note that for the case of Slepian-Wolf coding, 2.15 and 2.16 do not yet take into account the additional losses due to a receiver’s inability to decode a received message caused by losses in transmissions of other messages the received message is dependent on. 5 (71,10) —-> nA(l)) = 1 — [1 — p (12,-(3') —> nA.(l))]Lh+le("5(‘))l (2.15) CPER("i(j)_"nk(l)) =1— p (Til-(j) —> nA(l)) (2.16) Now we consider the case where Slepian-Wolf coding is employed and a further expression for the PER of a message can be obtained which takes into account losses in streams that the receiver depends on to decode the message. Since cluster-level communication is single hop only and the ON is essentially a multi—hop network the expressions for (5 D EC—C L and (5 D EC—ON are significantly different and we will depart from our practice of finding general expressions that we followed to this point. 6DEC—CL (me) —+ 71210)) = 1— [1— 22 ("1(1) —> nA:(0))] Lh+Lm (2.17) 23 where, W (”2‘0” 2 lH (Xnmfl/‘ll A=XA,va:1gagO(n,,(j)) (2.18) CPER-SW—CL (”2'03 -> nzt(0>) = 1 - 5DEC—CL (7120) -> MUD) 2.3.2 Overlay Network Communication We now turn our attention to the end—to-end capacity of the channel between an arbitrary CLH and the base station communicating over a multi—hop wireless network. The case in which all CLHs are directly communicating with the base station in the ON becomes a special case of the more general case of a multi—hop ON. Like for the l-hop case, we start from the expression for SINR, this time for a signal transmitted by a CLH TIA-(0) to its upstream neighbor. This is given in 2.19. Before proceeding further we define a set of new functions that will subsequently be used in this section. lining-(0)) returns the immediate upstream neighbor of CLH nZ-(O), where upstream denotes the direction towards the base station in the network topology. R1i(n.i(0)) returns the set of CLHs that is 1 hop downstream from 711(0), where the term downstream refers to the direction away from the base station in the network topology. RT(n.A(0)) returns the set of all CLHs that are upstream from nA-(O). Similarly, R‘L(ni(0)) returns the set of all CLHs that are downstream from 712(0). 24 Note that for a TDMA protocol in the ON anm) = 0V1: , and hence 2.19 simplifies to 2.20. P (”110) —+ Elfin-MOD) SINRON(nA(0)) = PON A (2.20) Applying the Q—function leads us to similar expressions 2.21 and 2.22 for the BER as before. pON(n,-(0)) = Q (\/2SINRON(nz-(0))) 1 00 _ = —— e 2 u «5? /\/2SINRON(n,-(0)) d (2'21) pow-x0» = Q (\/SINRON(nA-<0)>) 1 00 _u : _ e 2 A m /\/51N120N(n,(0)) d (2'22) From 2.21 and 2.22 we can obtain equation 2.23 a recursive definition for the BER of the multi-hop, end-to—end channel between a CLH and the base station. pomggEmA-w» =PON("2‘(0)) [1— mum (R1T>)] +pON—E2E (R1T(n,§(0))) [1 — p0,7\r(n,-(0))] . (2.23) The expression for the PER for a packet originating at 7227(0) on a link between nA(0) and its upstream neighbor R1T(nA(0)) is then provided by equation 2.24. 25 60N_Az.k<0)> = 1— (1 - meme»)LhtLMWW”, (2.24) where (50N_nk(0)(nj(0)) = 1 if ‘nA(0) (A? RT(n]-(0)) and the message size origi- nating from nA-(O) is, [Vi LmrnA-(on = Z Hm). (2%) i=0 This leads us to the final expression 2.26 for the end-to-end PER from an arbitrary CLH ni(0) to the base station. Equation 2.27 gives the corresponding expression for the end—to-end capacity. (SON__E2E(n,-(O)) = 1 — an(0)ERT(ni (0)) (1 — 6ON__nkA0)(n,-(O))) (2.26) CPER—O]V—E2E(”i(0)) = 1 - (SON—EZEl'H/iiol) (2.27) For Opportunistic compression and Slepian-Wolf coding the derivations for expres- sions in equations 2.19 through 2.27 proceed in exactly the same manner, equation 2.25 being the exception. Opportunistic compression and Slepian-Wolf coding replace equation 2.25 by equation 2.28 and 2.30, respectively. Lm(‘n.,,;(0)) = [H(an,(0) . . . X7Li(Ni)|A)l (2.28) A = {vxa : a e Rl(n,(0))} (2.29) 26 Lm(n,(0)) = Z Lm(a) (2.30) aeRi(n,-(0)) 2.3.3 Sensor-To-Base Station Capacity Using the above results the sensor-to—base station BER/ PER for any arbitrary sen- sor nZ-(j) can be obtained by multiplying the cluster-level BER p(n,(j)) in 2.12/ PER 602.2(3)) in 2.17 with the end—to—end BER pON—E2E(ni(0)) in 2.23/ PER (50 N— E2 E(n,(0)) in equation 2.26, respectively. This yields an expression for the sensor-to—base station BER in equation 2.31 and a corresponding sensor-to—base sta- tion PER expression in equation 2.32. From 2.31 and 2.32 we can obtain the corre- sponding capacity expressions in equations 2.33 and 2.34. 11521350120 )) = p0N_EzE(ni(0)) [1 - M71100] + 290120)) [1 — P0N_E2E(”z'(0))] (231) 652350121» = 1 - [1 — 6mm») [1 — (SON—EQEinz‘iODJ (2.32) CBER—SQBSiniijl) = 1 - Hb (Psggsmiljm (2-33) CPER_SQBs(’Il.i(j)) :1" 60120)) (2.34) = [1 — we») [1 - éoiv_E25<'rz..>] 27 2.4 Results and Analysis For the following experiments we use an 802.15.4 network with its MAC operating in TDMA/ GTS enabled mode. We use the PHY channel model for residential environments in [86]. The WSN consists of N = 150 sensor nodes randomly placed over a square region of dimensions 10 x 10 according to a uniform random distribution. To create longer multi-hOp routes in the ON we place the base station at coordinates (0,0). We assume a set of 15 available frequencies for cluster-level communication in addition to one frequency reserved for communication between CLHs in the ON. Figure 2.1 depicts a sample WSN. Circles denote the positions of CLHs while the x-marks denote the positions of sensors. Sensors in closest proximity of the means obtained by the k-means clustering algorithm [44] are assigned the role of the CLH for that cluster. Solid lines depict the topology of the ON while broken lines indicate a sensor’s association with its respective CLH. Values for the correlation factor p are varied through ,0 = 0.1, 1, 10, 20, 30. Increase in p can alternatively be viewed as an increase in the node density. The number of CLHs N1 is also varied through M = 5, 10,20, 30,40. We assume the use of near capacity achieving channel codes at the MAC layer and evaluate the EPS for the cases when, 1. No source coding, 2. Opportunistic compression, and 3. Slepian-Wolf coding are employed. For each of these cases we assume two sets of complexity vectors c1, (1'1,c2,c12, 1) {5,1,10,1}, and 2) {5, 2, 10, 2}. The constant coefficient at the receiver side c2 is assigned a higher value than the corresponding transmitter side coefficient c1 because channel decoding is typically more complex than encoding. This produces six options 28 Correlation Number of CLHS (a) No source coding 01 = 1, 02 = 1, c1 = 5, and c2 = 10. Correlation Number of CLHs (b) No source coding in = 2, (i2 = 2, C1 = 5, and c2 = 10. Figure 2.5: EPS spent across the network for varying degrees of spatial correlation and number of CLHs. to evaluate. Obviously, a low is desirable. Furthermore, based on the measurements reported by Polastre, Szewczyk and Culler in [101] and Madden, Franklin, Hellerstein and Hong in [79] we take the ratio of per bit energy consumption for transmission, 29 Correlation Number of CLHs (a) Opportunistic compression a1 = l, 012 = 1, c1 2 5, and c2 = 10. Correlation Number of CLHs (b) Opportunistic compression m = 2. Hg 2 2, cl = 5, and Cg : 10. Figure 2.6: EPS spent across the network for varying degrees of spatial correlation and number of CLHs. reception, and instruction execution to be 1 : 0.6 : 1 / 800. Figures 2.5a, 2.5b. 2.6a, 2.6b, 2.7a and 2.7b plot EPS against the degree of cor- relation and the number of CLHs. Figures 2.5a and 2.5b show a decrease in the EPS 30 40s Correlation Number of CLHs (a) Slepian-Wolf coding (11 = 1, a2 = 1, c1 = 5, and c2 = 10. 300s 200s EPS 100s Correlation Number of CLHs (b) Slepian-Wolf coding (21 = 2, (Y2 = 2, c1 = 5, and C2 = 10. Figure 2.7: EPS spent across the network for varying degrees of spatial correlation and number of CLHs. with increasing number of CLHs and no variation with increasing values of p. The second observation is according to expectations because we are not using any source coding to leverage the correlation in the data. Figure 2.6a, 2.6b, 2.7a and 2.7b ex- 31 hibit similar trends but on very different scales. EPS increases with increasing M and decreases with increasing ,0. The greater exploitation of the inherent correlation in the data means a smaller scale of the EPS for figure 2.7a and 2.7b relative to figures 2.6a and 2.6b. The sudden increase at high M and p can be attributed to outlier values. These results lead us to conclude that weakly correlated data favors the omission of any source coding scheme and a higher number of M. For highly correlated data on the other hand Opportunistic Compression and Slepian-Wolf cod- ing are the better choice. At high values of p the value of M plays an increasingly negligible role. The choice between Opportunistic compression and Slepian-Wolf will depend on the complexity of the available implementations of the two, i.e. at similar complexities Slepian-Wolf outperforms Opportunistic compression but in a compar- iSOII between Slepian—Wolf with complexity vector {5,2,10,2} with Opportunistic Compression with complexity {5, 1, 10, 1} the latter outperforms the former. 32 Chapter 3 CSI Driven Model of BER Process 011 IEEE 802.15.4 Links 33 3. 1 Introduction The bit errors and packet losses that are observed at the wireless receiver’s medium access control (MAC) layer are modeled by a random process that is commonly re- ferred to as the error process. An understanding of the error process is of fundamental importance for a wide variety of reasons, e.g. design of high level (network layer and above) protocols, retransmission strategies, error correction and concealment strate- gies etc. The IEEE 802.15.4 low rate—wireless personal area network (LR-VVPAN) standard [5] is of particular interest to the wireless sensor network (WSN) research community because it is the first wireless communication standard built around devices with severe constraints on power consumption rates. Thus it is widely anticipated that IEEE 802.15.4 will play a major role in WSN applications. This chapter analyzes the performance and contributes to the understanding of IEEE 802.15.4 based LR- VVPANS. The objective of this empirical study is it to gain better insight into the time Varying error process. We begin our analysis with a correlation analysis of the bit Error rate (BER), link quality indication (LQI) and received signal strength indica- tion (RSSI) processes and establish that if a packet’s BER is known to be non-zero, 18‘ it has failed the cyclic redundancy check (CRC) test, it is correlated with its LQI and RSSI measurements. Based on the knowledge and the empirical data set We Come up with a model for the BER’s probability density function (PDF) driven by Channel state information (CSI) measurements. We evaluate the utility of this model in different environments by dividing the data set along lines of different col- leCtions environments, generating models for each of them and, using traces from Other environments as test data, measuring divergence between models and test data. We further analyze the amount of memory in IEEE 802.15.4 LR—VV PAN links at the 34 packet, symbol and bit level. 3.1. 1 Previous Work To develop a better understanding of wireless channels’ error and loss processes, several recent data trace collection efforts have targeted a variety of wireless networks, including 3G networks [70], WaveLAN and 802.11x WLANs [93],[67],[66],[133],[105], CCllOO based MICA2 networks [137] and 802.15.4 LR-WPANS [77],[116],[115],[64]. All of these efforts involve the collection of received data while offering different levels of insight and resolution (e.g., bit.-, byte—, and / or packet-level) into the error process on wireless channels. These studies usually focus on what is referred to as the residual error process. In general, residual errors are bit-level or packet—level errors that are not corrected by the PHY-layer and hence appear at the MAC-layer. Such errors (usually) cause packet drops in traditional wireless MAC protocols such as IEEE 802.11 and IEEE 802.15.4. Most the error trace collection efforts restrict the error process resolution to packet—level information. The most that can be extracted from packet-level traces are statistics such as 0 Packet reception rates (PRR), the fraction of transmitted packets that are re— ceived error-free and pass the CRC. . Packet error rates (PER), the fraction of transmitted packets that are received with at least one bit in error and fail the CRC test. - Packet loss rates (PLR), the fraction of transmitted packets that are not received at all. By our definition of these terms. PRR = 1 — PER — PLR (3.1) 35 Table 3.1: Traffic information and statistics collected in various studies. Network PRR PLR/ Bit Truncated CSI PER Errors Packets Available [93] WaveLan J [66],[67] IEEE 802.11b J J [77] IEEE 802.15.4 J J [116],[115] IEEE 802.15.4 J J [133] RFM/MICA J [137] CC1100/ MICA2 J J [105] IEEE 802.11x J J [64] IEEE 802.11g J J J This Work IEEE 802.15.4 J J J J J Khayam, et al. work in [67] was arguably the first bit-level residual error trace collection efforts for 802.11b/g W’LANs. Meanwhile, there have been other trace collection efforts for the more recent IEEE 802.15.4 LR-VVPAN, but like most 802.11 trace collections these too are limited to the observation of packets that pass the CRC test. Table 3.1 tabulates the statistics and observable parameters in various works. The collection of data packets for traces is often augmented by recording of addi- tional information with each packet. Various wireless networking standards require measurement of physical layer channel conditions. For example, 802.11b/ g requires the measurements of signal-to—noise ratio (SNR) and background traffic noise level. Sirnilarly, 802.15.4 mandates the measurement of RSSI and LQI of each received paCket. We refer to all such measurements by the umbrella term CSI. As the side-by- Side comparison in Table 3.1 shows, our error traces are by far the most detailed in terfns of data collection and the recording of CSI. Our traces distinguish themselves in that they log are he only ones to provide bit-level residual error traces for IEEE 802.15.4, the positions of lost packets, as well as partially lost packets, a phenomenon, 36 which is probably unique to 802.15.4, and whose cause is explained a little later in this chapter. Further details regarding the meaning and definition of these parameters will also be provided. The remainder of this chapter is organized as follows. Section 3.2 provides a de- tailed description of the setup used for trace data collection. Section 3.3 establishes the degree to which CSI measures provide information about the BER process. Sec- tion 3.4 uses maximum likelihood estimation (MLE) to arrive at a CSI driven model of the BER process. Section 3.5 evaluates the CSI driven BER model. Section 3.6 concludes this chapter. 3.2 Trace Collection Setup To our knowledge, this is the first detailed trace collection effort for IEEE 802.15.4. These traces differ from previously collected ones in quantitative and qualitative as— pects. We collected error traces of approximately 10 million packets in a way that Provides, to the authors’ best knowledge, an unprecedented level of insight into the effects of the wireless channel state on the level of corruption of packets. 3-2-1 Experimental Setup The trace-collection setup is depicted in Figure 3.1 and consists of a Crossbow MI)1R2400 MICA2 mote [34] transmitter and another MICA2 mote mounted on a Crossbow MIB600 Ethernet gateway [33] as receiver. The gateway is connected to a host PC running an application that continuously retrieves data from the receiver and logs it. 37 3.2.2 Packet Payload TinyOS [75] is one of the most widely used open source operating system in WSN devices. TinyOS v1.1 allows various packet. formats to be transmitted. We suitably modified code to enable the standard 802.15.4 frame format which TinyOS v1.1 labels CC2420 Frame Format (after the Chipcon CC2420 chipset [120] used in MICA2 devices). Strictly speaking, the term packet refers to the protocol data unit (PDU) exchanged between network layers of the transmitter and receiver while the term frame is used for PDU’S exchanged between MAC layers. However, since our analysis is restricted to the MAC layer alone there is little cause for confusion and we will be using these two terms interchangeably to refer to MAC layer PDUs. The exact MAC frame format used is shown in Figure 3.2. The size of the frame is 41 bytes and comprises of a 1 byte Length Field, 2 byte frame control field (FCF), 1 byte sequence number, 2 byte destination PAN ID, 2 byte destination address, 1 byte type field, 1 byte group field, 29 bytes of data/ payload followed by a 2 byte frame check sequence ( F CS) containing a CRC. The contents of the payload field are of our own choosing and consist of 3 unused bytes, the Source Address, the Destination Address and 6 CODies of a 32 bit sequence number. The sequence number in the data/ payload is Used to keep track of lost packets. If the sequence number between two consecutively r eceived packets skips one or more numbers that is indicative of a packet loss. The Sequ ence number field alone proves insufficient for this task in the face of long fades. A130 , a single bit error in the 1 byte counter could easily become a source of ambiguity (did we just lose two long sequences of packets or receive bit errors in the sequence nuTuber field?) Note that transmitted packets differ only in the 1 byte sequence nuTuber in the header and the six 32 bit sequence numbers in the payload, and the CRC. For a particular trace all remaining bits remain unchanged. However, since the wireless channel will introduce bit errors the copies of the sequence number used 38 to track packet losses in the received packet may differ. For this purpose we use a majority vote of the received sequence numbers to determine the transmitted sequence number. From this we reconstruct the contents of the Data/ Payload field and hence the transmitted packet. 3.2.3 Trace Generation Bit-level error traces can be generated by comparing a transmitted packet with its received version. A simple bit-wise XOR operation on the transmitted and received packets yields a bit pattern in which a zero (‘0’) signifies a bit that is received without error while a one (‘1’) represents an inverted bit. We observe that in some cases the length of the received packet is shorter than the transmitted packets. This constitutes a partial loss and we use the term truncated packets to refer to such packets. An erased bit in a received packet will be denoted by a two (‘2’) in the error trace. Truncated packets are logged when bits in the MAC header’s length field are inverted and the receiver stops listening to the wireless channel prematurely. It has also been observed that if bits in the length field are inverted in such a way that the length of the incoming PaCket appears longer than actual the length of the logged packet still equals that Of the transmission. Although the Length field in the received packet may falsely indi cate a longer packet, the absence of a carrier signal allows the receiver to detect the end of the transmission. 3-2 -4 Channel State Information Each received packet’s logged entry is accompanied with three pieces of packet level CSI parameters. The first is the FCS status of the packet modeled by random variable (1’ \Vith the nth packet’s F CS status is represented by d)[n]. Ordinarily receivers only distinguish between two states, i.e. F CS Pass (denoted 39 Receiver MICA2 Mote Ethernet Gateway \ Host PC <——Dat Transmitter MICAz Mote ] IEEE 802.15.4 (2.4 GHz ISM) Figure 3.1: Equipment setup for trace collection. Octets: 1 2 1 2 2 1 1 29 2 Frame Sq Best Best Data / Le“ Control No PAN ID Addr TV“ (3'9 Payload FCS 2 1 1 4 4 4 4 4 4 1 0x8 Src Dst SeqNo SeqNo SeqNo SeqNo SeqNo SeqNo 0x 401 Adr Adr (1) (2) (3) (4) (5) (6) 00 Figure 3.2: CC2420 MAC frame format used for experiments. by <1")[7L] = 0) if the CRC value in the F CS field matches the CRC of the received Packet, and FCS Fail if does not. Since we have knowledge of packet erasures and Size of transmitted packets we extend the definition of FCS status to accommodate the reason for failure. We restrict the definition of F CS Fail BE (denoted by (l)[n] = 1) to IIlean that the size of a received packet matches the size of the transmitted packet and the CRC failure is due to bit errors (BE). We further define two additional states, FCS Fail PL (denoted by gb[n] = 2) and F CS Fail CL (denoted by ¢[n] = 3), where PL and CL are abbreviations for partial loss and complete loss respectively. Packets 40 Figure 3.4: Residential deployment environment. that. are partially lost cannot pass the CRC test and are marked FCS Fail PL. Packets that are not received at all, i.e. when the decoded Sequence Number at receiver skips, are marked FCS Fail CL. The Crossbow MICAz sensor mote uses a TI Chipcon CC2420 transceiver chip [120] for its communication subsystem. The CC2420 is an IEEE 802.15.4 compliant radio interface. In accordance with the standard, the receiver measures RSSI. The 41 RSSI constitutes the second piece of our CSI parameters and is modeled by random variable P and the nth packet’s RSSI denoted by p['n]. The RSSI is recorded as an 8 bit, signed 2’s complement value. Technically, the CC2420 does not measure the LQI directly. Instead, it measures tl‘le correlation CORR between the first 8 received symbols (of the PHY header) a11d a corresponding 8 known symbols (preamble). IEEE 802.15.4 uses 16-ary Offset.- Quadrature Phase Shift Keying (O-QPSK) modulation which encodes 4 bits in one s}' rnbol. The first 8 symbols, 4 bytes, of the PHY header comprise of the Preamble s<2<111cnce consisting of 32 binary zeros. The LQI is then defined as LQI = (CORR — c1) - c2. (32) where the two constants c1 and c2 are functions of the Packet Error Rate (PER) measured over an extended period of time and are determined experimentally. c1 and c2 serve to scale the 7 bit value of the correlation to the full range of an 8 bit 11111111381”. Since 8.2 is merely a linear transformation of the measured CORR we Sirnply take C1 = 0 and ('2 = 1. The LQI is modeled by the random variable A and the ’nth’ packet’s LQI denoted by Mn]. Although the BER process is not considered a CSI measure we are including it here nevertheless. The BER process is modeled by random variable B and the nth packet’s BER is denoted by Mn]. It must be mentioned here that the term BER is not used in its strict traditional sense where it denotes the long term average probability of a bit error, such as in a binary symmetric Channel (BSC). Instead the BER is computed over each individually received packet. Thus, for the nth received )acket it is defined as, I Number of inverted bits in. nth received packet BER = mm] = (3-3) Length in bits of Tim received packet 42 Table 3.2: State space variables, symbols and values. Quantity Symbol of Symbol of Real- Valid Values Assigned to Packet Level ization of Random Random Processes Random Pro- Process cess FCSStatus (I) ab[n] qb = r 0, F CS Pass 4 1, FCS Fail BE 2, FCS Fail PE A 3, FCS Fail CL RSSI P p[n] p E Z /\ —128 S p 3127 LQI A A[n] AEZ+AOSA_<_127 BER B sin] BeR+Aogsgi The value of B[n] associated with the nth packet is the instantaneous measure of the BER over that packet. Note that at this point we do not make any assumptions about the distribution of the inverted bits within a packet. Completely lost packets, with q) = 3, are assigned [1 = —128, /\ = 0, and l3 = 1' Readers might argue that transmitter receiver separation could have been included as another dimension of the phase space. However, numerous previous works like 1101] and ones listed in Table 3.1 have already established the tenuous nature of the relationship between CSI and distance. Hence, transmitter receiver separation is excluded from the phase space. Thus each received packet is characterized by its FCS Status, LQI, RSSI and BER processes. Together they constitute four state space variables of our system. Table 3.2 summarizes this notation and lists the range of possible values each may assume. 43 3.2.5 Spectral and Environmental Diversity The traces collected in this study are divided into two sets, a multi-channel (MC) trace set, and a multi-environment (ME) trace set. In order to obtain sets of traces rich in environmental diversity, traces in the ME trace set were collected over a period of months, at different times of the day, in office, residential and outdoor environments. All ME traces were collected while operating in channel 26 in the 2.48OCHz band. The reason for choosing channel 26 was the fact that it is the channel in the frequency spectrum that is the farthest removed from all 802.11bg frequency channels. Each trace collection is characterized by the locations of the transmitter and receiver, separation between them, packet transmission rate to in packets per sec- ond (pps) and whether communication was line-of—sight (LOS) or non-line-of-sight (NLOS). For all our traces the transmission power was kept constant at the default OdB which corresponds to 1777.11". Figure 3.3 and Figure 3.4 depict floor plans of the environments in which traces were collected. The circles labeled T1 through T18 denote transmitter locations. The corresponding locations of receivers are marked by R1 through R18. For the remainder of the chapter, we refer to individual traces TRl through TR19. Traces collected in the same location are collectively referred to by the name of the trace collection environment. This way T R1 through T R8 are collec- tively referred to as the ‘Hallway’ trace set, TR9 through TR15 as the ‘Lab’ trace set, TR16 and TR17 as the ‘Residential’ trace set and TR18 and TR19 as the ‘Outdoor’ trace set. With the exception of the ‘Hallway’ traces none of the environments had any significant WLAN interference sources. Traces are subject to interference from cordless phones and microwave ovens. Table 3.4 briefly characterizes the various trace Sets by providing PER, PLR and PRR of each. The MC set consists of 16 traces, labeled MC-ll through MC-26, all collected in the same residential, non-line—of—sight (NLOS) setting with 15 feet transmitter- 44 receiver separation. The transmitter is operated at full transmission power. Each MC trace is collected at one of the 16 channels numbered 11 through 26 specified by IEEE 802.15.4. The residential environment used for the collection of the MC set is subject to interference from multiple IEEE 802.11x W LANs. At the time the MC set was collected there were two networks in WLAN channel 1, two networks in channel 6, one network in channel 10 and 2 networks in channel 11 with vary'ing activity levels. Figure 4 of [56] depicts the population of the 2.4GHz ISM band and what IEEE 802.11b/g WLAN channels interfere with which IEEE 802.15.4 LR—WPAN channels. Furthermore, the transmit power of IEEE 802.11b/ g devices is 30mW which is significantly higher than the 1mW of 802.15.4. As Srinivasan, Dutta, Tavakoli and Levis reported in [115], to a co-located 802.11 WLAN sharing the same spectrum traffic from IEEE 802.15.4 devices appears as noise. One might argue that since interference scenarios are part of our evaluation, other interference sources occupying the ISM band (see figure 3.5) such as Bluetooth/ IEEE 80215.1 [4], microwave ovens and cordless phones should also have been part of our traces. However, as Sikora and Groza have shown in their study [112] on the coexistence of 802.15.4 with other systems in the 2.4GHz ISM band, co—located Bluetooth networks and microwave ovens have no discernible effect on the operation of IEEE 802.15.4 networks. The Effects of 802.11b/ g networks on the other hand are significant and have been the Subject of many studies ( [112], [48], [132], [102]), which is why we have only included 802.11b/ g networks as interference sources. 3.3 Correlation Analysis of CSI Measures A primary objective of this study is to model the probability density function (PDF) of the BER process B conditioned on CSI. It is important to highlight that although we were able to observe the BER process in our trace-collection study, in an actual 45 Table 3.3: Collection environments of various traces in the ME trace set. Trace Environment Interference Distance LOS/ Sources (feet) NLOS ME—l Office bldg corridor 802.11x 40 LOS (strong) ME—2 Office bldg corridor 802.11x 60 LOS (strong) ME—3 Office bldg corridor 802.11x 70 LOS (strong) ME—4 Office 802.11x 2O NLOS ME—5 Office 802.11x 20 NLOS ME—6 Residence 802.11x (multi- 15 NLOS ple networks) ME-7 Office bldg corridor 802.11.x (low) 20 LOS ME—8 Office bldg corridor 802.11.x (low) 50 LOS ME-9 Office bldg corridor 802.11.x (low) 100 LOS ME—IO Office bldg corridor 802.11.x (low) 80 LOS ME-ll Outdoors - 100 LOS ME-12 Office bldg corridor 802.11x (low) 120 LOS Table 3.4: Error rates in trace sets. TraceSets PER PLR PRR Hallway 0.1877 0.0762 0.7361 Lab 0.0275 0.0161 0.9564 Residential 0.0993 0.0420 0.8587 Outdoors 0.0005 0.0030 0.9965 46 2.412 GHz 5 MHz 22 MHz \ \ 9.9“?“ N \ .1555... 2.405 GHZ 5 MHZ 2 MHZ Figure 3.5: IEEE 802.11b and IEEE 802.15.4 channels in the ISM band. IEEE 802.15.4 MK 24 25 26 .3 .h 11 network application the error process can only be estimated; and hence )3 [n] is not observable in actual networks. However, all other processes (cf)[n], {)[n], and /\[n]) are observable. Hence, the problem of determining p([3[n]), the PDF of the error process 5[n], for the nth received packet based on observable CSI measures /\[n], p[n] and ¢[n]. Note that this is different from prior uses of CSI such as in [116] where it is shown that the average PLR/ PER of a link is correlated with the average RSSI. When gb[n] this indicates that the received packet passed the CRC and can be considered free 0f errors, i.e. [3 [n] == 0 with certainty. When at = 3 the packet is erased completely and there is no data and no CSI available. This leaves us to focus on the cases when 4) = 1, 2, i.e. the received packet contains errors and/or is partially lost, i.e. Alr‘1],plnllcbl'nl = 1, 2 -+ Jot/5171]). 47 Reducing the uncertainty surrounding the PDF of ,S[n] of a packet received with some bits in error on the basis of its LQI and RSSI implies that these CSI measurements are somehow correlated with p(1’3[n]). We begin by establishing that CSI parameters are indeed highly correlated with the actual BERs of packets by means of correlation based analysis. The uncertainty in the knowledge about p(,13[n]) is measured in terms of its variance. Packets with low BER are expected to have high RSSI and LQI, and vice versa. Thus, to qualify as ‘useful’ RSSI and LQI must both be negatively correlated with BER. Let T 27(1'3 ) denote a signal consisting of the BERs observed for packets captured in trace TRi. If X and Y are two random variables with means E [X] and E [Y], then the correlation coefficient ny(t) is defined as, C0v[X, YA] \/Var[X] Var[Yt] EllX - Ele)(Yt — ElYtlll _ (bier?) - E21Xl \/Em21 —— E21121 RXYU) = Where Yt is the t time delayed version of Y. When correlation is computed for a range of time delays the set of correlation coefficients so obtained will be referred to as a correlation function. For every trace we treat the observed values of state Space Variables B, /\ and p as time series signals and compute the correlation coefficients between them. Ideally we would like to see R B p(0). the cross-correlation coefficient of B and P, and RBA(t), the cross-correlation coefficient of B and A, to be very close 130 —1. For sake of completeness we also computed R p A(t), the cross—correlation Coefficient of P and A. These values are computed separately for different trace sets by concatenating signals of state space variables from all traces contained in a trace set. Strictly speaking though, correlation coefficients should be computed separately 48 Table 3.5: Cross correlation of different random processes. RBAU) RBPU) RAP“) Hallway -0.4662 -O.2938 0.8414 Lab -0.2745 -0.0919 0.5978 Residential -0.2071 —0.0091 0.5346 Outdoors —0.3262 -0.1613 0.8443 for each trace. However, the results shown in this subsection change very little across traces in the same trace set. Therefore, for brevity reasons we are presenting results for the set of concatenated traces. As Table 3.5 shows, for packets observed at the receiver (packets with (b = 0,1,2), both RSSI and LQI have exhibit a moderate to strong negative correlation with the BER. Furthermore, RSSI and LQI are also strongly correlated. This trend is also observable in a visual inspection of the data. We are able to obtain the joint distribution pBAPCI)(1B1A1p1d’) and from it any conditional distribu- tion, such as pB(/3]/\, <25 = 1, 2) and pB(/3|p, (b = 1, 2), by means of the error traces we collected. Figures 3.6 and 3.7 show two conditional distributions p 3(5 |/\, (D = 1, 2) and p 3(8] p, qb = 1, 2), respectively. The axis along the left hand side of the horizontal plane is the BER axis. The axis along the right hand side of the horizontal plane is the CSI measure (LQI in figure 3.6 and RSSI in dBm scale in figure 3.7). Thus for each value of LQI and R881 the figures depict a valid PDF of BER. Figure 3.6 depicts how variance and average BER of packets in the low LQI range increases which is in accordance with our previous observations. The same trend is visible for RSSI in figure 3.7. Thus, the figures depict inverse relationships of the BER with both CSI measures. Our analysis so far leads us to conclude that both RSSI as well as LQI measurements made with each received transmission have the potential to serve as good indicators of the BER for that particular packet. 49 PDF of BER conditioned on LQI pB(BIX.¢=1.2) 100 Figure 3.6: PDF of B conditioned on A and (I) = 1, 2. 3.4 CSI Driven BER Model In this section we employ maximum likelihood estimation (MLE) to determine the parameters opr(B|)\, p, (b = 1, 2), an exponential PDF modeling pB(B|)\, p, (b = 1,2). From collected traces we observe that the BER PDFs are always decreasing functions. We will be modeling PDFs of BER by a discretized exponential PDF. The shape of the exponential PDF is determined by a single parameter b as shown in 3.6, —a: e7; :1: 2 0. (3-6) o-IH f(:13;b) = The MLE estimates of parameter b can be obtained from a data set by, b = qu. (3.7) 50 PDF of BER conditioned on RSSI pBelp.¢=1.2) 0.3 ‘82 Figure 3.7: PDF of B conditioned on P and = 1, 2. The MLE of b for all observed combinations of values of (A, p) constitutes a model of the BER process. b(A, p) are depicted in Figure 3.8. Depending on the objective of the application seeking the channel state estimate, pB(,B|A, p, (b = 1, 2) can now either be used as is or mapped to a single numerical value representative of the channel state. For lack of a better graphical representation, figure 3.9 shows pB(b’|/\,p = 88dBm,d = 1,2), the PDFs of the BER process observed over the range of LQI measurements with RSSI fixed at 88dBm (chosen arbitrarily for illustration purposes). Figure 3.10 displays the same PDFs modeled by MLE exponentials. The above model leaves us with two very important questions. Q1: How useful is this model in terms of reducing uncertainty or variance of the BER’s PDF? 51 Parameters of exponential PDF at different LQI and RSSI b(?».p) = ElpB(BI?~,p)l -84 '82 A. 60 —90 ‘88 ‘86P (dBm) Figure 3.8: Values of b for various (A, p). Q2: How universally applicable is this CSI driven BER model especially when we consider that wireless channels behave very differently in different environments? We will address these two questions in the following section where we evaluate this model. 3.5 Model Evaluation 3.5.1 Variance Reduction Taking variance as a measure of uncertainty in stochastic systems we evaluate the expected value of variance in estimates of the BER. In other words, we contrast the performance of LQI and RSSI used individually and when used in conjunction by evaluating the expected value of the variance of estimates of the BER’s PDFs, i.e. E[VAR[pB(/3[,\,p,¢ = 1,2)]] = E[VARB|AP], E[VAR[pB(,B|A,¢> = 1,2)]] = 52 Actual pB(|3|}t,p=88dBm) from collected traces pB(l3l7t.p=88dBm) Figure 3.9: The PDFs of the BER obtained from the actual traces for various LQI measurements at an RSSI of 88dBm, pB(_B|/\, p = 88dBm, ab = 1,2). E[VARBIA], and E[VAR[]BB(,8]p, (,5 = 1,2)]] = Ell/ARBIP]. These expected values are computed over the joint PDF pAP(/\, p|¢ = 1, 2) of LQIS and RSSIS with which packets with errors are received, also obtained from our traces. Table 3.6 tabulates the expected value of variance with which we estimate the BER process. Clearly, once again we see that using LQI and RSSI together is more beneficial and estimates the error process with lesser uncertainty. 3.5.2 Dependence On Deployment Environment So far we have established that for every error-prone packet with g") = 1, 2 it is possible to obtain a better estimate of the PDF of its BER based on measurements of RSSI and LQI. Ideally, we would like to make this estimate dependent solely on the RSSI and LQI and would like to see little or no dependence on the physical environment. 53 Model of pB(|3|?t,p=88dBm) based on MLE of exponential PDF =88dBm) pB(l3l7~.p 0.1 100 Figure 3.10: The PDFs of the BER for the same range of LQI measurements at RSSI of 88dBm as modeled by a discretized exponential PDF, pB(i3|/\, p = 88dBm. (0 = 1,2). To evaluate the application of the CSI driven BER model in different environment we partition the data set according to collection environments, i.e. ’Hallway’, ’Lab’, ’Residential’, and ’Outdoor’, and use'cach to arrive at a CSI driven BER model independently. Ideally the four models so obtained should be identical. As we already know, each model is a set of PDFs. If /\ and p vary in the ranges )‘mz'n S /\ g Amaa: and pmin _<_ p S pmaay, respectively, that means each model will consist of (at most) Table 3.6: Expected value of variance when using different combinations of RSSI and LQI as CSI. Expected Variance E[VARB]; CSI = None 1.7000 x 10—3 ElVARBIA]; CSI = LQI 8.0863 x10"4 E[VARBIP]; CSI 2 RSSI 8.1242 x10—4 E[VARBMP]; CSI = LQI + RSSI 5.7524 X10—4 54 (Amag; — )‘min + 1) x (pmaj; — pmz’n + 1) number of PDFS pB(B|)\,p,¢ = 1,2), one PDF of B for every combination of possible (Aha) tuples, we Show that the PDFS pB(fi|/\, p, 05 = 1, 2) obtained from one trace set closely approximate the PDFS p BM} I/\, p, 45 = 1, 2) of a different race set. for the same values of (A, p). This way traces the CSI driven BER model derived using data from one environment will be verified against test data collected in a different environment. At this point. we require a measure that quantifies the degree of similarity between two PDFS. A well established divergence measure is the Kullback-Lez’bler Divergence (KLD), also known as relative entropy. The KLD of two PDFS p X and py is denoted by D(p X H py) and defined as, Dex II 103/) = Z pxmzogf (3.8) Sp X denotes the region of support of PDF p Xv or the elements in the domain 0f PX for which pX(:I:) > 0. Note that according to the definition of D(pX H py), if Sp X Q SPY then for any :1: g2 Sp X the KLD is 00. Although this should not happen in a large data set consisting of a comprehensive set of traces from various 10Cations, trace packets in individual partitions of the data set might not exhibit SUfficient diversity across the entire spectrum of possible values of (A, p) to avoid such a result. To circumnavigate this pitfall in our analysis we use a modified form of the KLD called the K-directed divergence (KDD) introduced by Lin in [76] which is defined. PX (1") ) K = E a? lo . ~ (I? X H Py) $6 p px( ) 9 (%p (‘17) $1) (y) (3.9) The KDD’S most significant feature relevant to our application is that the denomina- t01‘ of its fractional term will never be zero, and hence the KDD cannot evaluate to co. Thlis, to measure the similarity between PDF 158— X03 |/\, p, 09 = 1,2) derived from 55 traces collected in an environment X and a PDF pB_Y(,8|A,p, cf) 2 1,2) of traces collected in an environment Y we employ the KDD. A complete comparison of two environments will require the computation of KDDS for each (A, ,0) pair. This yields an entire set of KDD measures. Ideally, all KDDs in this set should be close to zero. In figure 3.11a we plot the histogram of the set of KDDS obtained from comparing the CSI driven BER model derived from the ’Residential’ set with the PDF of the data collected from the ’Office’ trace set. As the histogram shows, the vast majority of KDDs are zero, with very few that are non-zero but nevertheless close to zero. Similarly, figure 3.11b is the same histogram plot for PDFS from ’Hallway" and ’Outdoor’ traces. A particular reason why we chose this example for illustration is that. it uses the ’Outdoor’ trace set which exhibits and significantly different from that of the other three sets (see table 3.1). Those differences are manifesting themselves in a less obvious way in the histogram of KDD values in figure 3.11b. The histogram rises to a non—zero entry at the bin centered at 1 which, however, remains insignificant in Comparison to the number of entries in the bin centered at O. For the vast majority 0f Valid (A, ,0) pairs the KDD between different trace sets is zero. we conclude that the CSI driven model for the PDF of the BER process is applicable in a variety of environments. 3 - 6 Conclusions 7 . . . VA e collected and analyzed an extcns1ve and diverse set. of res1dual error traces from 802.15.4 links. Listed below are our conclusions. 1. LQI and RSSI exhibit moderate negative correlation with the BER process (and strong positive correlation with each other). 2. LQI and RSSI can be used to reduce uncertainty regarding in the BER individ- 56 80,000 60,000- # of KDDS 20,000* 80,000 60,000 40,000 # of KDDS 20,000- Figure 3.11: Histogram of KDD values for a) Model from ‘Residential’ trace set and ‘Lab’ traces and b) Model from ‘Hallway’ trace set and ‘Outdoor’ traces. 40,000" ' Residence vs Lab j 0T2 (it 06 0:8 K(pB-Residence“pB-Lab) (a) j 'Hallway vs Orutdoor' 0:2 0:4 ofe oia K(DB—Hallwayl"DB-Outdoor) (b) ual packets are subjected to. 3. The CSI driven BER model remains valid across a variety of physical environ- ments. 57 Chapter 4 Memory Properties of the Link-level BER Process in IEEE 802.15.4 Links 58 4. 1 Introduction Communication channels in the real world are not perfect and are prone to introduce errors into transmissions. Errors are orders of magnitude more frequent in wireless channels than in wired channels. Design of network protocols and other architectural components of wirelessly networked communication systems entail a better under- standing of the error process that affects transmissions. The memory length of the error process is an important parameter of interest that has to be taken into con- sideration in the formulation of channel models. In particular, channel models that take into account the persistence of errors in wireless channels, such as those based on Markov chains, require information about the memory length of the error process. Previous works ( [68], [66], [67]) measuring memory length in 802.11b channels were restricted to the bit-level error process and relied on the correlation function based analysis, which sometimes worked well enough at that scale. We were the first to perform bit-level analysis for IEEE 802.15.4 low rate-wireless personal area network (LR~WPAN) [5] channels and extend it to symbol and packet—level error processes in [56]. In this chapter we are extending our previous analysis by using a much larger data set that spans not only the set of all 16 channels in which 802.15.4 operates, bUt also a variety of physical environments. The failure of traditional correlation analysis is explained using results from [54]. At the bit and symbol level the error Processes are modeled by binomial processes (a bit / symbol is either received correctly or incorrectly). The packet-level process is called the bit error rate (BER) process and is denoted by B. The BER process B is defined as a series of measurements of h the rate at which each packet has been subjected to bit-errors. The n.t measurement in a realization of B is denoted by Mn] and is computed as shown in equation 8.1. # of bits in nth packet received with. error (4 1) [i n = j J # of bits received in nth packet 59 We are concerned with determining the memory length of errors due to the effects of slow and fast fading. As we will demonstrate, the determination of this memory length is complicated by several factors which include slow fading, non-stationarity due to long stretches of interference, and periodic interference. A way around the ef- fects of slow fading and interference is to preprocess the BER process by de-trending and normalization [131]. However, this is complicated by their non—periodic, unpre— dictable nature. Like some prior works that measured memory length of errors, this research too depends on bit-level, binary signals, called residual bit-error traces (short: error traces 0r traces), representing the positions of bit—errors in received transmissions. The basic concept of error traces is very simple and is explained easily enough. An error trace is a map of bit positions of all packets collected in the course of a trace collection session that reached the receiver with errors. Conceptually, for a single packet such a bitmap of errors is obtained by comparing a transmitted packet (free of errors) with its received version (may contain errors and failed the cyclic redundancy check). This way the sequence of BERs computed by equation 8.1 for each packet in a trace constitutes the BER process. The complications involved in working with traces arise due to lack of access to low level drivers and / or firmware that need to be modified to gain access to packets received with errors, otherwise discarded by receivers. The remaining chapter is organized as follows. Section 4.2 demonstrates the use of correlation coefficient in measuring the memory length of bit, symbol and packet-level error processes. Section 4.3 presents the results of Hurst analysis on the packet-level BER process. Section 4.4 describes relative mutual information (RMI), an alternative means of measuring memory of in measuring the memory length of the BER process observed of IEEE 802.15.4 LR—WPANS channels. Section 4.5 concludes the chapter. 60 4.2 Memory Length Measurement By Correlation Analysis 4.2.1 Correlation Function Let X be a random process consisting of random variables [X 1, X2, . . . , X N, . . .]. The corresponding measurements in a random process are denoted by [51:1,:1:2,. ..,:1:N, ...] X (m) is an m time unit delayed (right-shifted) version of X. To measure memory length we compute the correlation coefficient of X and Xim) for a range of values of m. Thus, the correlation coefficients denoted by R X(m) are a function of m and are defined as, UXUX(m) 0X0X(m) . (4'2) Here Cov (X , X (m)) denotes the covariance of X and X (m), o X the standard deviation of X, p X the mean of X, and E [] the expectation function. This function of m is also known as the correlation function or correlogram. The value of m after which the correlation function RX(m) becomes ”insignificant” and drops below threshold Rt is the memory length [W X of process X. There is no clear consensus on what the value of Rt should be. In the simplest of cases the smallest value of m for which the correlation function is 0 or close to it is taken as a measure of M X' There is a 95% significance level that is frequently used as a. rule of thumb to determine whether M’ X is zero (successive measurements in X are independent) or non-zero (successive measurements in X are not independent). For a signal of N consecutive 2 measurements the 95% significance range is defined as TW' If 95% of correlation coefficients for m in the range 1 S m 5 14V— lie within this specified range, then 61 (b) All bit-level traces of the ME trace set. Figure 4.1: Auto-correlation functions for bit level traces of the MC and ME trace sets. consecutive measurements are deemed independent, leaving M X = 0. 62 (a) All symbol-level traces of the MC trace set. (b) All symbol-level traces of the ME trace set. Figure 4.2: Auto—correlation functions for symbol level traces of the MC and ME trace sets. (4.3) min (Rx(7n) < Rt) . m MX= 63 4.2.2 Correlograms of Bit and Symbol-level Traces For analysis of bit and symbol-level error processes we compute Rb(k) and R3(k) defined as, R 1.: =ER Am? ,Rsk =ER5k,i. b() lb( )l (l l ( )l (4.4) h packet’s bit and Rb(k,i) and R3(k,i) are the correlation functions of the it symbol traces with its kth‘ following packet, respectively. The correlation functions Rb(k) and 123(k) of a particular trace are computed as the expectation function over i of Rb(k,i) and R3(k,i), respectively. If for a k > mb,m3 the correlation functions Rb(k) and 123(k) drop to a value very close to zero, then mb and 7713 are the bit and symbol-level channel memory of the channel. Figures 4.1a and 4.1b plot the auto—correlation functions or correlograms of all bit-level traces in the MC and ME trace sets, respectively. What is apparent from this figure is that. in spite of the wide variation in trace collection parameters, we consistently observe a bit-level channel memory mb of at most 2 bits across all traces regardless of channel frequency and environmental differences. Similarly, figures 4.2a and 4.2b are the correlograms of the symbol-level traces for the MC and ME trace sets, respectively. Horn both correlograms it is clearly visible that symbol level memory ms is also (at most) 2. Therefore, there is no further need to check for long range dependence (LRD) and we conclude that the bit and symbol-level error processes in 802.15.4 wireless channels have constant memory of (at most) 2 bits and 2 symbols, respectively. 4.2.3 Correlograms of Packet-level Traces Figure 4.3 depicts the correlogram functions for all 16 traces in the MC trace set, and figure 4.4 for the 12 traces in the ME trace set. For the computation of the 64 autocorrelation function, the length of each of the traces is truncated to a uniform N = 100,000 points, making the 95% significance range [—0.0063,+0.0063]. By this measure it appears as if all channel traces exhibit memory to some degree. To determine just how much memory several rules of thumb have been used in literature. These include; Rt = min,- (RB(i) = 0) : Correlation coefficient falls close to insignificance/zero. In all our analyzed traces this has rarely been the case. Rt = 0.1 x RB(1) : Correlation coefficient. drops to less than 10% of the coefficient at lag 1. By this standard, the memory length of the BER process will range in the tens to thousands of seconds. Rt = min, (IRB(i) — RB(j)| < 6) : Vj > i, 6 ——> 0 : Correlation coefficient becomes steady and subsequent changes between consecutive values are within a very small value 6. Periodic interference, most likely from IEEE 802.11b beacon frames, causes periodic spikes in the correlogram functions rendering this cri— terion useless. Furthermore, there is no clear interpretation of the value of correlation coefficients and the degree of predictability of one measurement on another. According to all these selection criteria for Rt, memory lengths of all these traces lie in the range of tens to hundreds of seconds. Clearly, that rules out correlogram analysis to measure memory length of fast fades. The failure of the correlogram anal- ysis is explained by the non-stationary nature of the BER processes captured by the traces. Figure 4.5 plots the BER process observed in MC-25, the trace of the MC trace set that was collected with devices operating in channel 25. For clearer visibil- ity, the BER process was pre-processed by passing it through a 600 point averaging filter. There is an initial period of about 14()Osec in which the channel experiences 65 0.5 - 0.4 f QAAAA A H :II". 1' " 03Hl:'1:'.:‘-AAA,A,AAAAA ' o',n',,'a‘ ‘ \l A mo- 1l-z1::: A A AAA ‘A’A’AAA 23 My 35 4 45 Figure 4.3: Auto-correlation functions for traces of the MC trace sets. a moderate BER which then increases to a much higher value for about 9003ec. It then reduces to a very low value and remains so for the remainder of the trace. We attribute these changes in channel conditions to interference from co-located devices sharing the spectrum in the 2.4GHz ISM band. When the correlation function is computed over a trace which experiences a change in channel conditions like the one in figure 4.5, the correlation function is expected to maintain a significant value for an extended period of time. 66 ME-1 ME-Z ME-3 ME-4 ME-5 ME-6 -~- ME? —0— ME-8 —El- ME-9 —A— ME-10 --+-- ME-1‘l -----x ME-12 0.6 Q I iiiill A... a "." .'\‘ ’ '5'“ , 3‘ a '\ 7"..‘rr ,-H~. _. ‘0' ‘ I . ---«' -n..-a..-.v.'.1*'. .% n ......- - ' n- 1.5 2 2.5 Figure 4.4: Auto-correlation functions for traces of the ME trace sets. 4.3 Hurst Analysis of Packet-level BER Process The correlation function alone did not allow us to make a definitive conclusion about memory length. For this reason we employ the Hurst parameter H for which several estimators exist in literature [10]. We use the Hurst parameter, (or Hurst exponent) as a means of determining whether a process is LRD or not. A stationary process is said to be LRD if there exists a real number 01 E (0, 1) and constant c]; > 0 for which, R(k) lim 2 1. (4.5) lit—>00 Cpk_a The Hurst parameter is defined as H = 1 — 7%. A process is determined to be LRD if 0.5 < a < 1. Several methods exist for estimating the Hurst parameter. In 67 l : High BER 0.1 Moderate ' Interval BER Interval- ...-1 Low BER interval p p o o o: oo Averaged BER f; A .0 o N A- - .4“ ““u‘ - 2000 3000 4000 5000 ‘60l00 time (sec) 0 1000 Figure 4.5: BER process of trace MC-25 after filtering by 600 point averaging filter. this work we use the Aggregate Variance, the R/ S method, the Periodogram method, the Absolute Value method, the Abry-Veitch estimator and the Whittle estimator, details for all of which can be looked up in [10]. We use the SELFIS tool deveIOped by Karagiannis, Faloutsos and Riedi as part of their work [63]. Figures 4.6a and 4.6b plot H B E R, the Hurst parameter of the BER process for the MC and ME trace sets using all the above listed estimators. In addition, for each trace we plot the average Hurst parameter over all estimators (thick line). The plots of the Hurst parameter are accompanied by those of three other quantities, i.e. the average packet error rate (PER), the average packet loss rate (PLR) and the average conditional bit error rate (CBER). The average PER for a trace is the ratio of number of packets received with failed CRC to total number of transmitted packets. The average PLR is the ratio of the number of packets never received by the receiver to the total number 68 of packets transmitted. The average CBER is the expected value of the BER of all received packets whose CRC failed. As all plots show, there are significant variations in the estimates of the Hurst parameter computed by different methods. Estimates of obtained by the absolute moments and aggregate variance methods consistently provide the highest estimates, whereas the ones obtained by Abry-Veitch and Whittle estimators are consistently the lowest. The ones provided by the Periodogram and R/ S methods fall approximately in the middle of this range. This observed ordering holds true for H B E R across MC and ME trace sets. 4.3.1 Observations For MC Trace Set For the MC traces we observe that most estimates of H B E R rise in three distinct places, peaking for channels 13, 17 and 25. Channels 13, 17 and 25 occupy the centers of the spectrum bandwidth occupied by interfering channels 1, 6 and 11 of IEEE 802.11b/g. The degree of interference experienced by channels is measured by the average PER and average PLR. Thus H B E R bear some correlation with the average PER and average PLR and, hence, the interference from nearby 802.11b/ g W'LANS. The Abry-Veitch estimator is the only estimator that defies this obser- vation and in fact exhibits inverse correlation with average PER and average PLR. Estimates of H B E R for channels experiencing strong interference are high enough to conclude LRD in the packet-level error process. But at the same time we observe that for 802.15.4 channels that do not experience interference from 802.11b / g WLANs estimates of H are close to or below the critical threshold of 0.5. It appears that in- herently the packet-level error process in 802.15.4 channels is not LRD, except when it is subjected to 802.11b/g interference. The explanation for this behavior comes from Karagiannis, Faloutsos and Riedi [63] who concluded that periodic interference in an otherwise memoryless channel can give the appearance of LRD (when LRD is 69 0.2" Q 0 A A A A Q n A a u D a A U D 8 ii a ° 8 8 5’ ° 7 8 a 9 i ? ° 2 12 14 16 18 20 22 24 26 MC-Channel # (a) MC trace set. +Aggregate Variance + R/S +Periodogram +Absoiute Moments +Abry—Veitch Estimator L +Whittle Estimator ‘ *Average H c Average CBER 0 Average PER A Average PLR 0.2T ‘ A ° '3 A ‘ 8 a a 0 E if D 4' L a R A A A A 2 6 10 12 ME—Trace # (b) ME trace set. Figure 4.6: Plots of estimates of the Hurst parameter obtained using various tech- niques along with their average BERs, PERs and PLRs. determined by estimating H). Moreover, LRD is also unlikely to exist in a process if estimates of H B E R by various methods do not converge, which is surely the case in our analysis. WLANs periodically transmit a beacon frame every lOOmsec that is used to synchronize the network. It is the periodic interference from these beacons 70 frames that is giving the appearance of LRD in the packet-level error process. 4.3.2 Observations For ME Trace Set Recall that all these traces in the ME set were collected in channel 26 to reduce effects of interference. Most traces in this set experience lower average PER and average PLRs. For many traces the average Hurst parameter often remains close to 0.5. Nevertheless, as in the case of the MC trace set, the estimates of H B E R still do not clearly converge to one value, and when they do it is in a range very close to 0.5. The lack of consensus among estimates, and the close proximity to 0.5 otherwise leads us to believe that the channels in the ME trace set are also not LRD. 4.4 Memory Length Measurement By Relative Mu- tual Information 4.4.1 Shannon Information Measures For random variables X and Y, with probability density functions (PDF) p X(:r) and PYW) and joint PDF gym/(1r, y), the mutual information I(X; Y) is defined as, (2:, y) 1(X;Y) = Z pXY(3’5> y) 10s2 pXY 1 . (4.6) Var,y;p(:v,y)>0 (px($)pY(J)> , Mutual information [32] can also be understood more intuitively in terms of en- tropy as, 1(X; Y) _—. H'(X) + H(Y) — H(X, Y). (4.7) More generally, mutual information is defined between two sets of random vari- 71 ables. If random variables X and Y in equation 4.6 are replaced by sets of random variables X1,X2, . . . ,Xn and Y1,Y2, . . . ,Ym, respectively, then pX(:z:), py(y) and pxy(x,y) are replaced by respective joint PDFs pX1X2.HXn(:r1,:r2, . . . ,crn) and leYg...Ym(l/1a92, . . . ,ym), and the joint PDF of all random variables leXZ...XnY1Y2...Y7n(I1’ 11:2, ' ' ' ,In, yl’ 3127 ' ' ' 33/771)’ 4.4.2 Description: Relative Mutual Information We are essentially faced with the challenge of evaluating; o How much information random variable Y can provide about another random variable X; 0 While at the same time providing a measure of the remaining uncertainty about X. The Shannon mutual information I (X ; Y) achieves the first goal. However, mutual information is not restricted to a fixed range. Thus, an evaluation of I (X ; Y) does not give us a sense of how much information about X or Y remains unknown. We use relative mutual information (RMI), denoted RM 1 (X ; Y), previously described by [29] and adopted by us for the purpose of memory length measurement in [57]. RMI is defined as; I(X;Y) (4.8) Note that while I (X ; Y) is a symmetric measure, by definition RMI is non- symmetric, i.e. RMI(X; Y) 7é RMI(Y; X) because H(X) 7E H(Y). Since 1(X; Y) S min (H (X), H (Y)), the RMI’s value is limited to the interval [0, 1]. An RMI close to 1 implies Y contains most of the information contained in X, leaving little uncertainty, while an RMI close to 0 implies the opposite. 72 l3(1m) ARM|B(1,m) RM, .0 .o .0 MB(5) 0.05 0.1 0.156 0.2 0.25 +Mc—15 Figure 4.7: For traces MC-ll, MC—12. MC-13, MC-14 and MC-lS each subfigure, (from top to bottom): [Top] RM’ I 3(1, m) of BER process observed in MC traces for lag m varying from 1 through 40. [Middle] ARMIB(1,m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of 6, the increments in RM I 3(1, m). In the current context we replace. X by the BER process B (0), and replace Y by the BER process of preceding packets 8(1), i.e. a one—right shifted version of 3(0). Then RM I (3(0); 3(1)) measures the amount of information that a packet’s BER ,B[n] shares, on average, with the following packet’s BER [fin — 1]. A natural extension of this measure would be to include more than just the immediately following packet. but include any arbitrary number m such that, 73 9999 thoo .0 OP—x AU! ARM|B(1,m) RMIB(1.m) 9 MB(5) 0.15 8 0.2 0.25 Figure 4.8: For traces MC—16, MC-17, MC—18, MC-19 and MC—20 each subfigure, (from top to bottom): [Top] RMIB(1, m.) of BER process observed in MC traces for lag m varying from 1 through 40. [Middle] ARMIB(1,m) of BER process for the same channel traces. [Bottom] The memory length M B plotted as a function of 6, the increments in RM I B(1,m). Since we are assuming the BER process to be wide sense stationary, the RMI becomes a function of m, the number of immediately following measurements. We use the abbreviated notation RM I B(1, m) for the RMI in equation 4.9. Recall that RM I B(1,m) is a function of the Shannon mutual information (and hence the joint PDF) of BER processes B through 3(7”). Ideally, once m exceeds the channel’s memory length M B, B become independent of B (m) and the Shannon mutual in- formation equation 4.6 will drop to zero, producing a zero RMI in equation 4.8. But as in the case of correlogram based analysis, the presence of slow fading complicates interpretation of RMI. Therefore, for the duration of the slow fade a packet’s BER will remain weakly correlated with its followers. Hence, after m > M B, this trans- lates into a slowly increasing RM I B(1,m) for successive values of m until it finally becomes 1. However, for the problem at hand we are not particularly interested in slow fades but the memory length of fast fades. Therefore, we define channel memory 74 AA AA A A A A‘A‘AiiA'iA A A A AA"A’A‘LAA A ~——————— __—'j—__——__ io-o-J-o-o-if-c-o-O'O" l L J Figure 4.9: For traces MC-21, MC-22, MC-23, MC-24, MC-25 and MC-26 each sub- figure, (from top to bottom): [Top] RMIB(1,m) of BER process observed in MC traces for lag m varying from 1 through 40. [Middle] ARM I B(1, m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of 6, the increments in RAMBO, m). length MB as the time it takes for the RMIB(1, m) function to rise to a level after which it grows only slowly. Then channel memory M B is determined by computing the RMI function for increasing values of m and setting A! B equal to the largest lag m for which the amount of additional RMI provided by including the (m + 1) delayed BER becomes smaller than 6, i.e. 618(6) 2 nmx (|RAIIB(1,m — 1) —— RJUIB(1,m)| 2 6) \7’m 6 [1,00]. (4.10) Thus the memory length 1113(6) is a function of 6, the significant RMI increment threshold. That leaves us with the choice an appropriate value of 6. RMI is under- stood to be the fraction of Shannon information of one random variable contained 75 collectively in another set of random variables. Thus, in terms of RMI the memory length of the BER process can then be understood as the lag m after which every subsequent BER measurement will contribute less than 100 X ‘70 of new information about B (O) The feature that makes RMI attractive for use as a tool for memory measurement is not the fact that provides an unequivocal measurement of the BER process’ memory length. Like the correlation coefficient before it, the RMI depends on the subjective selection of a threshold that determines the cutoff between signif- icance and insignificance. Rather, its strength lies in the fact that there is a clear interpretation of the threshold (in this case 6) in information theoretic terms, e.g. 6 = 0.15 implies that on average, an MB delayed measurement contains at least 15% information about the current measurement. Another advantage of using RMI over the commonly used correlation coefficient is that the changing trends operating on the timescales of slow fades that cause non-stationary behavior of the BER process do not complicate the analysis. 4.4.3 Discussion The plot at the top in figure 4.7 is the R11'IIB(1,m) of traces of IEEE 802.15.4 links operating channels 11, 12, 13, 14 and 15 for a range of lag values m. The middle figure plots the ARM I (1, m) functions of the same traces for the same range of lags. The bottom plot in figure 4.7 shows the memory length as a function of increments 6. Figures 4.8 and 4.9 plot the same quantities for the remaining channels in the MC trace set. Similarly, figures 4.10 and 4.11 plot RMIB(1,m), ARMIB(1,m) and M 3(6) for the traces in the ME trace set. For our reading of the plots let us take 6 = 0.15 ,i.e. last measurement within memory length contributes at least 15% information. Then the plots of M 8(6) for all traces adequately demonstrate that all 802.15.4 traces exhibit a memory length within a narrow range of O to 10 76 ARMB(1,m) RMB(1,m) AA AAAA AAA A. 5 10 15 204m 25 ' 30 35' ;.ME_1 A : —~—ME—2 :11, la, . ' I—-—ME-3 : . , +ME-4 0 +ME-5 0.05 0.1 0.15 5 0.2 0.25 _+_ MEJB Figure 4.10: For traces ME-l, ME—2, .\lE~3, ME—4, ME—5 and ME—6 each subfigure, (from top to bottom): [Top] RM I 3(1, m) of BER process observed in MC traces for lag m varying from 1 through 40. [Middle] ARM I B(1, m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of 6, the increments in RMIB(1, m). packets which, at the packet transmission rate of 10 packets per seconds used for trace collection, corresponds to a time period of 0 to lsec. Thus, diversity in physical environments and channel selection do not appear to have any significant bearing on the duration of fast fades, as measured by RMI. On a side note, there is a major practical challenge to the online and/ or real- time computation of RMI. The computation of RM I B(1,m) is based on an m + 1 dimensional joint PDF of all processes 3(0),B(1),B(2),...,B(m). Populating such a high dimensional PDF requires large data set even for moderate values of m. Collecting data points to fill a modest 10 dimensional PDF takes significant time, especially when considering that IEEE 802.15.4 is a low rate communication standard. This makes this methodology especially unsuitable for applications in which this computation is to be performed online. We repeatedly performed this computation 77 ARMB(1,m) RMB(1,m) MBe) ME-1 1 ME- Figure 4.11: For traces ME—7, ME—8, MEI—9, ME-lO, ME—ll and ME—12 each subfigure, (from top to bottom): [Top] RM I B(1, m) of BER process observed in MC traces for lag m varying from 1 through 40. [Middle] ARMIBU, m) of BER process for the same channel traces. [Bottom] The memory length MB plotted as a function of 6, the increments in RM I B(1, m). offline on different data sets, and found that even on a mid-level server class machine the computation of the RMI function based on 50,000 data points for m ranging from 1 to 40 takes more than 30 minutes. 4.5 Conclusions 1. All IEEE 802.15.4 channels, regardless of channel selection or physical environ- ment, exhibit a memory length of at most 2 bits and 2 symbols, respectively. [\3 . Based on the correlation function and LRD based analysis we conclude that various estimates of Hurst parameter may or may not detect packet level mem- ory in 802.15.4 channels. The ’memory’, however, is not due to the channel’s inherent properties at those frequencies, but due to interference from 802.11b/ g 78 traffic and beacon frames, i.e. if interference is periodic the channel appears to have memory, if it is not periodic there is no memory. . The Abry-Veitch and Whittle estimators’ consistent relative insensitivity to changes in average PER, average PLR, average CBER and interference across different traces leads us to conclude that they are better measures of the 802.15.4 channel’s inherent degree of LRD. . The aggregate variance, R/ S, periodogram, and absolute moment estimators’ strong dependence on average PER and average PLR leads us to conclude that these estimators are good detectors of (W’LAN) interference. . The average CBER to which a packet is subjected by a channel is inversely related to the average PER/ average PLR. Thus, it appears that interference produces higher BERs in packets than do channel fading effects. . We present use of RMI as a standardized version of the mutual information and apply it to the BER process captured in bit traces. We observe that interference free 802.15.4 channels are memoryless, while channels experiencing significant interference from 802.11b / g networks sharing the 2.4GHz ISM band, a common source of interference, have ”true” memory lengths varying in the narrow range of 0 to lsec. 79 Chapter 5 A Statistical Measure Of Network Lifetime For Wireless Sensor Networks 80 5. 1 Introduction One of the most fundamental challenges in wireless sensor networks (W SN ) is the short and often limited supply of energy. Due to the disposable nature of WSN nodes power sources are often non-replenishable or replenishable very slowly at best. In either case this forces prudent use of battery power for all operations. Since WSNs can be spread over large geographical areas multi—hop communication is employed in transmitting sensor measurements to the data collection point, also known as the base station. The problem is further compounded by the many-to-one traffic flow pattern that is imposed by the data collection process. It produces a traffic hot-spot or bottleneck around the base station and, depending on the positioning of nodes, in other regions of the network as well. This phenomenon is called the reachback and was investigated by Barros and Servetto in [9]. If the same sl'iortest-path-first (SPF) routes [30] are maintained, as in the case of most present day mobile ad-hoc networks (MANET) and W SN routing algorithms, nodes start running out of energy. Nodes gradually start disappearing from the sensor network beginning with those handling the highest traffic volume, the ones communicating directly with the base station. Such nodes are referred to as critical nodes. Each node going offline will reduce coverage provided by the WSN. Eventually all nodes in communication range of the base station will run out of power and the base station will stand disconnected from all surviving nodes, effectively dropping situational awareness at the base station to zero. While the nature of the trafiic flow makes the degradation of system capabilities over time inevitable, it is desirable to make it as graceful as possible. This leads us to consider a solution that will redistribute the volume of traffic handled by critical nodes more evenly. It is noted here that any deviation from routes selected using a routing algorithm based on SPF means selecting a route that is suboptimal in the traditional, greedy sense (of which there are many even for small sets of critical nodes). 81 The above discussion provides us with two objectives; 1) reducing the differences between energy consumption rates of nodes, 2) but at the same time keeping the average energy consumption rate low. This requires the joint minimization of both objectives. Since these two objectives run counter to each other the selection of an operating point is a trade-off between mean and variance of power consumption rates. The remaining chapter is organized as follows. Section 5.2 reviews some recent efforts that attempt to increase longevity of WSNS and positions our work. Section 5.3 describes our interpretation of network lifetime and how the advantages of its use as an objective over previous definitions. Section 5.4 describes our network model and introduces terminology. Section 5.5 formulates the problem as a quadratic program. Section 5.6 describes some results for small scale examples and section 5.7 concludes the chapter. 5.2 Previous Work The volume of works spanning energy efficient routing protocols for WSN is extensive. Early WSNs borrowed routing protocols from ad-hoc wireless networks and MAN ETs. The routes selected by dynamic destination-sequenced distance-vector (DSDV) [99], dynamic source routing (DSR) [61], ad—hoc on-demand distance vector (AODV) [100] and directed diffusion [58] protocols are ” optimal” only in a greedy, SPF sense which worked well enough for networks without power constraints. The performance of a system using these protocols is as much subject to the reachback problem as one making use of naive SPF routing. In [25] Chang and Tassiulas formulate the lifetime problem as a minimax linear program (LP) that seeks to maximize the minimum sensor lifetime. However, while the approach is theoretically sound and provides a bound for any attempt at maxi- mizing that particular notion of network lifetime, there are scalability problems which 82 are exacerbated by the very large number of optimization variables for which the LP is solved. This was followed by several other LP formulations of the lifetime problem [11],[107],[135], [78], all based on the same or similar meaning of network lifetime, of varying degrees of usability. In [6] Back and de Veciana proposed a proactive multi- path routing scheme by introducing joint minimization of the ”spreading factor” w, and the probability of battery depletion of a sensor which is similar to Ilyas and Radha’s parallel work in [53] that uses average and variance of power consumption rates in sensors. However, Back and de Veciana’s mechanism used for path discovery does not take into account several other available conununication links. While the authors demonstrate the improvements offered by their energy balancing algorithm in networks with any-to-any data flow the proposed solution does not seem to offer an improven'ient when the traffic flow is many-to-one/ all-to—one. More recently Khanna, Liu and Chen [65] took an evolutionary approach. However, this was marked by a high complexity due to the inherent nature of Genetic algorithms and poses challenges to scalability. 5.3 Novelty Of Approach The bulk of previous work on the lifetime problem defines network lifetime as the time until the first sensor runs out of power. The. rigidity of this definition is of advantage because it provides a clear objective function for optimization. However, any set of routes that deviate from greedy SPF routes produce an increase in the power consumption rates of some nodes, decreasing their individual lifetimes. The prior LP approaches that maximize the minimum sensor lifetime are no exception. However, by solely focusing on one sensor’s lifetime (the minimum lifetime sensor), it ignores the cost, the decrease in other sensors’ lifetimes at which this maximization is achieved. This also implies a higher rate of failure of sensors as a network approaches the end of 83 its life, as defined under LP minimax problem formulations. This definition disregards the inherent redundancy in WSNs and their ability to cope with a limited device failure rate. In this chapter we use a notion of lifetime that takes these ”shortcomings” into account. We propose the joint use of two statistics of P, the random variable modeling the energy consumption rates of sensors in a W SN, namely; 1. E[P] : the mean of P. 2. Var[P] : the variance of P. The problem then becomes a joint-minimization problem. This notion of lifetime takes into account the lifetimes of the entire population of sensors making up the network. Some previous solutions such as Singh, Woo and Raghavendra [113] describe the independent minimization of only the variance of node power levels to extend the lifetime of a network. l\«'Iinimization of E [P] alone is achieved by SPF routing protocols based on energy as a cost metric. However, selecting routes based solely on the minimization of E [P] will inevitably lead to the aforementioned reachback problem where sensor nodes closer to the base station transmit packets at significantly higher frequency compared to sensor nodes farther away. This problem can be formulated as a budget constrained allocation problem: The minimization of Var[P] defined as equation 5.1 is subject to the constraint equation 5.2 that E [P] be less than some maximum budget value E[P]*, where P,- is the energy consumption rate of node n,,‘v’ g i g N, and N is the number of nodes. ZN (Pi. - E[P])2 min Var[P] = 2:1 . (5-1) 1’\/ Subject to, N P E[P] .. ZZZ-,1 7* g E[P]* (5 2) Using the constraint formulation highlighted above, we can summarize our opti- mization framework as identifying the set of routes throughout a given WSN such that the following is satisfied: minE[P]+z 30,000 ”saw-":1" 20,000 . 1090930 100 150* 200 250 E[P] Figure 5.2: Tradeoff of Var'[P] versus E[P] for a network with N = 10. certain point Var[P] starts increasing again. 5.7 Conclusions We propose a new definition of network lifetime consisting of E [P] and Va'r[P]. This notion of network lifetime provides a more inclusive view of the power consumption of sensors across the network. The objective function offers an alternative view of network lifetime. We went. on to formulate the optimization problem for the new objective function in the form of a QP and showed that a solution exists. 92 MeanvsVarianoeofP E in > " -- ' ' 60,000 " -. I'- . - ' I m,m P— . ... -' . l. :. l . o 200 400 600 Figure 5.3: Tradeoff of Var[P] versus E[P] for a network with N = 15. 93 800 VARIP] E t MeanvsVarianoeofP do so 160* 1.5.0 1210 150 E[P] Figure 5.4: Tradeoff of Va7‘[P] versus E [P] for a network with N = 20. 94 Chapter 6 A Dynamic Programming Approach to Maximizing Lifetime of Sensor Networks 95 6.1 Introduction Wireless sensor networks (WSN) are the enabling technology for applications rang- ing from infrastructure protection and Operation, emergency and crisis intervention, all the way to surveillance and environmental monitoring systems. One of the most fundamental. constraints of WSN is the short and often limited supply of energy. Difficulties accessing sensors post—deph)yment, hostile deployment environments, and impracticality of performing maintenance operations on individual sensors requires making sensors disposable. Power sources are often non-replenishable or replenish- able very slowly at best. In either case this forces prudent use of battery power for all operations. Since W SNs can be spread over large geographical areas, multi-hop communication is employed in transmitting sensor measurements from sensor nodes to the data collection point or base station. The problem is further compounded by the many-to—one traffic flow behavior witnessed in information gathering for in-situ and remote sensing applications. It produces a traffic hot-spot around the base sta- tion and other regions of the network with traffic bottlenecks. Barros and Servetto [9] called this phenomenon the reachback effect. Wan et al. [125] named it the funneling effect. If the same shortest-path-first (SPF) routes [30] are maintained, as in the case of most present day mobile ad-hoc networks (MAN ET) and WSN routing algorithms, some nodes will run out of energy sooner than others. Nodes will gradually start dis- appearing from the sensor network beginning with those handling the highest traffic volume, i.e. the ones connnunicating directly with the base station. These nodes are referred to as critical nodes. Eventually all nodes in communication range of the base station will run out of power and the base station will stand disconnected from all surviving nodes, effectively dropping available coverage to zero. It is desirable to stave off this event for as long as possible. This leads us to consider a solution that will redistribute the volume of traffic handled by critical nodes more evenly. It is 96 noted here that any deviation from routes selected using a routing algorithm based on SPF means selecting a suboptimal route (of which there are many, even for small sets of critical nodes). We discuss and compare several methods for obtaining or- dered listings of suboptimal paths. A dynamic programming algorithm (DPA) then selects an optimal set of routes. The link cost metrics are derived from physical layer information, thus qualifying this route selection method as a cross-layer approach. The above discussion provides us with the objective of reducing the differences between energy consumption rates of nodes while keeping the average energy con- sumption rate low. This requires the joint minimization of both objectives. Since these two objectives have conflicting requirements the selection of an operating point becomes a trade-off between mean and variance of power consumption rates. We evaluate a number of route discovery algorithms that produce paths other than the shortest paths between source and destination. This is followed by picking one path for each source-destination pair in a way that energy consumption is spread out, yet, kept low. The core contributions of this work are summarized below. 1. We propose mean and variance of the distribution of node power consumption rates as alternative optimization objectives for network lifetime. 2. We provide a low-complexity, dynamic programming formulation of the opti- mization problem rooted in operational rate-distortion theory. 3. We evaluate various algorithms for the discovery of paths deemed sub-optimal in the SPF-sense as inputs to the dynamic programming algorithm. The rest of the chapter is organized as follows. Section 6.2 reviews some recent efforts that attempt to increase longevity of W SNs and positions our work. Section 6.3 describes our network model. Section 6.4 is the formal problem formulation. Section 6.5 describes four route discovery algorithms. Section 6.6 explains in detail 97 the working of the DPA inspired by operational rate—distortion (RD) theory. Section 6.7 presents an in-depth analysis of the performance of DPA and the route discovery algorithms used in conjunction with it. Finally, section 6.8 concludes this chapter. 6.2 Previous Work The volume of works spanning energy efficient. routing protocols for WSN is extensive. Early VVSNs borrowed routing protocols from ad-hoc wireless networks and MAN ETs. The routes selected by dynamic destination-sequenced distance-vector (DSDV) [99], dynamic source routing (DSR) [61], ad—hoc on-demand distance vector (AODV) [100] and directed diffusion [58] protocols are ”optimal” only in a greedy, SPF sense which worked well enough for networks without power constraints. These protocols are prone to the reachback reflect. In [25] Chang and Tassiulas proposed an optimization approach based on linear programming. However, their formulation maximizes the minimum node lifetime because it defines the system lifetime as the time until the first node runs out of power. More recently, Baek and de Veciana proposed in [6] a proactive multi-path routing scheme which bears some similarity to our own inter- pretation of the problem by introducing joint minimization of a ”spreading factor” to, and the probability of battery depletion of a sensor which is very similar to Ilyas and Radha’s parallel work in [53] that uses average and variance of power consumption rates in sensors. However, Baek and de Veciana’s mechanism used for path discovery does not take into account several other available communication links. While the authors demonstrate the improvements offered by their energy balancing algorithm in networks with any-to-any data flow the proposed solution does not seem to offer an improvement when the traffic flow is many-to-one. More recently Khanna, Liu and Chen [65] took an evolutionary approach. However, this was marked by a high complexity due to the very nature of Genetic algorithms and poses challenges to seal- 98 ability. As we will show in the following sections the DPA proposed here resolves traffic hotspots in a WSN irrespective of the nature of traffic flow. 6.3 Network Model 6.3.1 Device Model To model devices we are adhering to the IEEE 802.15.4 low-rate wireless personal area network (LR-WPAN) draft. standard [5]. The standard defines two device classes, reduced-function devices (RFDs) and full—function devices (F F Ds). RF Ds feature only a limited implementation of the features defined by the standard. They are capable of associating and communicating with F FDs only and are incapable of performing routing functions. FFDs on the other hand have a full implementation of the standard and are capable of associating and communicating with both F FDs and RFDs. FFDs are also capable of performing routing functions. Since the DPA is a routing algorithm and only FF D3 are capable of performing routing functions all nodes in our network model are assumed to be FFDs. A WSN consists of N _FFD sensors capable of performing routing functions, ad- ditional RFD sensors and one base station. FFD routers are numbered 1 through N. The base station is assigned FFD ID 0. Furthermore we are assuming the nodes participating in the W SN to be capable of measuring received signal strength indi- cation (RSSI) and link quality indication (LQI) for received packets and adjusting their transmission power as laid down in the standard. Moreover, nodes are capable of varying transmission power at run-time on a packet-by-packet basis. Transmis- sion power is chosen as a function of the spatial separation between transmitter and receiver and the signal decay factor described next. 99 6.3.2 Link Model We are employing and adhering to the channel model proposed by the 802.15.4 Phys- ical Channel Modeling Subgroup in [86]. Early exploratory work by Ilyas and Radha [53] assumed the simple disk model for a node’s communication range. A consequence of this model was that it made all links bidirectional which is not necessarily true in real wireless networks. We are modeling the communication range of a sensor in each direction by a Gaussian ramqhnn variable 3 with mean #3 and variance 0%. Each j is assigned a link cost Lisj' The link cost is a function of the energy cost of receiving, processing and (re-)transmitting a packet link from a node n,- to another node n (reliably) and the remaining battery level at the transmitter. Although the total energy consumed is the sum total expended in receiving, processing and transmitting a packet, this total is dominated by the energy of the transmission step. The cost. of receiving a packet depends on the platform used for a sensor and is approximately constant for equally sized packets and the processing energy is negligible in compari- son. The link cost Li, j in equation 6.1 is the cost to node "i of transmitting a packet to node nj, that is dw- distance away. For an omni-directional antenna the decay factor a is usually around 3 [86]. Li,j also takes into account the remaining battery level in a node. The sum of reception, processing and transmission cost is divided by the fraction of remaining battery level 8,. (10 . «lay-Z where did- 5 Ci Liaj = l 00 where di‘j > c, (61) 100 Table 6.1: Symbols and notation. Symbol Description "0 Base station nlj FFD sensor node with identifier 1 EM- Maximum communication range of n,- in the direction of G (V, A) Graph consisting of vertex set V connected by directed edge set A. Ai,j Directed edge from n,- to nj. T,- Rate of traffic generated at ”2" Pi, j k-th best path from 71.2 to n]. E,- Energy consumption rate of 71.,- under the global traffic flow under consideration. ,u E Sample mean of energy consumption rates E, for 1 S 2' S N. 0%: Sample variance of energy consumption rates E-z' for 1 _<_ 2 S N. S P(i —-> j, G) Shortest path from n,- to n]- on graph G. Lm- Link cost on ”i for link from ”2' to nj. 3.,- Fraction of total battery power remaining in "i- Then the power consumption rate of a node n,- V 1 S i S N is denoted Ez- and is defined in terms if link cost terms like in equation 6.2, N N E: Z Z L,“- for all 1 g is N n=1 . 321k mm Naefih 101 6.4 Problem Formulation WSNs serve to provide situational awareness and collect data from the entire region covered by them. An area is said to be covered as long as there is at least one sensor taking measurements from it. Data reporting of an area can stop due to two reasons, 1) The sensor providing coverage runs out of power, and 2) the sensor is unable to route its data to the base station due to a partition / fragmentation of the network. When a node stops cormnunicating data to the base station there is a drop in coverage. Therefore, the utility of a W SN is related to the time period for which a W SN can maintain minimum coverage. The skewed distribution of energy consumption rates in sensors requires a redistribution of traffic load that, 1. Produces a more evened out traffic load across sensors. 2. Yet, at the same time, guarantees low total energy consumption. In mathematical terms, if E is a random variable modeling the energy consumption rates of sensors in a WSN, we aim to minimize its sample variance 0% (defined in equation 6.3) while keeping its sample mean “E low (defined in equation 6.4). 2 __ ZillEi ‘ HE)2 0' E N (6.3) v M = ——Z"l=1 Ei. E N (6.4) This leads to a joint-minimization problem. l\~‘Iinimization of n. E alone is achieved by SPF routing protocols based on energy as a cost metric. However, selecting routes based solely on the minimization of n E will inevitably lead to a situation where sensor nodes closer to the base station transmit packets at significantly higher frequency 102 compared to sensor nodes farther away. In a multi-hop WSN this implies significant variations in individual nodes’ energy consumption rates. Due to the optimality principle of subproblems, the SPF routes from sensors to the base station form a tree rooted at the destination. Over time the region of failing nodes will expand from the base station away. Once this region spreads to the maximum transmission range of a sensor node in all directions around the base station it is cut off from the rest of the network. The network will experience a partition [119] despite the fact that there will be a large number of nodes with significant battery life left. This problem can be formulated as a budget constrained allocation problem: The minimization of (7%: in equation 6.5 is the objective function. Minimization of the objective is subject to the inequality constraint that p E be less than some (user defined) maximum budget value a E budget in equation 6.6. - 2 mina E (6.5) subject to constraints, N N L7,], :1 Z N S ”E budget' 71: . = 1 J _ (6.6) . . 1 A27] 6 PTL,0 In [113] Singh, Woo and Raghavendra describe the independent minimization of only the variance of node power levels to extend the lifetime of a network. We propose joint minimization of [,L E and 0%. Using the constraint formulation highlighted above, we can summarize our optimization framework as identifying the set of routes, one for each source destination pair in a given W'SN such that 0% is minimized while 103 n E _<_ p E budget' This is analogous to minimizing a distortion measure given a rate budget constraint under an RD framework. Consequently, our proposed dynamic programming algorithm (DPA) is based on an operational RD—framework where we strive to select the mean-variantte (MV) operating point that offers the lowest achiev— able 0%) while maintaining it E S p E budget The solution takes the form of a set of routes, one from each node to destination (base station). In terms of the optimiza- tion problem formulated in equations 6.5 and 6.6, the solution is the set of values k1, k2, k3, . . . , kN that select a corresponding set of paths 1311?), 192/6%, Pfifl’ . . . ,P:% that minimize the variance of the power consumption under the simultaneous flow of traffic from all nodes. We have not, to this point, discussed the generation of sets of alternative routes Pig) from every node 1 S 2' _<_ N to the base station. In the following section we describe four different algorithms to obtain alternative paths between sources and destination. 6.5 Route Discovery Sub-sections 6.5.1 through 6.5.4 describe the four different route discovery algorithms used for finding alternative paths from nodes to the base station. The four types of routes are bottleneck edge disjoint (BED), bottleneck node disjoint (BND), edge disjoint (ED) and node disjoint (ND). To explain and illustrate the differences between the route discovery algorithms figure 6.1a through 6.1d show the different routes determined from sensor node 7199 in a W SN consisting of a base station and N = 99 randomly placed FF D sensor nodes in a square shaped region of size 10 x 10 with each nodes transmission range chosen from the Gaussian distribution N 01.30%) (with mean #3 and variance 0.2:). For the following discussion we represent the H W SN by graph a C(V, A). Nodes are represented by the set of vertices V and the 104 Bottleneck Edge Disjoint Routes Bottleneck Node Disjoint Routes 1 O (a) BED paths. (b) BND paths. Edge Disjoint Routes Node Disjoint Routes l , r: ’;_.’,4'// .\_ ‘Ffi'f‘W/M’. (‘1‘?"7‘ "lint/affix“;--[lflgllfll" \ 5 (WV/1V ‘ ‘9’; ‘(/’ Z ual/m ( //’l‘ ' fl:“"'//"""' 737” V<."'.r,’A‘-A 1727 "W’ 0 5 10 (C) ED paths. (d) ND paths. Figure 6.1: Paths from 7199 to no. communication links between elements of V is denoted by the set of edges A. A directed edge from vertex n," to nj is denoted by Ai,j- Furthermore, let F denote the minimum spanning tree rooted at the base station on the connected component of G. We also define the maximum power node function MaxPowNodefl") which returns the node that experiences the highest power consumption when traffic flows to the base Station along I‘. The predecessor function Pred(I‘, z") returns the parent node of n,- in P. The indegree(nz~, F) function returns the in-degree of node n,- in graph I‘. The Shortest path from vertex "2’ to vertex nj on a graph G is denoted by SP(i —) j, G). 105 6.5.1 Bottleneck Edge Disjoint Paths We define the bottleneck edge to be the outgoing edge from node MaxPowNode(F). This method repeatedly determines and removes the bottleneck edge, and rediscovers the minimum spanning tree F and from it the shortest paths from each node to the base station. Figure 6.1a depicts all BED paths from ”N to no. Algorithm 1 Generate Bottleneck Edge Disjoint Paths Require: n 2 0 V :2: 3f 0 Ensure: 5(2) 2 {},V1 3 2' S N G := Topology of WSN with all available links F := C while indegree(n0, F) > 0 do F := Minimum spanning tree on G rooted at no for all "2' do if SP(i —) O, F) 74 S(end) then S(i) :2 {5(1), SP(2'. —> O,F)} end if end for G I: C(V’ A — A(=.\-'IaxPowNode(F),Pred(MaxPowNode(F),F)) end while 6.5.2 Bottleneck Node Disjoint Paths A bottleneck node is defined as the node returned by the hvt’laxPowNode(F) function. This method repeatedly determines the bottleneck node under traffic flow along F, removes all its incoming edges from the graph, and rediscovers the minimum spanning tree F and from it the shortest paths from each node to the base station. Figure 6.1b depicts all BND paths from 7199 to "0° 6.5.3 Edge Disjoint Paths Edge disjoint paths between two vertices ”i and 'nj in a graph are paths that do not have any edges in common between them. To determine an ordered set of edge disjoint 106 Algorithm 2 Generate Bottleneck Node Disjoint Paths Require: n 2 0 V 3: ;£ 0 Ensure: 5(2)={},V1§2'S N G := graph of WSN with all available links while indegree(n0, F) > 0 do F := Minimum spanning tree on G rooted at no for all 222- do if SP(2 -—) 0, F) # 5(67221] then 5(2) 2: {5(2) SP(2' —> 0,F)} end if end for G := G(V — MaxPowNode(F), A) end while paths from a node ml: to the base station this algorithm repeatedly finds and saves SP(2' a 0, G) and removes all edges it is composed of from G. The Edge() function returns the edge set of the path provided in the argument. Figure 6.1c depicts all ED paths from n N to 220. Algorithm 3 Generate Edge Disjoint Paths Require: n 2 0 V a: aé 0 Ensure: 5(2) = {},\7’1 _<_ 2' g N G :2 graph of WSN with all available links while indegree(nO, F) > 0 do F 2: Minimum spanning tree on G rooted at 720 for all ”2' do if SP(2' ——> 0, F) 75 5[end] then 5(2) := {5(2) SP(2 —> 0, F)} end if end for TempM azN ode := MaxPowNode(F) While Temp.M acrN ode 75 220 do G == G(V/1 — ATempMacrNode,Pred(TempMaxNode,F)l TempltfaxNode := Pred(TempMa:1:N0de, F) end while _end while 107 6.5.4 Node Disjoint Paths Node disjoint paths between two vertices 22,- and nj in a graph are paths that do not have any nodes in common between them. To determine an ordered set of node disjoint paths from a node 22,; to the base station this algorithm repeatedly finds and saves SP(2 ——> 0, G) and removes all nodes it is composed of from G. The Vertices function returns the vertex set of intermediate odes between source and destination nodes of the path provided in the argument. Figure 6.1d depicts all ND paths from n N to no. It is worth mentioning here that the ND paths discovered by this algorithm bear resemblance to the routes determined between source and destination nodes in the multipath routing method described in Baek and de Veciana [6] Algorithm 4 Generate Node Disjoint Paths Require: n 2 0 V2: aé 0 Ensure: 5(2')={},\7’1_<_2'S N G := graph of WSN with all available links while indegree(n0, F) > 0 do F 2: Minimum spanning tree on G rooted at 720 for all 22,- do if SP(2 —-> 0, F) # 5[e'n.d] then 5(2) := {[5(2) SP(2 —-> 0,F)} end if end for TempM axN ode := MaxPowNode(F) while TempZW axN ode # 720 do G := G(V — TempMaxNode, A) TempM 0.ch ode := Pred(TempM azN ode, F ) end while end while 6.6 Dynamic Programming The algorithms in the preceding section described four different methods of generating a list of paths in increasing order of path cost from every node to base station. In 108 P101 P201 F’so1 rn" PNO1 P1,o2 Paoz P392 1---- Pun2 [31,03 P2,03 P3,o3 ""- PN,O3 I l l I . . . . [k1 k2 k3 kN] l l | 4‘ k1 Paokz : J ! Pm i j k3 PN 0kN i . Pao ’, I l i J l l l l l [31,0r1 l:’2,or2 Paor3 F’N,orN Figure 6.2: N lists of routes sorted in ascending order of path energies. this section we describe the DPA that selects one path from each list while achieving the optimization objective. Figure 6.2 illustrates this idea and depicts lists of paths obtained by one of the route discovery algorithms. Each column corresponds to a source node 222-, and every box in it represents one of the 7',- paths from source node ”2' to destination "0' The shaded boxes identified by path indices [151, kg, k3, . . . ,kN] represents the solution vector to the optimization problem. The DPA described in this section traverses the space of possible solution vectors and attempts to find one that approximates the optimum solution. but at significantly lower complexity. 6.6.1 Theoretical Background Similar to the operational rate-distortion [32] problem in source coding [94], this joint optimization can be mapped into a Lagrange optimization framework [39]. This for- mulation is feasible if there is an optimum tuple (ME, 02E] such that ,u E S l1 E budget 109 (i.e. an optimal/ minimal overall energy can be found such that it exactly equals the budget constraint). In this case, one can view the problem as one that allocates the total energy budget N x It E budget to all N nodes in the network such that the 2 variance 0 E is minimum. This is referred to as the budget constrained allocation problem [94]. In brief, we can formulate the lifetime maximization problem by considering the Lagrangian cost J (A) = 0%: + ApE, which depends on the Lagrange multiplier A 2 0. Identifying the optimum value for the Lagrange multiplier is a crucial aspect of this approach. In particular, the parameter A represents the slope of the curve in the RD plane. However, the computational complexity of finding the true optimal solution is staggeringly high. The MV plane consists of a E on the horizontal axis and 0%: on the vertical axis. The MV region consists of all MV operating points achievable by different coml.)inations of possible paths, one from each node, to the base station. The desired optimal solution will lie on the hull of the MV region. This is very similar to the problem of finding the optimal quantizer in an operational RD sense from Information Theory [32]. We exploit some of the strategies used under RD optimization to develop a DPA for identifying the optimum solution points in the MV space. 6.6.2 Dynamic Programming Algorithm In order to reduce the computational complexity of finding the hull of the MV region we use a DPA similar to the one used in the determining the hull of the RD region for optimal quantizer design. In the sensor network lifetime maximization problem under consideration it is desirable to minimize 0%, the variance of node power con- sumption rates, and “Ev the mean of node power consumption rates. The reduction in computational complexity over an exhaustive search of all operating points comes 110 (0,4) (0) 2(0) x1 [:Il’lE ao-E :] - (0,4) 0_2(0, 4) [:IuE 90- :] 3103) (0,3) 02(03) 1(01) 0,2 2 0,2 [#E( >90; 1] (0,1) 2(0,1) 02(1) [#5 90E :[Z [#15090- :] V» ”E Figure 6.3: Selection of next optimal point in the MV-plane by DPA. at the cost of DPA being only an operational optimization method approximating the exact optimal solution. The DPA operates 011 N sorted lists, one for each node, each containing [P 11,—0l — r, paths to base station ordered in ascending order of their path costs. The algorithm described here is greedy in nature. It is possible that this algorithm does not find the optimum operational [111;], 0%] point under certain scenarios. Nevertheless, the algorithm does provide the optimum operational solution under many practical scenarios. Furthermore, a set of RD variations of this algorithm are rather popular due to their simplicity and low-complexity ([103],[109],[118]). (0) 2 (0) The starting point [12E ,JE ] of the DPA is the operating point that offers the lowest possible ,12 E and is obtained by selecting all P310 where Vj,1 S j g N and . . . . . 0 . 18 located closest to the 0% ax1s. The nnnnnum mean power consumption 11%) is 111 associated with a relatively high variance 0%(0). The DPA uses [11(3) , 033(0)] as a (1) (1)] starting point to search for the next achievable operating point [11E ,0’%—: closest to the hull of the MV region that adheres to the budget constraint Ebudget' The 0) 2 (0) shortest routes that correspond to [11%. ,0 E ] are the ones at the top of all columns in figure 6.2. If pair [12%). 0%.(0)] satisfies the specified constraint 112.0) S ,uE budget and [11(El),0%(1)] does not, [ughagjlm] is the optimum point and the algorithm terminates. However, in general, the above condition is not met except in special cases (such as where all nodes are at an equal distance and one hop away from the base station), and the algorithm proceeds to the next step. Rather than considering all possible route combinations, at any operating point Lug), 0%.(i)] during the (2+ 1)th iteration, the algorithm introduces the smallest increase AE in energy to each route - - . ,- -, (’1?) 2 (2) 2+1 by con81der1ng replacement of le,0 111 the set of routes used for [11E ,0 E ] by 133,0 in turn. In a network of N nodes this produces up to N new possible operating points ' 2' 1 . . . for [#%+1)10%~( + ) ]. The exact number of alternative operating pomts depends on the number of route lists that still have an alternate path left for consideration. Each of these possible alternatives is obtained by replacing one of the routes that produced [11%),0%(7)] by the next path and computing a new operating point. This way up to N different alternatives lflg+1’j),a%(l+1’])] for 1 Sj S N are obtained. For each of these N possible operating points we compute their slopes MM) with respect to previous operating point Lag), diam] like in equation 6.7. .. U2('i+1,j)_02(i) 190): E, . E A?” — 11%) (6.7) . , _ . 2 1,' Equation 6.8 shows that out of these N alternative operating pomts “(EFF J), 112 2+1, ' . . .' ' - (7%; '3) we select the one which offers the lowest gradient /\(l’]m'ln). jmz’n = arg min(/\(i’j)) (6.8) Equation 6.9 assigns the point obtained by changing node njn . 1’s path to be the : 222 next achievable operating point of the MV plane and advances the the route pointer in column jmz’n of the route list in figure 6.2 down by one position. (2317- ) 2 (2327 v ) : [H mm ,0. 771.277. ] E E (6.9) This way the algorithm iteratively determines the next point on the MV region’s hull. (0) 2 (0) Figure 6.3 illustrates a simple example. [11E ,0 E ] is the starting point and there are four possible points in the MV plane one of which has to be chosen as the next operating point on the MV curve. In this example M021) < M02) < M023) < /\(024). Therefore, the point [11(19’1),0%3(0’1)] corresponding to the smallest slope M021) (1) 2(1) be chosen for [11E , a E ]. 111 this manner a curve is obtained in the MV plane which will estimates the boundary of the MV region. Figure 6.4 depicts MV curves for a WSN using different route discovery algorithms at our disposal. The differently sloped lines (A’, A” and Am) represent different benefit/cost (variance reduction/mean increase) ratios, that can be used to identify a suitable operating point on the hull of an MV curve. The curves shown in this figure are truncated at the right end when the mean value becomes greater than the mean at the initial starting point. If the DPA is allowed to run to completion the number of points returned by it is approximately 50 to 100 times the ones plotted here. However, the region of the curve that is of interest to us is the one between the starting point and the point offering I'ninimum 113 180 160 ' ‘ " 150 \ 140- \ N L” Net t>130» . ' 120— , —BED 11o— , - BND . M ED 100 ._ END 908 9 ' '10 1'1 1'2 113 14 “E Figure 6.4: Mean-Variance tradeoffs offered by BED, BN D, ED and ND paths. variance. 6.6.3 Computational Complexity of Finding Optimal Solu- tion There are two sources of complexity in this problem; 1) The computation of achievable operating points, 2) the traversal of the search space for the best achievable operating point. The graph G(V, A) that represents the WSN consists of a vertex set V of cardinality N + 1 and a directed edge set A of maximum cardinality N 2 + N (we consider a worst case scenario in which the network topology forms a fully connected graph). First, we derive an upper bound for the order of complexity of the size of the 114 search space for a brute force method. The total number of paths from a node ”2' to base station n0 with q intermediate hops is (N—1)Pq' Then the total number of possible paths from n, to no is the number of paths with 0, 1, 2, . . . , N —1 intermediate nodes, i.e. 26V_1 (N—1)Pq = 281—1 Ali-ail! ! = O(N!). Then the search space of solution vectors for routes from all N nodes to destination consists of 0(N 1N) points. A linear search of this space leaves the complexity unaffected, i.e. 0(NlN). Now we compute the complexity of the DP formulation proposed in this chapter. The size of the search space for in DPA is I121]:- qu. The expression of T2 in terms of N depends on the route discovery algorithm used. For BED the upper bound on the number of paths 'ij generated for a node ”2' is (N + 1)N = 0(N2) bringing the total size of the search space to N - (N + 1)N = 0(N3). The bound for BED can be used as an upper bound on the number of paths per node generated by ED. For BND the upper bound on the number of paths 2‘, generated for a node n,- is N = 0(N) bringing the total size of the search space to N - N = 0(N2). The bound for BN D can be used as an upper bound on the number of paths per node generated by ND. Since the removal of each entry from the search space requires the computation of N slopes, the complexity of the DPA for BED and ED is upper bound by 0(N - N3) = 0(N4) and for BND and ND it is upper bound by N ' N2 = 0(N3). Regardless of whether BED / ED or BND / ND are used for route discovery, their respective complexity terms 0(N4) and 0(N3), respectively, are still orders of magnitude lower than O(N!N), the order of the exhaustive brute force search method. 6.7 Performance Analysis For the comparative evaluation of BED+DPA, BND+DPA, ED+DPA and ND+DPA algorithms we generate 100 randomly generated networks deployed in a square shaped 115 region of size 10 x 10. In all networks the base station is located at coordinates (0,0) to obtain large variations in path lengths. N = 99 nodes are randomly and uniformly scattered in the plane. Transmission ranges E of sensors are Gaussian distributed according to N (10, 2). The WSN is monitoring a process with an entropy uniform across the space spanned by the network. This implies that the traffic generation rates of all sensors are also equal, i.e. T1 = T2 = T3 = = T99 = T. Sensors are equipped with omni-directional antennas with decay factor a = 3. Initial battery reserves Bi for all sensors are assumed to be 1. 6.7 .1 Mean-Variance Trade-off Figure 6.4 illustrates the variations in the estimate of the MV region boundary pro- duced by the DPA when different route discovery algorithms are used for the same network. In this particular example the BND paths seem to offer the greatest decrease in 0%, ND the least and BND and ED fall in between the two extremes. However, similar plots of other networks may reveal that this ordering does not hold true for all cases. We will attempt to determine if there is a route discovery algorithm which provides consistent superior performance over the other algorithms. The four scatter plots in figure (5.5a through figure 6.5d correspond to the four route discovery algorithms. Each plot is obtained by applying the DPA to the list of routes produced by one of the four route discovery algorithm. Each point in a plot corresponds to one of the 100 randomly generated networks. Its position on the horizontal axis indicates the percent increase in ,a E (denoted A11 E) and its position on the vertical axis the percent decrease in 0% (denoted [30%) offered by the minimum variance point (marked by red cross hair) on the MV curve with respect to its starting point (marked by black 2 cross hair). The decrease in variance of power consumption rates A0 E are savings 5 116 that are achievable at a cost C that is the increase in mean power consumption rate A11. E' In the remainder of this section we will use the terms savings and cost to refer to the two quantities. As such, it is desirable that most data points be concentrated in the upper left corner of the scatter plots, indicating high savings 5 achievable at low cost G. Points located close to the origin indicate little change from the starting point. Data points located in the lower right corner indicate bad trade-offs, i.e. low savings in return for high cost. The great overlap in the regions covered by the points indicates that there is no clear winner among the route discovery algorithms. To gain further insight we project data points in scatter plots in figures 6.5a through figure 6.5d on the horizontal/C axis, and the vertical/5 axis. This process is similar to finding the marginal distributions of a joint distribution of two random variables. The four histograms in figure 6.6 are obtained by projection of data points in figure 6.5a through 6.5d on the horizontal/C axis. Similarly, the histograms in fig- ure 6.7 are obtained by projecting onto the vertical / 5 axis. In most cases the shapes of the histograms in figure 6.6 and figure 6.7 all appear to indicate an underlying gaussian distribution. We estimate the values of the mean and variance parameters of gaussian distributions fitting the histogram using. We compute the maximum like- lihood estimates (MLE) [122] of the parameters 12C, 0%, )1 5 and 0%. based on 100 data points for each histogram. The MLEs for BED, BND ED and ND are given in table 6.2 and the resulting Gaussian distributions properly scaled for comparison are plotted together with the histograms. Since we were previously unable to clearly iden- tify one route discovery method as being superior to others in terms of performance we now evaluate their performances in probabilistic terms. A clear winner will have a distribution for C with low mean and low variance and a distribution for 5 with a high mean and low variance. Based on MLE parameters in table 6.2 ND emerges as the least attractive option because it offers the smallest average savings 115 = 24.37% 117 Table 6.2: MLE parameters of marginal histograms generated from applying DPA with BED, BND, ED and ND route discovery algorithms to 100 randomly generated network topologies. 10 cg. 13 02 BED 15.25 328.76 28.09 353.20 BND 20.94 289.93 36.22 303.03 ED 32.25 504.43 35.37 307.67 ND 29.06 390.07 24.37 250.96 at nearly the highest average cost “C = 29.06%. V’Ve eliminate it from further con- sideration. Although with 35.37% ED offers on average one of the largest savings, it does so at a cost that is even higher than ND, i.e. an average savings of 35.37% in return for an average cost increase of 32.25%. In comparison, the BND+DPA option offers an average savings of 36.22% in return for a 20.94% increase in cost, which is significantly lower than from costs of ED and ND. Finally, BED offers average sav- ings of 28.09% at an additional cost of 15.25%. In comparison with BND this means BED offers lower savings for a lower cost. However, the variances of cost. and savings distributions of BED in table 6.2 show that there is considerably greater variation and uncertainty about BEDs costs and savings. relative to BND. The significant dif- ferences in variance terms 0% and (7% can be attributed to the fact that the Gaussian seems to be an ill—fit for BED’s histograms in figures 6.6 and 6.7 and approximates an exponential more closely than a Gaussian. While multi-modal distributions could offer more accurate fits for the data they will complicate performance comparison. We explain the poor performance of paths generated by ED and ND route dis- covery algorithms with respect to BED and BND by the fact that they exclude not just one, but all elements (edges or nodes) of a discovered path from consideration in subsequent path searches. While this cuts down the size of the search space it also removes too many alternative paths from consideration. 118 Furthermore, the high concentration of values in the bins centered close to 0 in ED’s histogram in figure 6.7 indicates a high rate of failure of the DPA, i.e. instances where the DPA is not able to offer a significant trade-off. BED has the highest number of failures followed closely by ED. A closer look at the scatter plots of BED and BND in figures 6.5a and 6.5b respectively shows that BED offers better performance on tight budget constraints on 12 E budget in the low range of savings 5whereas BND performs better when the constraint on 11 E budget is more relaxed and higher higher savings 5 are required. The higher rate failure rate of BED makes its use a more risky option. Also, it should be noted that the scatter plots only plot trade—offs offered by minimum variance point, i.e. when A = 0. As the curve plots in figure 6.4 there is a. large set of points that offer intermediate trade-offs for when lambda is in the range —-00 < A < 0. This is illustrated in figure 6.4 for three different values of A set to A], A” and A”, 6.7 .2 Spatial Redistribution of Energy That leaves open the question of how effectively this method evens out the spatial distribution of energy consumption rates observed under SPF routing. The diffusion plot in figure 6.8 depicts the spatial distribution of energy consumption under SPF routing. This plot is obtained by averaging it over the same set of 100 networks used in the previous section. As expected, as one moves from the upper right corner, towards the lower left corner where the base station is located there is a gradual increase in the power consumption rate in nodes. The lower left corner, the region in immediate vicinity of the base station occupied by critical nodes, forms a traffic hotspot. To illustrate the differences in the spatial distribution of energy consumption rates produced by the BED, BN D, ED and ND route discovery algorithms and DPA we first subtract the diffusion plot of the SPF routes in figure 6.8. The results are the 119 NDUJ 1 NbUJ 1 .9 . . '. _ .9 _ g #1.. a: .... I g I v:- r . °\° - , o\° , 50 100 100 %inorinnE %inorinuE (a) BED paths. (b) BND paths. ED ND NbUJ 1m, NbUJ 1m .E ' I I ,E .5 a) . ‘I" 5' . gm I II ...-I '- II' .-~.I ' . 5,,- II ' \O l I ‘ . °\o fl... . ° (5'7 50 100 (57 100 % incr in 11E °/o Incr in 11E (c) ED paths. (d) ND paths. Figure 6.5: Plots of percent decrease in variance against percent increase in mean. differential spatial diffusion plots in figures 6.9 through 6.12. Like the plot in figure 6.8, these too are averaged over all 100 networks. All route discovery algorithms produce a reduction in power consumption rates in the region occupied by a peak in the SPF’S diffusion map in figure 6.8. This is shown by the blue negative region in the same place, representing a reduction in node power consumption. We also observe an increase in power consumption rates marked by a yellow-red-yellow band that envelOps the blue region on its upper-right side. This signifies a partial shift of relay traffic from critical nodes to their immediate neighbors that are farther away from the base station. A closer look at figure 6.9 and 6.10 shows that the redistribution of traffic is 120 BED 30 20 _ 10 m G a;— I o 20 4o BND 60 80 100 m 30" '5 20— f g 10- 4—0 G —A—— I (D 0 20 40 ED 60 so 100 C 30~ H— O 20- 2 °W Gl .———q . o 20 40 ND 60 80 100 30 20 10‘ 7:]LW 0] I J l o 20 60 80 100 40. ' % Incr In 11E Figure 6.6: Marginal histograms of percent increase ”A1113 for the scatter plots in figures 6.5a through 6.5d. Similar under BED and BND, although BND spreads the energy out over a slightly larger region and that the reduction in power consumption in BND+DPA is around 8000 units, while BED+DPA produces a maximum reduction of only 7000 units. Rom our previous analysis we would expect the changes in the traffic distribution between SPF and ED to be less stark which is confirmed by figure 6.11. Finally, ND seems to be the worst performer because it produces the least change figure 6.12. 121 20 BED i 0 ' 1 200 20 4o BND 60 80 100 (I) x L _— g 10 , r. 04 J (D 0 20 4o 60 so 100 C 20 ED q— 0 F— - 10 O __ Z 0 , 0 20 40 ND 60 80 100 20 10 r" 0‘ . . 0 20 60 80 100 40 _ 2 % decr In O'E Figure 6.7: Marginal histograms of percent decrease ”A02 for the scatter plots in E figures 6.5a through 6.5d. 6.8 Conclusions In this chapter we presented an statistical interpretation of network lifetime that takes into account a limited degree of node redundancy in WSNs. The interpretation of network lifetime in terms of the mean and variance of network-wide node power consumption rates provides us an optimization objective that does not narrowly focus the on the lifetime of a single node as is the case of most prior work. We provide a dynamic program formulation of the problem that seeks to optimize variance of power 122 10000 *isooo --6000 [44000 0 2‘ l 4 6 8 10 X Figure 6.8: Diffusion plot of energy consumption rates averaged over all 100 networks under SPF routing. consumption rates while constraining the average consumption rate. We develop the DPA that chooses routes in a way that optimizes for our objective from sets of paths that would be considered sub—optimal in the shortest path sense. Four variants are developed based on the BED, BND, ED and ND route discovery algorithms. We also observe that the routes discovered by the ND algorithm are very similar to those proposed in previously proposed load balancing techniques such as Baek and de Veciana's in [6]. Interestingly, under our understanding of network lifetime and a many-to—one traffic flow ND is the worst performing of all route discovery algorithms. A statistical performance comparison of these four techniques for the case when A = 0 shows that on average the BND and BED in conjunction with the DPA yield the best 123 0 2 “it 6 8 x Figure 6.9: Differential diffusion plots of energy consumption rates averaged over 100 networks using BED paths and DPA. 0 24's 8 x Figure 6.10: Differential diffusion plots of energy consumption rates averaged over 100 networks using BND paths and DPA. performance. BND and BED yield reductions of up to 28% and 36% in variance of power consumption rates at the cost of raising average node power consumption by 15% and 21%, respectively. The computational complexity of variants of the DPA vary from 0(N3) to 0(N4) which is significantly lower than the full search of 124 6 8 X Figure 6.11: Differential diffusion plots of energy consumption rates averaged over 100 networks using ED paths and DPA. 1o. $315000 710000 0 2' 4 6 ' 8 Figure 6.12: Differential diffusion plots of energy consumption rates averaged over 100 networks using ND paths and DPA. the solution space which is of complexity 0(NIN). Analysis by means of diffusion plots verifies that. DPA indeed reduces power consumption of sensors that experience highest power consumption under shortest path routing algorithms. Diffusion plots also show that the reduction power consumption is highest under BND, followed 125 closely by BED. The resulting route selection method is one that is suitable for applications with many-to—one traffic flows. Route discovery algorithms and DPA assume availability of global network connectivity which is very likely going to be the base station. While this may exclude its use in some applications we envision it having great application in critical infrastructure protection / control/ monitoring, surveillance network and en- vironmental / agricultural monitoring applications with infrequent topology changes. 126 -.. (K 1.]. ] Chapter 7 Mean-Field Solution of Small-World Wireless Sensor Network Models With Range Limited Shortcuts 127 7 .1 Introduction The limited range of wireless channels naturally imposes geometric or Euclidean graph topologies [98] on wireless networks [117]. Wireless sensor networks (WSN) [2] are a class of mobile or stationary, multi-hop ad-hoc wireless networks of power constrained nodes. WSNs are employed by sensing, detection and data gathering applications which impose a 111any-to-one data flow. ()11 the spectrum of randomness of graphs the endpoints are occupied by lattice graphs on one end (no randomness) and random graphs on the other (complete randomness). In between these extremes lie small—world networks [128]. Lattice graphs are characterized by strongly connected neighborhoods that imply a high degree of connectivity and resilience, but rather large diameters. Random graphs [13], on the other hand, are characterized by small diameters (that imply an ability to retrieve and disseminate information quickly) but low connectivity between neighborhood nodes. Note that the same topological properties that enable the fast dissemination of information within a network also enable fast information retrieval. Clearly, in the context of WSNS both strong connectivity at the local level and small diameters are desirable, both properties of small-world networks. In [128] and [127] Watts provided analytical models for 1-dimensional lattice graphs, connected caveman graphs and Moore graphs. Several attempts have been made to leverage the small-world network effect in WSNs ([111],[27],[125],[52]). However, to the authors’ best knowledge there are no analytical models of 2—dimensional Euclidean graphs with range limited shortcuts that are applicable to WSNS. This research derives analytical models for the clustering coefficient and characteristic path length of VVSNs whose topologies are augmented by a small number of shortcut links whose range is limited by practical limitations. Results show that in spite of the fact that shortcuts are range limited and significant differences in construction method the phase difference between drop in clustering coefficient and characteristic path length 128 that is the hallmark of small-world networks still appears. Although shortcuts are range-limited only about 0.005 — 0.05% of nodes had to be equipped with the ability to communicate over long ranges. The remaining chapter is organized as follows. Section 7.2 provides a brief back- ground of small-world networks, their properties and their standing relative to Eu- clidean and random graphs. Section 7.3 describes different system models for W SNs with small-world topologies and provides a literature review of prior methods used to this end. Section 7.4 uses mean field analysis to derive generalized expressions of clustering coefficient and characteristic path length that can be used to model small W SNs based on any of the system models in section 7.3. Section 7.5 evaluates the model for different ranges of parameters. Section 8.8 concludes the chapter. 7.2 Background: Small-World Networks Small world networks were first discovered by Milgram in social networks in [82]. Watts in [128] and [127] analyzed social networks which included a collaboration net- work of actors and a collaboration network of mathematicians, to verify Milgram’s idea of six degrees of separation. More recently Horvitz and Leskovec verified the presence of six degrees of separation in social networks using a much larger data set from Microsoft’s Windows Live lVIessenger instant messaging traffic [130]. Since Milgram’s original experiment several other works have analyzed networks in natu- ral and man-made systems to discover that their topologies are in fact small world graphs. Latora and Marchiori [73] and Watts [127] analyzed the neural network of the C.elegans worm. Montoya and Sole [87] studied food webs in nature. Moore and Newman [88],[89] studied the transmission of infectious diseases in populations with small world connectivity. Studies of transportation networks include Latora, Marchiori [73],[74] on the Boston subway network and Sen et al. [110] on the Indian 129 railway network. Small world analysis of communication networks include Adamic’s [1] on the World Wide Web. i Cancho and Sole [50] studied the lexical networks of human languages and determined them to be small worlds. More relevant to our work are studies on creating small world topologies in wireless networks by various means. Wan et al. [125], Cavalcanti et al. [23] and Costa and Barros [31] showed that selectively equipping a small fraction of nodes in a WSN with two radios (one regular, short range IEEE 802.15.4 and one long range IEEE 802.11b) induces a small world topology. Hubaux et al. [49] and Dimitar et al. [36] propose a small world application layer for ad hoc networks similar to logical links in peer—to—peer networks. Dixit, Yanmaz and Tonguz [37] analyze the topology of cellular wireless networks. Helmy [46],[47] proposes mobility assisted wireless networks to create shortcuts that mimic random links. Sharma, hilazumdar [111] make selected use of wired links to create shortcuts. Among prior models of small world networks are Watts [128] models for the clus- tering coefficient and characteristic path length of 1-dimensional (circular) lattice graph, connected caveman graphs and Moore graphs. In [91] Newman and Watts found a mean-field solution of the small world network model for l-dimensional lat- tices. Arnaral [3] studied the statistical properties of classes of small world networks using a taxonomy based on the form of degree distribution of nodes. Some recent advancements in W SNs have enabled the addition of a number of links with longer communication range, called shortcuts or global scale links, to a network by various means (at a cost). In this chapter we derive analytical expressions for two defin- ing properties of small-world networks, the clustering coefficient C' and characteristic path length L of geometric graphs in a 2-dimensional plane with a number of range limited shortcut links. Let G (V, E) denote a graph consisting of a set of N vertices V = {221, 212,213, . . . ,vN} and a set E of M edges consisting of all edges, where 6M 130 Figure 7.1: Illustrated examples for three different classes of graphs; a) Geometric graph, b) Random graph, and 0) Small world graph. denotes an undirected edge from ”2' to vj. 7 .2.1 Characteristic Path Length Characteristic path length is defined as the average length of geodesic paths between all pairs of nodes. For a graph G, the characteristic path length L(G) is defined as the number of edges in the geodesic path between two vertices, averaged over all pairs of vertices. If Le - is the number of edges on the geodesic path from v- to Us, then, 3:] Z J L =Zly=12jv=1Ltj NUV - 1) (7.1) 7 .2.2 Clustering Coefficient The Clustering Coefficient is a measure of the cliquishness, the degree to which ver- tices in a graph coalesce into tight groups. For a graph G, the clustering coefficient C (G) is defined as follows. Suppose a vertex v has 100 number of neighbors, then the maximum possible size of the set of undirected edges between 2) and all its neighbors is k” ICU-H . Then CU is the fraction of these edges that actually exist in E. The 131 clustering coefficient of the graph is then defined as the average GU over all vertices V, as in equation 7.2. N , C : 27:1 Cl N (7.2) The above definitions of characteristic path length and clustering coefficient are easily extended to directed and weighted graphs. 7 .2.3 Small World, Geometric and Random Graphs We will be using the terms graph and network and the terms node and vertex inter- change-ably. Geometric graphs have (see figure 7.1a), both large L and C by virtue of their strong local connectivity. Random graphs (see figure 7.1b) are the other extreme and are characterized by both small L and C. Small world networks (see figure 7.1c) have small L but large C. There are several construction methods for small world networks. Among the simplest to understand is the 13-model described by Watts in [128]. A small world network can be constructed from a lattice or geometric graph by rewiring one end of every edge to a randomly selected node with probability 5’. The type of graph that is constructed by the fi-model depends on the value of rewiring probability 5. If 6 = 0 the graph remains a lattice/ geometric graph, while 13 == 1 yields a random graph. Watts and Strogatz [129], Newman and Watts [92], Pandit and Amritkar [96] and Watts [128] repeatedly demonstrated ,3 =2 0.01 — 0.05 z (9 (7%,) as a typical range of values for constructing small world networks, which means only a very small fraction of links has to be rewired. Hence, on the scale of randomness where lattice / geometric graphs occupy one extreme and random graphs the other, small world graphs fall in between the two, but closer to the former than the latter. 132 In the context of W SNs the property of random graphs to propagate information quickly means that nodes can relay important data back to the base station quickly. The property of Euclidean graphs to have high G and strong local connectivity pro- duces a stable network structure difficult to partition. It also enables the formation of clusters which facilitates collaboration among groups of nodes. Thus, the W SN application den'iands the best of Euclidean and random graphs. 7 .3 Small-World Topology Construction Methods for Wireless Networks There are several approaches to realize shortcuts in wireless networks with the intent of creating a small world topology. We conducted a survey of practical techniques. 7 .3.1 Hybrid Sensor Network Sharma, l\=’Iazumdar [111] and Chitradurga [27] proposed the judicious use of wired links between a small subset of nodes in a W SN . The resultant network is not a pure wireless network and is called a hybrid sensor network. The graph topology of hybrid sensor networks uses range limited links for shortcuts instead of truly random links. From a practical perspective the wired shortcuts limit the possible deployment scenarios. 7.3.2 Multi-radio Network The multi-radio node as a means to building small worlds was first proposed by Wan in [125] with the objective of easing congestion in the primary network consisting of ubiquitous low-rate links. The multi-radio node architecture has the disadvantage that it requires a heterogeneous mix of motes. The links of the long range radio 133 interface serve as small world shortcut links. The implementation used in [125] uses IEEE 802.15.4 [5] in conjunction with IEEE 802.11b [51] network interface. The significantly higher power consumption of IEEE 802.11b is a disadvantage in power constrained wireless SGDSOI‘ IIGUVOI‘kS. 7.3.3 Receiver Side Cooperation The third solution is based on single-input multiple—output (SIMO) principles and is dubbed by Ilyas and Radha as the ’Poor-Man’s-SIMO-System’ (PMSS) because it uses receiver side diversity combination techniques in a network of commercial-off-the- shelf components. Its principal strength over hybrid sensor networks and multi-radio networks is that it circumvents the need for customized or reconfigured hardware. Instead, it relies on receiver side cooperation in motes to form a SIMO system. This way c00peration reduces losses and retransmissions while increasing throughput and channel utilization. In [52] Ilyas and Radha describe the PMSS and how three well- known diversity combination techniques are adopted for use in a network of commer- cial IEEE 802.15.4 devices. The diversity combination techniques are derivatives of diversity combining methods for analog signals presented by Brennan in [19]. Simply put, the purposes of diversity combining are twofold; a) Select an error-free version of a received transmission from among multiple received versions or, b) If the first goal is not achievable, obtain another version of the transmission, with no errors or fewer errors than any of the individual received versions. In conclusion of this survey it should be understood that as diverse as these different implementations of small-world networks in wireless networks may be, the analytical model can be parameterized accordingly. 134 7 .4 Mean Field Analysis of Small-World Wireless Networks 7 .4.1 Clustering Coefficient Sensor nodes are distributed as a 2—dimensional Poisson point process with mean ,0 points (sensor nodes) per unit area. Let there be two nodes '01 and 212 capable of communicating with nodes within range R1 and R2, respectively. For simplicity’s sake we will take R1 = R2 = R. If the two nodes are separated by distance r < R then communication coverage regions of nodes 211 and '02 will overlap, as depicted by the shaded region in figure 7.2. Let A denote the size of the overlapping communication coverage regions. Then A is computed by adding the areas of sectors X OX ’ and X 0’ X ’ and subtracting the areas of triangles X OX I and X 0’ X ’ because they have been added twice during the addition of both sectors. The resulting expression for A is shown in equation 7.3. () A(6l, R) :2 g—NRZ — 2 - Rsind - Rcosél 7r =26R2 — R2 sin 26 (7-3) Here 0 is the central angle 1X 0’ X ' in figure 7.2. We can exm‘ess (I as a function of r. 6(r, R) = arccos “—2 R (7.4) 135 Substituting the expression for 6 in equation 7.4 back into equation 7.3 give us A as 26f 2 /1_ 7" A ,R =2R6 ,)R-— R —— — [ 7.5 =2R2arccos(r2R)—-7R-1—— ( ) As we already described, for the network topology to be a small world some nodes a function of r. have to provide shortcuts or global scale links to other nodes. These nodes will be referred to as shortcut nodes or global scale nodes. In literature, the graph formed by global scale nodes is also referred to as a network’s substrate [128]. The remaining nodes are called local scale nodes. The ratio of the maximum communication range of global scale link to that of a local scale link is called the scaling factor 5. Now, let p denote the average node density with which nodes occupy the covered region. The cooperative communication model for small world WSNS in section 7.3.3 for the implementation of shortcuts in a wireless sensor network requires multiple nodes to function as a single receiver. Depending on how many nodes are collapsed into a single node will reduce the effective node density ,0. Let nc denote the average number of nodes that combine to function as a global scale node. This reduces the node density in the equivalent small world graph (spread over area A) to p, which relates to {2 according to equation 7.6. p, -p _ Ngloballnc — 1) A (7.6) Note that when shortcut links are implemented in multi-radio networks (subsection 7.3.1) and hybrid sensor networks (subsection 7.3.2) the node density in the small world graph remains unchanged, i.e. nc— —— 1 which implies p - —p. Then A(r, R)p 136 Figure 7.2: Overlapping communication regions of two communicating sensor nodes in a WSN. denotes the number of edges 3. node (221) distance r away from a reference node (222) has with the set of nodes that can also communicate with the reference node. Let F(-v) denote the neighborhood of a vertex v E V, where V denotes the set of all vertices in the graph G of the wireless sensor network’s topology. We treat the entire region covered by sensors as a continuous, homogeneous sea of sensors populated with a uniform density of p, nodes per unit area. Then the total number of edges d in the neighborhood of vertex u can be computed by integrating A(r, R)p’ with respect to r over the interval [0, R], the radius of the communication range; The number of links in the neighborhood F(u) of a node v is denoted by d(F(u)). The exact derivation of the expression for d(F(v)) in equation 7.7is provided as lemma 1 in this chapter’s appendix. are)» =7rp/2R3(2.9604R — V3) (7.7) 137 Let D(F(u)) denote the number of edges in the completely connected graph of node v and its neighborhood F(v). D(F(v)) =7rp’R2 X 7rp’R2 = «262124 (7.8) The clustering coefficient is defined as the expected value of the ratio of the number of links in a nodes neighborhood to the number of links in a complete graph of its neighborhood. This can also be defined in terms of previously computed values as; _ d> C(Gl ‘EV [Danni (79) For a node that is part of the sea of sensors communicating over local scale links only we define the clustering coefficient Clocal as, _ dam) _ 2.960412 — \/a local _D(F(U)) _ 7TH ~2.9604R — \/§ (7.10) NR Hence, Clocal grows O (712) with respect to R. For a node that is part of the substrate communicating over local as well as global scale links we define the clustering coefficient Cglobal as, C dfrlvll + kglobal l b l: 9 O a D(F(’U)) + kglobalOO/WRZ) 'l' (kglobal _ 1)! (7-11) 138 1 -, 9.‘ . ,- l. I I, .. ‘r 1 .1». .11 r ,., s. 1 . [q ’V '1 ‘ . u... g I 0 -.. 1. '. « ' I. “F, ‘ ,_ 1 -¢-. .5 71.0] 'i‘ l“-A -2 1 h i'. ‘1' [l‘ .l. “';.I l | 9 L.” | . \ « h, “\ flu? ] ”:31ij Note that in doing so we assumed that 6 Z 2. Here k l is the average degree of globa nodes in the global scale network or substrate with other nodes in the global scale network. The function for C rows as O n 1 ). It must be noted here global g (W that in the computation of Clonal and Cglobal ignores border effects and assumes nodes are spread on a torus. To obtain the clustering coefficient of the network G local and Cglobal are combined in the ratios in which local and global scale nodes appear. N If we define a = . globarl then C is obtained by equation 7.12. f global‘l'Alocal C =12C' +(1— u)C global local (712) 7 .4.2 Characteristic Path Length The characteristic path length of a graph is defined as the average length of all geodesic paths (measured in hops). In a graph G(V, E) the characteristic path length L is defined as the average of geodesic path lengths [(211, uj) between all connected pairs of vertices vi, uj E V and u,- # uj. Like the clustering coefficient, the characteristic path length is also a function of the number of nodes with global scale links. Since the global scale links are range-limited, and since global scale nodes have to be placed within communication range of one other to be useful, the area covered by them is also limited. The region of the WSN that is serviced by global scale nodes may be fragmented into many different patches. Figure 7.3 shows a model of a WSN. For analytical ease the shape of the region covered by all nodes of the network is approximated by a circle of radius VA and center 0. The region covered by global scale nodes is approximated by a circle of radius m < x/A also with center 0. The difference between coverage areas of the entire WSN and only the global scale nodes is a result of the constraint imposed by a) the limited range of shortcuts and b) 139 A f ..l the global vertex degree (the number of shortcut links incident on a substrate node). Figure 7.3 also shows a node :1: distance removed from O. For the node in the figure :1: > g and the sensor region can be divided into three separate regions, numbered 1 through 3 in the figure. These regions are defined relative to every node 2). Region 1 consists of all sensors that are reachable from 22 without having to traverse any global scale links. In figure 7.3, for node v at distance :1: from center 0, region 1 corresponds to the uncolored white region. Region 2 is the area of size Ag occupied by global scale nodes and is colored solid gray. Region 3 is the region occupied exclusively by sensors with local scale links but which is reachable (by a shortest path) only after traversing region 2. In figure 7.3 region 3 is identified by shading and it’s area is denoted by 5 (:13) Assuming the deployment of sensors is sufficiently dense, we approximate the geodesic path from one node to another by a straight line between them. To proceed we define three central angles (1 = %ABOB’, [3 = .480] = ABIOJ’ and ’y = AJOJ’, where 2(02 + 13) + 'y = 277. Since a and c): are functions of :r we will be denoting them by 07(2) and 7(2). A 9 x (7.13) (1(a) = arccos Ag fl (7.14) 13 = arccos ';r=7r— (1:1:— ’3: 7r—(11t— a() 2 2f) 21 2f (l 6) (7.15) 140 \ 't'[_ ., . ~.[‘4V. w ‘4 \/A X z VA—i Figure 7.3: Geometry of W SN deployment and regions within it with respect to an individual sensor 22,-. The area of the region in figure 7.3 labeled region 3 is (see lemma 2 in the appendix) given in equation 7.16, 26+y Ag 5(1)) :2 AAg sin/3 + £0? " 02(2) _ B) — 2 (716) 141 Characteristic path length is denoted by L. It is the average length (in hOps) of all geodesic paths from every node u,- E V to every other node uj E V. Llocal is the average number of hops contributed to geodesic paths by local scale links, while L l is the average number of hops contributed to geodesic paths by global scale globa links. Then L can be expressed as equation 7.17. L =L + L local global (717) Based on the 3 regions of the \NSN in figure 7.3, geodesic paths are classified into one of four different types. Type 1: Geodesic paths that originate from and terminate at nodes in region 1 and (outside the region covered by the substrate). Type 1 paths consist of local scale links only. Type 2: Geodesic paths that originate from a node in region 1 and terminate at a node in region 2. Type 3: Geodesic paths that originate from a node in region 1 and terminate at a node in region 3. Such paths pass through region 2. Type 4: Geodesic paths that originate from and terminate at nodes in region 2. We compute Llocal (L ) in equation 7.18 (equation 7.19) as the sum of Llocalffl (L global globalalli the contributions of local (global) scale links to type 2 paths, weighted 142 i“ ll F3: Ll .. '1'“. \ .V by the normalized frequency of occurrence of type 2' paths. 4 1 . Llocal zfi Z Llocalm i=1 (7.18) 4 1 . Lglobal 26—}? Z Lglobalm ' 2:1 (7.19) (1) [0601(1) denote the average For a node v in region 1 at a: > Ag distance from 0, let l spatial distance on type 1 paths traversed over local scale links. Then for a particular node the size of region1 is A — Ag — 5 (.13) Since the deployment of sensors is in 2 dimensions we approximate the size of the region traversed by these paths by the square root of its area, \/ A — Ag — 5 (2:) Although region 1 is irregularly shaped we approximate the spatial distance by one half of it, assuming the sensor is located (1) approximately in the center of region 1. Then [localml is given by equation 7.20. <1) 1 . local( ) 2\/ g ( ) (7.20) A node v at distance a > , /Ag from O has pllocalffl paths to other nodes in region 1. To obtain Llocalu) we integrate this term over the entire region of deployment of the W SN, i.e. all circumferences of radii ranging from , /Ag through VA. This is 143 shown in equation 7.21. L (1) =—1——— fl 277.1:- (A — A — 5(1)) 1(1) ($)d:r local (p/A)2 mp p 9 local (721) Since the paths from u to other sensors in region 1 do not traverse region 2 no global scale links are used. Hence L globalU)’ the component of global scale links in paths to sensors in region 1 is 0, as in equation 7.22. L (1) = 0 global (7.22) (2) For a node v in region 1 at I > Ag distance from 0, let l l oca [(2) denote the average spatial distance on type 2 paths traversed over local scale links. It is approximated by the mean of the shortest (:r —— Ag) and longest distances (from node v to point B) from v to a node in region 2, i.e. %(:r — fl + :rsin (1(2)). To include paths from nodes in region 2 back to node 22 we multiply this term by 2. This is approximated (2) by equation 7.23. We roughly approximate lgloballx) by the square root of the area of region 2 in equation 7.25. ,(2) local<$l =11: — ”Ag + assin (1(2) (7 23) Llocal(2) (equation 7.18) is the component of Llocal contributed by node u’s type 2 paths, i.e. to other nodes in region 2. A node v at distance :L' > ,/Ag from 0 has p”Ag paths to other nodes in region 2. To obtain Llocal(2) we integrate this term over all circumferences of radii ranging from «Ag through \/A. This is shown in 144 equation 7.24. (NA)? local . 1 VII 2 LZOCGZQ) =—/ . 102711" ' PHAgl( ) (.L')(l;r V A9 (7.24) The length of global scale paths from v to sensors in region 2 is approximated like in equation 7.25. 1(2) (I) = Ag global (7.25) Equation 7.26 weighs this by the number of paths from all 2: outside of region 2 to all sensors inside region 2 (and vice versa) relative to the number of paths between all pairs of nodes, i.e. (p’A)2. Lglobalgll =(/—)-——/14)2/\/_A_g/)27r.”rp Am/A gda: :ppllnAg 32/ (A— Ag) (7.26) (P’A)2 (3) For a node v in region 1 at :1: > A9 distance from 0, let [locallxl denote the average spatial distance on type 3 paths traversed over local scale links. It is approximated by equation 7.27. 1‘3) (1:17) ()+’/‘72_7 local local (.1: + V_— (/A 9+ 2:1: sin 0( (727) 145 A node v at distance :1: > ,/Ag from O has p5 (:13) paths to other nodes in region 3. To obtain Llocall3) we integrate this term over all circumferences of radii ranging from ,/ Ag through VA. This is shown in equation 7.28. . (3) p27r1: - p5(;r)l , (:1:)d.1: local (7.28) I L . . 3 :— 1()C(ll( ) (/)/A)2 / /—‘49 For Lglobalw) in equation 7.29 we approximate the length of global scale links by the diameter of region 2, 2,/A , and weigh it by the total number of paths from all u to nodes in region 3, {)5d(r). 1 VA L 3 277.1: )5(.1)2g(l.1: globall l: (p A—T—fg / r—4 P I 1W (7.29) (4) Final[fifor a node 22 in region 2 at distance x < Ag from 0, let [local denote the average spatial distance on type 4 paths traversed over local scale links. We assume that on average, a node ’U in region 2 communicating with another node in region 2 will route (over local links) to a nearby node with global scale links. Once traffic has I""‘l‘lu‘d the vicinity of the target destination node traffic is routed over local scale links to the destination. Let hmag; denote the maximum distance of a node from its Closest global scale node, as expressed in equation 7.30. l A h h=1 ‘ global (7.30) 146 Assuming that equidistant nodes form concentric bands around global scale nodes the probability mass function p H(h) of the hop distance H is modeled by equation 7.31. «(1.12)? — «((11 —1)R)2 2h — 1 pH(h) = 2 = 2 ' 7r(hmaiL‘R) hmaa: (7.31) Then the 1(4) local is approximated by the expected value of H as in equation 7.32. hmaa: 2h _ 1 (4) l . =5 H lhl = h local ’12::1 hgzax (7.32) A node v at distance :1: < ,/Ag from 0, within region 2, has pi/Ag paths to other nodes in region 2. To obtain Llocal<4> we integrate this term over all nodes in region 2. This is shown in equation 7.33. L1 . 1(4) =_—2(p”A9)21(4) 06“ (1M)2 local (7.33) L (4) —2(p”A9)2 , /A 910’” (1)/A)? 9 (7.34) NOW We can back substitute equations 7.21, 7.24, 7.28 and 7.33 into equation 7.18 \0 Obtain Llocal' Similarly, equations 7.22, 7.26, 7.29 and 7.34 are put back into equation 7.19 to obtain L Equations 7.18 and 7.19 are substituted into 7.17 global“ to obtain the characteristic path length L. 147 Clustering coefficient C vs. u Characteristic path length L vs. n 0.09- , 120- ' IIIIIIIIIIIIIIIIIIIIIIIIIIIII +R = 3 0.088""""'"-""‘--‘--'--'- +R =4 _.-.-.-.-._.______, 100— +R=5 0.086~ . :§;: 0'084— I I —+———R:9 """""‘-'?-----'-------j . _+R= 10 0 0.082- 4' .4 60 . —R = 3 ‘ 0.083'"R=4 ------.-.. ..,.R:5 40' '''''' R=6 0.078~ —R= 7 --- = 20' l n V 0076:," 2 =3 - . _____ ’ _____ O 074 lllllll R =10\ G ":-:-: -: i 247-: :.-;-. , :: : ; L; ' 0 0.5 1 0 0.001 0.002 H H Figure 7.4: Plots of clustering coefficient C [left] and characteristic path length L, lfight] as functions of u for different values of R. Network parameters that remain fixed are A = 10000, kglobal = 4, p = 10, f = 3 and 11c = 1. 7-5 Observations 111 this section We explore the behavior of the analytical models of clustering coefficient C and characteristic path length L as we vary the length of local scale links R, the average degree of shortcut nodes in the substrate k l and the scaling factor 5. globa For the following evaluations we assumed a network of 100,000 nodes in an area of size A = 10, 000 and 110 = 1. Unless stated otherwise, the default parameters of the network are R = 3, g = 3 and kglobal = 4. Figure 7.4 plots the clustering CDeficient and characteristic path length of networks as functions of 11, the fraction Of nodes that are shortcut nodes, for different values of R. The clustering coefficient 148 Clustering coefficient C vs. u Characteristic path length L vs. a 0_O3924..., ' ‘ 350 - - " ‘ —B—§ : 3 _ 300 4 —.e.—§ = 4 0.039 : +§ = 5 0.0388— ' 1 +5, = 7 —n—§ : 8 O H —+—§ : 9 0.0386——§=3 +§=10 . . .g = 4 a = 5 0.0384 IIIIIII é ___ 6 - _g = 7 0.0382—---§=8 _ .... E“ = 9 0 ““““ i = 10 ; . _ . '0380 0.5 1 00 0.005 0.01 0.015 11 11 Figure 7.5: Plots clustering coefficient C [left] and characteristic path length L, [right] 88 a. function of 11 for different ratios of global scale link to local scale link communi- cation range é. Network parameters remain fixed at. A = 10000, kglobal = 4, p = 10, "c = 1 and R = 4. 0 appears as a linearly decreasing function of )1 with identical slopes. The clustering (30(‘fficient has higher values for longer range R of local scale links. The right pane of figure 7.4 plots the Characteristic path length for various R. Higher values of R imply that destinations can be reached in fewer hops, thus reducing the characteristic path length_ This is born out by the curves of L. Moreover, a side—by—side comparison Clearly illustrates the phase difference in the reduction of of C and L. This means the derived analytical model indeed captures the small world effect in the network. Unlike in Watts’ fl—model [128] of constructing small world networks, C lacks a sharp drop OE as l4 ~+ 1. The reason for this is the range limitation on shortcuts which imposes a 149 Clustering coefficient C vs. u Characteristic path length L vs. ll +kglobal = 2 +k = 0.08 global 4 4 . , 4 . __ kglobal = 4 0.078 .. . .' . r 4 +kglobal = 5 _. I .. d .. d P i +kglobal = (1076" kglobal - O —+—k = 0.074 ---- global “rte-oval ' 0.072 '— 0.07r - . O 068 """" global = O . _ . 0 0.5 1 0 0.001 0.002 n 11 Figure 7.6: Plots clustering coefficient C [left] and characteristic path length L, [right] as a function of a for different values of kglobal' Network parameters remain fixed at A = 10000,p=10,§=3, R=3andnc=3. degree of localization in a shortcut link’s reach which leads to clustering. In addition, all construction methods of small world WSN in section 7.2 add shortcuts on top of the existing geometric graph instead of rewiring existing links as the ,B-model does Where each global scale link is added at the cost of removing a local scale link. Figure 7.5 plots clustering coefficient C and characteristic path length L as func- tions of l1 for different values of global scale link scaling factors 6. Recall that in deriVirig the analytical model for the clustering coefficient we made the assumption that 5 2 2, i.e. shortcut links have a communication range of at leats twice that Of local scale links. Note that in figure 7.5 all plotted function of C overlap, i.e. as long as as the assumption 5 2 2 holds, the clustering coefficient as a function of p is 150 independent of the global scaling factor g. The small world network effect is clearly visible by the large gap between clustering coefficient and characteristic path length. AS expected, the drop in characteristic path length L drops off earlier as 5 increases, i.e. fewer shortcuts are necessary to achieve the same reduction in L as shortcuts get longer. For the networks in figure 7.6 we varied the average number of shortcuts kglobal incident on global scale node. Larger values of kglobal imply a slower expansion of the area within a WSN that is serviced by shortcut nodes (region 2 in figure 7.3). Figure 7.6 shows that as kglobal increases, the rate at which the clustering coefficient drops increases. We also observe that the number of global scale nodes needed to achieve a significant reduction in L also increases as evidenced by higher value of a to achieve the same characteristic path length L for higher kglobal' That is because at higher kglobal the range limited nature of shortcuts forces more global scale nodes to be deployed in closer proximity. However, we observe consistently that the small world effect holds in 2-dimensional Spatial graphs with range limited shortcuts such as those formed by WSNS with some shortcuts. What is also interesting is the fact that for a sufficiently dense WSN the number of shortcuts that is needed to achieve a significant reduction in L is very small. 7-6 Conclusions We derived analytical models for both clustering coefficient and characteristic path length of a 2-dimensional spatial graph with range limited shortcuts that models the tOpological constraints to which W SNs are subject. 1' The model is sufficiently general to accommodate any small world network COnstruction methods in wireless networks previously proposed for W SNs and 151 is, to the authors’ best knowledge, the first analytical model for networks with these constraints. 2- VVe observed that for sufficiently dense networks characteristic path length can be reduced significantly by replacing a 11 z (9(0005 — 0.05) fraction of the local scale nodes by global scale nodes providing shortcuts in the network. The order of ,u, the fraction of nodes that are designated shortcut nodes, is about the same as the value of b, the rewiring probability, in Watts’ small world network construction method. 3. Whichever small world network construction method is applied carries with it a cost. The model lends itself for the task of designing WSNs, e.g. determining the number of shortcut nodes required to achieve a certain characteristic path length. APPENDIX Lemma 1. We derive the expression for d(f (11)), the number of links between the 36’: of nodes consisting ofv and all its neighbors T(u). The region covered. by F('U) is approximated by a circular region of radius R centered at v. Consider another node ”I at a distance r from node 1) shown in figure 7. 7. Then the number of links from v, to other nodes in Nb) is A(r)p’. The narrow ring of width dr is inhabited by 27rrp’ Other nodes at the same distance r from u. The number of links from all nodes at distance 7~ from v is 24.,.p/A(.,.)p’4 Then, to find d((F(’U)), the total number of links between nodes '1) and [(11), we integrate 27r7~p’A(r)p’ with respect to r over [0, R], the 152 ra di'us of communication of v. R / / d(F(i')) 2/0 /) 27rrA(r)/) dr R R :/O p’227rr 2R2 arccos _QLR — _2_r 1 — 2172—?) dr R . R (7.A-1) =47rR2p/2 / r arccos —r—dr — Zp/Z/ rQV 4R2 — r2a'r 0 2R 2 0 =47rR2p’2 . A(R) — gp’2.3(1{) W’here A(R) and BU?) are evaluated in equations 7.A-2 and 7.A-3. . , 1 l .2 All?) = arcsin (57-1?) R2 — §r 1— 47—52-51? +1 2 < " > R —" arcc °‘ — 27 Ob 2R 0 1 l = arcsin (g) R2 -— jig—R + 5R2 arccos (5) =13? _ —\/—§R 3 4 2 1, ,/ . . . . 313 4R2 _722F1(15’—05,25,4—7l€2) 7.2 1 __ 4R? 153 (7.A-‘2) (7.A-3) 2171 (a; b, c, 2) denotes the hypergeometric function {equation 7.A-4) and is evaluated in equation 7. .4-5, . . .., __ Fe) ”5,404,044 2F1(a,b,c,4) —F(b)P(C- b)‘/0 (l —t2)a (it (7.A-4) 1 —r5 _t2 = — 0.1875 / t (1 ) dt (7'A'5l 0 . Substituting the value of the hypergeometric function from 7.A-5 into equation 7.A-3 P’I‘Od‘uces equation 7.A-6. BU?) =§R4 «2 F1(1.5; —-O.5; 2.5; 0.25) — 0 = 06142-134 (7.A-6) Substituting A(R) and BU?) from equations 7.A-2 and 7.A-6 back. into equation 7.A-1 gives equation 7.A-7. d(l‘(v)) 22.9604np/2R4 — flap/2R3 (7 A 7) LeInma 2. We compute the area of region 3 in figure 7.3 for a node a? distance from O denoted as S(at), where :1: > ,/A9. In order to proceed we compute the area of triangle BOJ denoted by A(:r). For :2: > ,/Ag, A(r) can be expressed in previously defined terms as, 154 Figure 7.7: Graphical representation of integration term of d(F('v)). A: A ‘fls' i3 l7 ... (7.A—s) Similarli, the area of sector JOJ’ with central angle 7' and radius #7 is denoted by ,\ A(CL’). For :1: > ‘ Wig, A(at) can be (;'.'17pr(_ess(_zd in previously defined terms as, lilac) =A/éir)7r\/ZZ = g(n —- oz(a') — [3) 7T (7.A-9) The area of sector 308’ with central angle 2/3 + 7 and radius ,/A9 is denoted by A(l‘). The, for :1: > M] , like) can be expressed as, 2 awn/(as) 2 2s+'y(:r-) A(x):—27r—7Tl/Ag = —-—2——Ag (7.A-10) 155 We now use Mr), like) and [KL/t) to obtain the area of region 3 denoted by 5(a). 3(1?) =2A(;L‘) + Ru) — Km . A 2.13+“/(~T) : ./ _ _ ,.._ __ 7.A-11 2,/AAgana+2(n an) a) 2 Ag ( ) 156 Chapter 8 Enabling Cooperative Communication and Diversity Combination in IEEE 802.15.4 Wireless Networks Using Off-the-shelf Sensor Motes 157 8 . 1 Introduction Channel fades and interference effects limit the throughput, useful communication range and (in case of battery powered devices) lifetime of nodes. In this chapter we describe the generalized ‘Poor Man’s SIMO System’ (gPMSS), a readily deployable lovv—cost, low-power, protocol centric approach that enables cooperative communi- cation in IEEE 802.15.4 [5] wireless sensor networks (WSN). We demonstrate that gPlVISS reduces the fraction of packets that are received with bit errors or not re- CE‘iVEEd at all by an order of magnitude, thus reducing the number of retransmissions. It Illakes the use of long range links that are unfeasible due to high packet loss and retransmission rates for sible again. We also show that even in instances where gPMSS is not able to correct all errors from a packet it still succeeds in reducing the number of bit errors. At the receiver side gPMSS uses diversity combining methods adapted fI‘Onl their analog domain counterparts of the same name [19] for digital signals. W hat. nl'cxkes the application of SIMO diversity combining principles novel from traditional “'38 is that they are applied to the demodulated version of received packets, after p1lysical layer processing. W‘ den'ionstrate the efficacy of gPMSS by applying it to bit error traces collected from IEEE 802.15.4 channels that allow detailed analysis and precise reproduction of results. we also demonstrate gPMSS’ effectiveness under real- WOrld conditions by implementation on Crossbow’s Imote2 .NET Micro Framework SEinsor platform [35]. Enabling the use of long range links (that would otherwise not be used) makes gPMSS a viable protocol due to the benefits and utility of such links by several applications in wireless sensor networks. Network Lifetime Extension: Funnel-ing is the effect of network traffic from multi- ple sources flowing to a small number of sink nodes [125]. This traffic surge produces COngestion in the region around the sink nodes / base station, forcing nodes near sink 158 s sis-3E!- ‘FT-m nodes to relay more traffic than other nodes and consume power at correspondingly higher rates. Since nodes in W SNs have only limited power resources this means that the sink node’s neighbors will run out of power sooner, leaving the sink node discon- nected from the rest of the network. Load balancing techniques like [53] attempt to distribute the burden of relaying traffic to increase the lifetime of sensor networks. Em ploying gPMSS in such a scenario will grow the set of neighbor nodes of the sink IlOde and allow load balancing among more nodes. Small—world Networks: Several attempts have been made at building small-world network [128] topologies in wireless networks to simplify resource discovery and re- ducin g average path length to facilitate data dissemination. Proposed architectures required hardware modifications such as adding a secondary radio frequency interface (l1 24],[125]) or building hybrid networks by augmenting wireless networks with wired ShOI‘tcuts ([111],[27]). Since gPMSS is a protocol centric approach it does not require any hardware modifications which adds to its appeal as a lox-x-r—commexity and low-cost SOlution. Network Connectivity: Long range links can be used to add links between two COIliponents of a network that are only sparsely connected with one another. gPMSS adopts well—understood diversity combining methods for analog signals and applies them to digital signals (packets). Specifically, gPMSS implements selec- tion diversity, equal gain diversity combining and maximal—ratio gain diversity com- bining. The latter relies on a model of the instantaneous bit error rate (BER) driven by channel state information (CSI) [55], i.e. received signal strength indication (RSSI) and link quality indication (LQI). We provide proof of concept by applying gPMSS tO channel traces and demonstrate one order of magnitude reduction in packet losses. Applying gPMSS to traces allows more detailed analysis and reproducibility that is rlot possible in a live setup, i.e. the event when receivers are not able to reconstruct an error-free version of the transmission. We show that even then we are able to 159 . Low packet loss ’ . communication range, FigLIre 8.1: Application of generalized gPMSS in a wireless sensor network with mesh toDOlogy. Path from transmitter T to receiver R1 marks the multihop path that would be taken in a network without gPMSS. Dashed line links between T and receivers R1, R2 and R3 denote the longer range but high loss links that are used under Generalized gPMSS. Siglnificantly reduce the average BER of incorrigible packets. Finally, we implement gPMSS on Imote2 sensor motes [35] using C# and demonstrate a clear reduction in packet losses. Experimental results from IEEE 802.15.4 links indicate that using diversity combining raises packet reception rate (PRR) by up to an additional 130% Over those in a single receiver. Our contributions are threefold; 1. gPMSS is a protocol centric, cross-layer approach which means it can be used in presently deployed wireless sensor networks by making software changes only. It does not require any modifications to hardware but. runs on networks of commercial off-the-shelf (COTS) single antenna sensor motes. 2. gPMSS is non-intrusive in the sense that it does not require changes to the pre—existing IEEE 802.15.4 standard. 160 3 - gPMSS is able to reduce power consumed at the transmitter per packet delivered by up to 68%. This represents a significant increase in the lifetime of sensor node. Figure 8.1 illustrates the difference between routes traversed by a packet sent by transmitter T to a distant node R1 when gPMSS is used (dotted arrows represent long range links, solid lines represent links between R1, R2, R3 that form a fully connected graph), and the multi-hop path from node T to R1 when it is not used ( SOlid arrows). The remainder of this chapter is organized as follows. Section 8.2 reviews some related works. Section 8.3 describes the three diversity combining techniques for paCket recovery. Section 8.4 describes the gPMSS that enables cooperation between ITlllltiple receivers. Section 8.5 describes the trace collection setup and demonstrates a proof of concept of gPMSS in a manner that can be reproduced. Section 8.6 deSCribes the gPMSS implementation on Imote2 and its results. Section 8.7 discusses 0111‘ results in terms of PRR, retransmission attempts and energy consumption per 13 a-Cket. Section 8.8 concludes this chapter. 8 ~ 2 Related Work T119 concept of spatial receiver diversity is not new and has been studied extensively in the analog signal domain. Chakraborty et al. proposed the extended automatic reliDeat-request (ARQ) scheme [24] that recombines spatially diverse versions of a re- CeiVed packet to detect bit errors and an exhaustive search to correct them if their n\Unber is less than a threshold value. Extended ARQ has a lot in common with the version of gPMSS that uses equal gain combining and is agnostic of what MAC Standard is used, but the results provided in [24] are based on theoretical analysis Only. Miu et al. [83] proposed a system that used transmitter diversity to increase 161 ‘C packet reception rate in IEEE 802.11 [51] networks with multiple access points (AP) as senders. The scheme roughly corresponds to gPMSS with selection diversity, with- out diversity combination for error correction. Miu et al. generalized this approach i n [85] for applications beyond streaming video. In [84] Min extended the idea further to reduce packet losses on the uplink (mobile device to AP). However, this required n‘lodifications to IEEE 802.11b AP hardware or deployment of more APs, and uses EL dedicated frame combiner connected to all APs through a wired network. It used the equal gain method for detecting bit errors and, like extended ARQ, relied on all exhaustive search of the correct bit values. Cheng and Valenti [26], [123] ex- tGlided the idea for improving throughput on uplinks in IEEE 802.11a networks by l-lsirlg maximal ratio combining based on CSI measurements. However, like Miu’s 85" Stem it still required a dedicated combiner connected to all APs. In [60] Ji et al. Dr C>I)osed an approach for improving the throughput of downlinks by scheduling trans- nl iSSions to multiple receivers in IEEE 802.11a/ b networks based on explicit feedback from receivers while maintaining fairness. In [7] Bahl made the case for multi-radio tr‘Efl—rlsmeivers, but as figure 4 in his paper showed, collaboration between network in- terfaces is possible only when they are all located on the same device. More recently, VVOO described SOFT [134] which also exploited receiver diversity for the uplink in IEEE 802.11 networks similar to Miu’s in [84], but with diversity combining being I)erformed using maximal ratio combining. Therefore, it too requires a centralized combiner on the wired network that all APs are connected to. To summarize, the g1DIVISS system presented is distinct from all these prior works on cooperative com- r111lliication and diversity combining in wireless networks because it is (1) designed for IEEE 802.15.4 networks, (2) is purely implemented in software and COTS motes ‘Vithout modifications to mote hardware, (3) is tested on bit error traces collected from real IEEE 802.15.4 channels, (4) as well as actual implementation on motes. 162 ‘Ii! MPH Int-“r 8 - 3 SIMO Diversity Combining Techniques T118 solution that is described in this section is dubbed the generalized ’Poor-Man’s- SIB/I O-System’ because it uses receiver side diversity combining techniques and is 1 ) uilt using commercial-off-tlie-shelf components, without customized or reconfigured llardware. Receiver diversity improves link quality of wireless channels with high losses. This way we reduce losses and retransmissions and increase throughput and (:11 annel utilization. This subsection describes linear diversity combining techniques. All these techniques are derivatives of the techniques by the same names presented by Brennan in [19]. Brennan describes scanning diversity, selection diversity, equal gain (iiVersity and maximal-ratio diversity combining. Although the methods described })3’ Brennan were meant for analog signals, we have suitably modified and adapted tllern for use with demodulated, digital signals. we have included the last three, Selection, equal gain and maximal-ratio diversity combining. Readers should know t" 118-t even when the diversity combining method used is either equal gain or maximal- r'd'toio combining, selection diversity is used whenever at least one receiver possesses an error-free version of a transmissions. Equal gain or maximal ratio combining are 0 . . . 111)? used when none of the gPMSS receivers was able to receive error—free (1.e. the Si . . . . . . . t' 11 ation described in figure 8.5c). The purposes of diverSIty combining are twofold. 1 . Select an error-free version of a received transmission from among all received versions. 2. If the first goal is not achievable, obtain another version of the transmission, with fewer errors than any of the individual received versions. 163 8 - 3 -1 Selection Diversity Selection diversity is the simplest diversity combining technique. Figure 8.2 is an equivalent system diagram of the selection diversity process. The basic idea in is to select from all received packets the one that is expected to have the fewest errors. T11 is is advantageous when it is used in conjunction with forward error correction ( 2F EC) because fewer bit errors are easier to correct than more bit errors. When all r€2C‘eived versions have errors, the best selection diversity can hope to achieve is pick tl‘le version with the fewest bit errors. We define the BER of the nth packet in a Sequence as, # of error bits in nth a la BER=6[n] = "BC“ 10 . # of bits in nth recvd pkt (81) Tlllls the underlying random process producing the sequence of BER observations [3 [71] is called the BER process and is denoted by B. The term BER is not used in its St 1‘51 Ct traditional sense where it denotes the long term average probability of bit errors, 811 Ch as in a binary symmetric channel (BSC). instead the BER is computed over each re‘Qeived packet. Unfortunately, under ordinary circumstances the BER process is not directly observable. A packet’s failure to pass the cyclic redundancy check (CRC) test only tells us that the number of bits with errors is non-zero (B > 0), but it (10 es not give any information about the number of errors. Therefore, we must rely on estimates of the BER. The performance of selection diversity will be determined by the accuracy of the model used to predict the BER of packets that fail the CRC test. We have used Ilyas and Radha’s [55] CSI measurement-based model of the BER process on IEEE 802.15.4 links. For each received packet the model relies on two CSI parameters, i.e. LQI, and RSSI. Measurement of both RSSI and LQI is mandated by 164 ill .' tlle IEEE 802.15.4 LR—WPAN standard for every received packet. The RSSI random pro cess is denoted by P, and RSSI measured by a receiver R for the nth packet in a sequence is denoted by pR[n]. VVe used the MICA2 [34] to demonstrate proof-of-concept and the Imote2 [35] to (ienjonstrate the functioning gPMSS protocol implementation, both of which use the Chipcon CC2420 radio transceiver [120]. Technically, the CC2420 does not measure t1'le LQI directly. Instead, it measures the correlation C between the first 8 received SDv’ITIbols (of the PHY header) and the corresponding 8 known symbols (preamble). IEEE 802.15.4 uses lG-ary ()ffset-Quadrature Phase Shift Keying modulation which el”Icodes 4 bits in one symbol. The first 8 symbols, 4 bytes, of the PHY header C()1'r1prise of the Preamble sequence consisting of 32 binary zeros. The LQI is then C1EEfined as, LQI 2: (C — Cl) - 02. (8 2) In the Chipcon CC2420 c1 and (:2 are functions of the packet error rate (PER) I11‘38.sured over an extended period of time and are determined experimentally. c1 and c2 scale the 7 bit value of the correlation to the range of an 8 bit number. Since eq‘u ation 8.2 is merely a shifting and scaling of the measured C we take Cl = O and C2 2 1. The LQI random process is denoted by A, and LQI measured by a receiver R for the nth packet in a sequence is denoted by ARM]. Coming back to our description of the CSI-driven BER model of [55], each pair of LQI and RSSI inputs produces a probability density function (PDF) of the BER of packets received with those particular CSI measurements. To be useful in the current C30ntext, the output of the CSI-driven BER model has to be mapped to a single value. VVe use flcho to denote the X th percentile of the BER process’ PDF (550% is 8’3 mean). The instances of the BER model return BER estimates denoted as MR1), 165 5 ( R2) and BUB). The output selector in figure 8.2 receives as input the estimated BERs MR1), MR2) and BUB). Based on these estimates it selects the receiver with t.11e lowest BER estimate as the least error-prone one and accepts its received copy e1.s the best one and outputs it as D(Sel), i.e. D661) 2 D j "'1! A A(RZ) (R2) F A [3(8) _r // fl / . R2 (R 2) > BER B / / / p > Model ./ ///\[ ~D(R3) 0 (R3) utput R3 A ‘ BER BR” > Selector PR3) > Model Figure 8.2: Illustration of logical functioning of selection diversity. ~D(R1) (JO R2 R1 1 ., ~ (R2) ,c ... D ~D(R3) R3 Figure 8.3: Illustration of logical functioning of equal gain diversity. 8 .4 gPMSS Protocol This section describes the operation of the gPMSS protocol. Assume a W SN consist- ing of a large number of single-antenna COTS receivers communicating over multiple hops with the base station collecting data. According to some topology construction 168 T ~D (R3) R3 A = BER 9(R3) : Model Figure 8.4: Illustration of logical functioning of maximal-ratio gain diversity. algorithm, a node R1 is chosen as an upstream end-point of a link. To use R1 as part, of a set of multiple receivers we propose the gPMSS protocol that defines the message exchange between cooperating receiver nodes to handle transmissions that at e received with errors or not received at all. The following subsection provides a br ief overview of gPMSS protocol message exchanges for four important operations. For T illustrative purposes we assume a scenario in which there is a distant transmitter and a receiver R] with two neighbor nodes R2 and R3 that are located close enough to communicate with R1 with few losses. 8 «4.1 gPMSS Cluster Creation Tlle ’Poor Man’s SIMO System’ described by Ilyas, Kim and Radha in [52] differs from gPMSS in the way clusters of receivers are formed. Cluster creation in PMSS was e3-(plicit, and required the operation by which nodes R2 and R3 come to be associated as cooperating receiver nodes of a node R1. In gPMSS nodes take advantage of CSI 0f overheard messages. Figures 8.9 and 8.10 density functions of LQI and RSSI of packets originating from R1, R2 and R3. Nodes in a network with the gPMSS protocol 169 _ A" j ..""":’====1:::::_- _~_-:_-:_-:_._.::::: _________ / .................... ...... R2) ‘ D( ACK ACK (a) Reception of an error free packet by a (b) gPMSS message exchanges when parent re- gPMSS cluster. ceiver R1 receives message with errors but child R2 receives error-free. Diversity combining (c) gPMSS message exchanges for recovery of data when neither parent R1 nor children R2 and R3 receive error-free. Figure 8.5: gPMSS protocol operations. will maintain such histograms for all neighbors from which they overhear traffic. A high mean, median or mode of LQI and RSSI density functions is indicative of a link with high PRR. In this way, once a node determines it enjoys good link conditions with a neighbor it will act as a member of that neighbor’s cluster of receive nodes. However, unlike in PMSS this association will not be made explicit by an exchange of 170 (YI messages. Instead, the node will make its contribution by participating in selection diversity and diversity combining functions of the neighbor node. For the following discussion we will assume that this way two nodes R2 and R3 placed close to R1 make the assessment that they enjoy a reliable wireless channel with R1 and volunteer to assist it as cooperating receivers. 8.4.2 Error-free Reception by at Least One Recipient This section describes the exchange of messages under the gPMSS protocol that occurs when at least any one of the receiving nodes receives a transmitted packet without errors. Figure 8.5a depicts the simplest case. The solid lines represent the transmission and reception of a message between source and destination node. The dotted lines represent communication that occurs implicitly as a result of a receiver operating in promiscuous mode, (deliberately) eavesdropping on messages exchanged between other nodes (marked by solid lines). Here T sends a data message D(T) to R1 that is overheard by R2 and R3. R1 will promptly responds to T with an acknowledgement (ACK). R2 and R3 overhear the ACK and recognize that the packet was successfully received by R1 and no further action is required. Figure 8.51) depicts the case where R1 is not the final destination. In addition, T) let us also assume that R1 receives the transmission D( with errors (marked by a zigzagged arrow), whereas R2 and R3 receive the same error-free. What happens is that all receivers that receive D(T) error-free choose a random wait-time t1 from an exponential PDF limited to the range [0, T1]. Let t1(R2) and t1(R3) denote R2 and R3’s random wait-times, respectively. Let t1(R2) < t1(R3), then R2 will transmit ACK back to T before R3. R3 will overhear R2’s ACK and cancel transmission of its own ACK. At any time, if an ACK packet is lost and not received by T, T will T)( retransmit D( although it may already have been received and ACK’ed). This 171 way the power consumed in nodes forming the gPMSS cluster to relay packets will be more evenly distributed. 8.4.3 Erroneous Reception by All Recipients This section describes the exchange of messages under the gPMSS protocol that occurs when all nodes that form a gPMSS cluster receive a transmission with errors. T) Figure 8.5c depicts this entire transaction. Here T sends a data message D( to R1 that is overheard by R2 and R3. Since all receivers R1, R2 and R3 receive with errors none of them is able to respond to T with an ACK within time T1. Let Run), Run) and 15023) denote the different versions of D(T) as they are received by R1, R2 and R3, respectively. Thus, there is no error—free copy of the transmitted message at any receiver. Nodes R1, R2 and R3 all wait for one another to respond to T with an ACK. When none of the receivers R1, R2 and R3 overhear an ACK going back to T within the T1 time of receiving, they infer that none of them (T) received D error-free. Instead of requesting a retransmission from T, R1 collects the error-prone versions of the D from cooperating receivers, acknowledging each one immediately as it receives them. R2 will transmit 15(R2), A(RZ), MR2), which denotes the concatenation of EU”), the LQI A(RQ) and RSSI {)(RQ) with which it was received from T, to R1 between [T1,T1 + T2] after it received 15022). Similarly, R3 will transmit [Di-R3), A(R3),p(R3) between [T1, T1 + T2] after it received 15023). Once R1 has received {15(R2), A(Rg), p(R2)} and {E(R3), A(R3), p(R3)} it executes one of the diversity combining algorithms described in the preceding section in an attempt to recover D(T). If the CRC computed from the recovered packet matches the appended CRC the attempt is successful. On the receiver side T waits for an ACK, any ACK from any of the receivers R1, R2 or R3, for a timeout period of TT until it attempts retransmission of DiT). Note that TT > T1 + T2. 172 / Host PC MICAz Mote Ethernet Gateway Receiver 1 MICAz Mote Ethernet Gateway Receiver 2 MICAz Mote I Channel 2x IEEE 802.15.4 Channel 26 (2.480 GHz) MICAz Mote Transmitter Ethernet Gateway Receiver 3 Figure 8.6: Equipment setup for trace collection. 8.5 Trace Based Proof of Concept In this section we provide proof of concept of gPMSS by testing its performance on bit error traces. We collected error traces of a few million packets in a way that provides, to the authors’ best knowledge, the BER a packet is subjected to and the LQI and RSSI with which it is received. 8.5.1 Experimental Setup The trace—collection setup is depicted in figure 8.6 and consists of a Crossbow MPR2400 MICAz mote [34] transmitter and another three MICA2 motes mounted on Crossbow MIB600 Ethernet gateways [33] as receivers. The three receivers R1, R2 and R3 are connected to a host personal computer (PC) running three instances of Xlisten (a data logging application), one for each receiver. This way a data collection session produces three traces. All traces were collected while operating in channel 26 in the 2.4800Hz band. The reason for choosing channel 26 was that it is least prone 173 Octets: 1 2 1 2 2 1 1 29 Frame Sq Best Best Data / Le” Control No PAN ID Addr TV” (3'9 Payload FCS 2 1 1 4 4 4 4 4 4 1 0x8 Src Dst SeqNo SeqNo SeqNo SeqNo SeqNo SeqNo 0x 401 Adr Adr (1) (2) (3) (4) (5) (6) 00 Figure 8.7: CC2420 MAC frame format used for experiments. to interference from any 802.11b / g frequency channels. Our own experience shows that selecting channel 26 does not completely eliminate interference from co-located 802.11b/g VVLANs, but reduces it significantly. Packet Payload TinyOS [75} is one of the most widely used Open source operating system in WSN devices. T inyOS vl.1 allows various packet formats to be transmitted. We suitably modified code to enable the standard 802.15.4 frame format which TinyOS v1.1 la- bels CC2420 Frame Format (after the Chipcon CC2420 chipset [120] used in MICAz devices). Strictly speaking, the term packet refers to the protocol data unit (PDU) exchanged between network layers of the transmitter and receiver while the term frame is used for PDU’S exchanged between MAC layers. However, since our analysis is restricted to the MAC layer there is little cause for confusion and we use these terms interchangeably to refer to MAC layer PDUS. The exact MAC frame format used is shown in figure 8.7. The size of the frame is 41 bytes and comprises of a 1 byte length field, 2 byte frame control field (FCF), 1 byte sequence number, 2 byte 174 destination PAN ID, 2 byte destination address, 1 byte type field, 1 byte group field, 29 bytes of data followed by a 2 byte frame check sequence (FCS) containing a CRC. The contents of the payload field are of our own choosing and consist of 3 unused bytes, the source address, the destination address and 6 cepies of a 32 bit sequence number. The sequence number in the payload is used to keep track of lost packets. If the sequence number between two consecutively received packets skips one or more numbers that is indicative of a packet loss. The sequence number field alone proves too small for this task in the face of long fades. Note that transmitted packets differ only in the 1 byte sequence number in the header and the six 32 bit sequence num- bers in the payload, and the CRC. For a particular trace all remaining bits remain unchanged. However, since the wireless channel will introduce bit errors the copies of the sequence number used to track packet losses in the received packet may differ. For this purpose we use a majority vote of the received sequence numbers to reconstruct the transmitted sequence number and from it the entire packet. Trace Generation Bit-level error traces can be generated by comparing a transmitted packet with its received version. A simple bit-wise XOR operation of the transmitted and received packets yields a. bit pattern in which a zero (’0’) signifies a bit that is received without error while a one (’1’) represents an inverted bit. We observe that in some cases the length of the received packet is shorter than the transmitted packets. This constitutes a partial loss and we use the term partially lost packets to refer to such packets. Partially erased packets are logged when bits in the MAC header’s length field are inverted and the receiver stops listening to the wireless channel prematurely. It has also been observed that if bits in the length field are inverted in such a way that the length of the incoming packet appears longer than actual the length of the logged packet still equals that of the transmission. Although the length field in the received 175 packet may falsely indicate a longer packet, the absence of a carrier signal allows the receiver to detect the end of transmission. 8.5.2 Channel State Information Each received packet’s logged entry is accompanied with three pieces of packet level CSI parameters. The first is the F CS status of the packet modeled by random variable (I) with the nth packet’s FCS status is represented by q§[rl.]. Ordinarily receivers only distinguish between two states, i.e. F CS Pass (denoted o = 0) if the CRC value in the FCS field matches the CRC of the received packet, and FCS Fail (denoted (lb aé 0) if it does not. Since we have knowledge of packet erasures and size of transmitted packets we extend the definition of F CS status to accommodate the reason for failure. We restrict the definition of FCS Fall BE (denoted o = 1) to mean that the size of a received packet matches the size of the transmitted packet and the CRC failure is due to bit errors (BE). Furthermore we classify a packet as being F CS Fail PL (denoted o = 2) and F CS Fail CL (denoted cf) 2 3), where PL and CL are abbreviations for partial loss and complete loss respectively. Packets that are partially lost cannot pass the CRC test and are marked FCS Fail PL. Packets that are not received at all, i.e. when the decoded sequence number at receiver skips, are marked FCS Fail CL. Among other CSI there are RSSI and LQI which we described in earlier sections. Completely lost packets, with db = 3, are assigned p = —128, /\ = 0, and £3 = 1. Thus each received packet is characterized by its FCS Status, LQI, RSSI and BER processes. 8.5.3 Implementation Results Due to shortage of space and due to the consistent similarities in results, we restrict our discussion to a subset of traces. This particular data. set was collected in an 176 +R2 . +R3 0.02 0.04 0.06 .08 0.1 0.12 0.14 B R-|3 Figure 8.8: PDF of BER experienced by receivers R1, R2 and R3 (pB(,3 = 0) is cropped out for better view of non-zero range. office environment over a period of 24 hours consisting of approximately 800,000 transmitted packets. The link between transmitter and receiver was non-line—of—sight, with a wall, a door and several furniture items in the direct line between them. The receivers were separated by a distance of 0.25m. The gPMSS cluster consisted of three receivers, also Crossbow MICAz motes mounted on MIB600 Ethernet gateways. Figure 8.8 is a cropped portion of the PDF of BERs observed in packets at gPMSS receivers R1, R2 and R3 that excludes ,8 = O for enhanced visibility. Figure 8.9 depicts the PDF of the LQI of all received packets at R1, R2 and R3. Figure 8.10 depicts the PDF of their RSSI. These three figures clearly show that. all three receivers experience different channel conditions. 177 40 W 60 80 100 LQI - 7t Figure 8.9: PDF of LQI experienced by receivers R1, R2 and R3. PER and PLR Analysis We define two quantities based on the FCS status, the packet error rate (PER) and the packet loss rate (PLR); # of reed packets "with. d) = 1,2 PER = # of transn'zxitted packets ’ (8.7) PLR _ # 0f rcvd packets with q) = 3 — # of transmitted packets ’ (8.8) The packet reception rate (PRR) as PRR 2 1 — (PER + PLR). In figure 8.11 the first three entries on the horizontal axis plot the PER, PLR and the sum of the two, PER+PLR, for R1, R2 and R3. For individual receivers PER+PLR happens to be 178 .0 0) .0 <11 .0 i? .0 N .0 —\ -95 _QRSSI - p(d§5m) '80 Figure 8.10: PDF of RSSI experienced by receivers R1, R2 and R3. approximately 7%, 17% and 12%. These figures are followed by plots of these same quantities for the three diversity combining techniques. The simplest technique, se— lection diversity, appears to track the PER+PLR of the best performing receiver, in this case R1. Equal gain and maximal ratio diversity combining both perform better than any individual receiver and selection diversity. This was to be expected. Recall that selection diversity merely tries to pick out the least corrupted version among a set, whereas equal gain and maximal ratio actually attempt to correct errors in re- ceived messages by un-weighted and weighted voting, respectively. This is adequately reflected in the plot of PER, PLR and PER+PLRS. Both are able to reduce the PER 179 7 0.2 ->-PER —o—PLR . g 7 +PER+PLR 4 0151 . . ..... . .. . ... 0.1- 911 R2 R3 Select Equ Gain Max-ratio Receiver ' Figure 8.11: PER, PLR and PER+PLR experienced by receivers R1, R2 and R3 without gPMSS diversity combining and with selection, equal gain, and maximal ratio diversity combining. BER Analysis In figure 8.12 we plot the histogram (not PDF) of packets with non-zero BER as experienced by individual receivers R1, R2 and R3 without any diversity combining, as well as with different diversity combining methods. Again, the trends exhibited by diversity combining methods are the same across all traces. Figure 8.12 shows that the histogram of the selection diversity combining closely matches that of the best receiving individual receiver, i.e. R1. The close match of the histogram of selection diversity with that of R1 shows it manages to bring a gPMSS’ BER performance up to that of the best receiving node. Thus, the BER model that is at the heart of this diversity combining technique delivers good performance. The result of equal 180 60,000 l r l l l r m ; .R1 ? .R2 T .SlMO-Selection Div. .5 .SIMO-Equal Gain Div. _ % 40’000 :4 F’SlMQ-Maximal Ratio Div. 0. 30.000 1 l..— o 4* 20,000 + ______ - 10,000 0.02 0.04 0.06 0.08 0. 0.12 0.14 BER Figure 8.12: Histogram of BERs observed by receivers R1, R2 and R3 without gPMSS diversity combining and with selection, equal gain, and maximal ratio diversity com— bining. gain and maximal gain diversity combining are even better. For every BER bin in the histogram, both equal gain and maximal—ratio combining are able to reduce the number of corrupt packets. Both are very close in their performance, but equal gain is consistently beating maximal-ratio combining across all BER bins in figure 8.12, and is also able to maintain this performance across different. trace sets. 8.6 gPMSS Protocol Implementation This section describes our implementation of the gPMSS protocol for motes and ana- lyzes its performance. For the mote platform, we selected the Crossbow’s Imote2 with the pre-installed .NET Micro Framework edition [35]. Using this edition of the Imote2 enabled us to implement gPMSS in the C# programming language which simplified 181 and accelerated development. At this point we would like to clarify that although the Imote2 used for the actual implementation in this section is different from the MICA2 we used for trace collection in section 8.5, both use the same Chipcon CC2420 radio transceiver [120] which makes them equivalent for the purpose at hand. As the description of the gPMSS protocol above showed, in a situation when a transmission is received correctly by at least one recipient, gPMSS implements selection diversity described in subsection 8.3.1. But when a transmission is received with errors by all receivers, gPMSS either implements the functionality of an equal gain diversity or maximal ratio diversity combiner. We have implemented both in C# for Imote2. The maximal ratio diversity combiner depends on the CSI-driven BER model by Ilyas and Radha [55]. Since the BER model takes as input an LQI, RSSI pair A, p we still need to map it. to a probability value. In the first instance we find the 90th percentile value of the BER’S predicted PDF, i.e. the BER for which the value of the cumulative distribution function (GDP) is 0.9. In the second instance we map PDFs of the BER to their corresponding 50th percentile. We analyze the performance of the gPMSS protocol in a setting with one transmitter and N = 3 receivers. The receivers run a complete implementation of the gPMSS protocol described in section 8.4. For the experiment the timeout constants were set to T1 = 10 sec, T2 = 12 sec and TT 2 30 see. We deliberately chose large values for T1, T2 and TT to avoid synchronization issues and justify them by the low—rate nature of target applications for IEEE 802.15.4. For the time being we have not attempted to optimize them to maximize throughput while still avoiding synchronization problems. The experiment was conducted at a residence with moderate W i-F i network interference. 182 8.7 Results and Analysis This section analyzes and compares PRR, energy per packet and effect of retransmis- sion limits on packet delivery rate with and without gPMSS. 8.7 .1 Packet Reception Rate We denote the total number of transmissions made from transmitter T by CT, and the number of retransmissions among them by CR. Similarly, the number of transmitted packets that are received at R1, R2 and R3 without errors are denoted by C1, C2 and C3, respectively. Finally, CS denotes the number of packets for which diversity combining was attempted and succeeded, and CF the number of packets for which it failed. All these values are tabulated in table 8.1. Each row in the table corresponds to a trial experiment using a variant of gPMSS specified in the first column. The results presented here are for three variants, i) Maximal-ratio combining using 690% for the BER point estimate, ii) Maximal-ratio combining using the 650% for the BER point estimate, and iii) equal gain combining. To make sense of the packet counts in table 8.1 and quantitatively assess the benefits of using only selection diversity, and using selection diversity in conjunction with maximal-ratio/ equal gain combining we look at PRRs, denoted by 8. Columns (1), (2) and (3) in table 8.2 contain the PRRs of the baseline configuration in which receivers R1, R2 and R3 do not cooperate. Column (4) contains the PRR when gPMSS is used with the diversity combination method in column (0). Some of the packets received using gPMSS will have been received as a result of selection diversity, while others will have been recovered as a result of diversity combining. The following columns separate the gain in PRR over that in the baseline configuration by providing the additive increase in PRRS of individual receivers. Columns (5), (6) and (7) are additive contributions of selection diversity in 9913111sz to the PRRs of individual receivers. Thus, AOSD,Rli AQSD,R2 and 183 Table 8.1: Packet counts. Diversity. combining CT CR C1 C2 C3 C3 CF Max-Ratio 590% 3170 855 937 893 957 597 0 Max-Ratio 050% 4167 1039 1254 1322 1198 739 0 Equal Gain 3683 879 819 844 825 497 0 A6 S D R3 are the increments in the PRR with respect to their respective baseline performances 6R1, 6R2 and 6R3 in non—cooperating mode. Finally, column (8) is the additive contribution of diversity combining ABDC to the PRR 691321155 of the system with gPMSS. Thus, since the PRR gains in columns (5), (6), (7) and (8) are all additive the relationship between the terms in table 8.2 is, 9913.11.93 = 9m + A95pm + Moe = 9R2 + A950,122 + MDC = 6R3 + A930,123 + MUC- 8.7 .2 Energy Per Packet In this section we compute separately the energy expended by the transmitter T as well as the receiver cluster R1, R2 and R3 per error free packet communicated to any one receiver. Let E D AT denote the energy spent to transmit a data packet, E AC K the energy spent to transmit an ACK packet and E AC K < E D AT' Then the energy ET spent by the transmitter T during the course of an experiment is CT x E D AT' The energy spent by receivers R1, R2 and R3 in acknowledging these are E131: C1 X EACK’ ER2 = C2 x EACK and ER3 = C3 x EACK' Note that although energy is consumed by motes in tasks other than radio transmissions, 184 Table 8.2: PRR of individual nodes without gPMSS, PRR with gPMSS protocol, PRR gain for individual receivers R1, R2 and R3 due to selection diversity, and the PRR gain due to diversity combining. (0) (1) (2) (3) (4) (5) (6) (7) (8) 6R1 932 933 69PMSS 4950121 A9513M 49,919,123 Moe Expl: 0.29 0.28 0.30 0.73 0.25 0.26 0.24 0.19 Max- Ratio 590% Exp2: 0.30 0.31 0.29 0.75 0.27 0.26 0.28 0.18 Max- Ratio 550% Exp3: 0.22 0.23 0.22 0.76 0.40 0.39 0.40 0.13 Equal Gain 0.0020 — ArszogPMSS Rx: NogPMSS VTXI Select Div A A} Rx: Select Div “4 Brx:gpl\/lss a szgPMSS at 0.0010 v Q \ *— s V V :2 [a B o _ Exp1zMax—Ratio (90%) Exp’2:Max-.Ratio (510%) Experlment # Exp3quu Gain Figure 8.13: The energy in nJ consumed by transmitter and receivers per successfully delivered packet. 185 Table 8.3: Energy consumed by transmissions at transmitter and receiver side per error-free received packet. Columns (1) and (2) correspond to the baseline scenario using only retransmissions. Columns (3) and (4) correspond to the case when only selection diversity is used by receivers. Columns (5) and (6) corresponds to the case where a full implementation of gPMSS is used that employs diversity combining (equal gain or maximal-ratio) in addition with selection diversity. (0) (1) (2) (3) (4) (5) (6) DlV PT PR PT PR PT PR comb Expl 3'383EDAT EACK 1.845EDAT EACK 1'369EDAT 1'516EACK Max— + Ratio 0.516EDAT 390% Exp2 3'323EDAT EACK 1.744EDAT EACK 1.332EDAT 1'473EACK Max- + Ratio 0.473EDAT 350% Exp3 4.497EDAT EACK 1'596EDAT EACK 1.314EDAT 1'355EACK Equal + Gain 0.355EDAT the power consumed by computations is orders of magnitude less. Since the gPMSS protocol has computational complexity of 0(N). We compute the energy per packet consumed at the transmitter PT and the sum of energy consumed by all receivers together PR as, ET PT = # of packets 7‘ ER ecvd wo errors ’ P = . R # of packets recvd wo errors (8.10) (8.11) Thus, PT and PR are energy consumption rates of transmitter and receivers obtained by normalizing by number of successfully delivered packets. Table 8.3 lists PT, the per 186 decodable packet energy at the transmitter, and PR, the per decodable packet energy at all receivers combined for all three experiments (listed in column (0)). Columns (1) and (2) in table 8.3 correspond to the baseline case when gPMSS is not used and packets received by R1 are retransmitted. Columns (3) and (4) correspond to the case when only selection diversity is used by cooperating receivers. Columns (5) and (6) corresponds to the case where a full implementation of gPMSS is used that employs diversity combination (equal gain or maximal-ratio) in addition to selection diversity. To keep the relationship general the tabulated values are in terms of E AC K and EDAT- The Intel Imote2 consumes 79272.] / b when in transmit / receive mode when it op- erates at 13.MH2 [35]. Based on this figure EDAT for a 41 byte frame is 260/1J and E AC K for a 5 byte acknowledgement frame is 32/lJ. Figure 8.13 plots PT and PR (in Joules) expended in experiments 1, 2 and 3 when when maximal-ratio combining with 590%, maximal-ratio combining with 050% and equal gain combining. As in table 8.3 we also evaluate energy for the cases if no gPMSS and if only selection di- versity were used. Black lines correspond to energy consumption of the transmitter, while blue lines correspond to energy consumption of the receivers. Clearly, the trans— mitter power consumption rate PT and receiver power consumption rates do not vary significantly across experiments and gPMSS variants. However, there is significant variation in PT and PR when gPMSS is not used versus selection diversity versus gPMSS. For all three experiments PT is highest when gPMSS is not used while the corresponding receiver power consumption rate PR is lowest. Opting to use selection diversity alone significantly reduces PT for maximal ratio gain variants (Exp 1 and 2) by about 42% and about 64% for equal gain variant (Exp 3). PR remains unchanged. Note from the previous section that this is accompanied by a 25% (for Exp 1 and 2) and 40% (for Exp 3) increase in PRR. Thus selection diversity is able to provide significant power savings while increasing PRR at the same time. V’V hen gPMSS is 187 20 ............ ............ : ............ h [ +Exp1: w/o gPMSS § + Exp1: Max—Ratio [390% 5 :l 15_ + Exp2- W/O gPMSS .......... ........... 1’ + Epo: Max-Ratio B i Exp3: w/o gPMSS ; E 10 Exp3: Equal Gain """""" " ' 50% 0 20 40 60 80 100 9 (043) Figure 8.14: Maximum number of transmission attempts m versus delivery guarantee g(%)- employed PT is reduced by about 58% (for Exp 1 and 2) and 68% (for Exp 3) over the baseline configuration not using gPMSS. However, this is accompanied by an increase of approximately the same amount of energy on the receiver side. Thus, it appears that gPMSS shifts some of the power consumption from the transmitter side to the receiver side. 8.7.3 Packet Transmission Attempts The number of times the IEEE 802.15.4 MAC will retry transmitting a packet is controlled by the marMarFrameRetries attribute whose default value is set to 3 but can be varied from 0 — 7 (refer to IEEE 802.15.4 standard [5]). This limit on the 188 number of transmission attempts m for a packet limits the maximum PRR that can be guaranteed to 9. Conversely, we may ask what is maximum number of transmission attempts m that the MAC must be allowed in order to ensure that at least 9% of packets are received without errors? Figure 8.14 plots m against 9 for all three experiments. Clearly, to achieve any delivery guarantee 9%, fewer transmissions are required with gPMSS, regardless of whether maximal-ratio or equal gain diversity combination is used, compared to the case where gPMSS is not enabled. For example, figure 8.14 shows that to achieve a 95% delivery guarantee we have to allow 9, 9, 13 transmission attempts for the channel conditions observed in experiments 1, 2 and 3. Using gPMSS, however, the maximum number of transmission attempts required to achieve the same delivery guarantee 9 = 95% are 3, 3, and 3, respectively. Clearly, the values of 777. required to achieve 9 = 95% without gPMSS exceeds IEEE 802.15.4’s lap-abilities. From the plot in figure 8.14 we see that at IEEE 802.15.4’s default value of m = 4 the maximum achievable delivery guarantee for the three experiments lies in the range 65 — 75%. 8.8 Conclusions We presented the gPMSS, a protocol-centric approach to enable receiver cooperation and diversity combining without requiring any changes to mote hardware or the IEEE 802.15.4 LR—WPAN standard. We described three principal mechanisms enabled by gPMSS, namely selection diversity, equal gain and maximal-ratio gain diversity corn- bining. We provide proof—of-concept and demonstrate gPMSS’ efficacy by applying these diversity combining techniques on bit error traces collected from a network of IEEE 802.15.4 motes. we demonstrate gPMSS by implementing it on the Intel Imote2 sensor mote running the .NET i\-"licro framework. We analyze the performance of gPMSS in terms of PRR, retransmission attempts and power consumption per de— 189 livered packet. We saw that gPMSS raises the PRR from 22 — 30% to 73 — 76%, a relative increase of 150 — 245%. Since gPMSS is a protocol-based solution it implies a messaging overhead. we observe that power consumption by the transmitter per correctly delivered packet. is reduced up to 68%. We evaluated the effect of retry limit imposed by the IEEE 802.15.4 standard of the on the packet delivery rate that can be achieved. At the default retry limit of 3, (m =2 4) gPMSS can achieve delivery rates of greater than 99%, against only 65 -— 75% when gPMSS is not used. Thus we demonstrate that gPMSS is capable of raising PRR, making use of highly lossy links feasible, thus reducing the number of required retransmission attempts and re- ducing the energy consumption rate of the transmitter per packet delivered. gPMSS has direct application in the design of small-world topologies in wireless networks to reduce the characteristic path length and diameter of networks which facilitates service discovery and the routing of high priority data in a network. This has the advantage of not needing any additional hardware([124] and [125]), or adding wired conuections([27] and [111]). The extension of the effective communication range also has applications in extending the lifetime of nodes surrounding the base station in wireless sensor networks subject to the funneling effect. The larger communication range allows more nodes to communicate with the base station directly and reduces the traffic load from nodes positioned closer to the base station. More generally, gPMSS can be used to connect weakly connected components of a network by adding more links between nodes farther apart. 190 Chapter 9 Principal Component Centrality as a Measure of Node Centrality in Communication Networks 191 9. 1 Introduction Centrality [14], [15], [17], [42], [106] is a measure to assess the criticality of a node’s position. Node centrality as a measure of a node’s importance by virtue of its central location has been in common use by social scientists in the study of social networks for decades. Over the years several different meanings of centrality have emerged. Naturally, the idea of ranking nodes for their ability to spread or detect (positive or negative) influence is of significant interest to social network analysis. Among many centrality measures, eigenvalue centrality (EVC) is arguably the most successful tool for detecting the most influential node(s) within a social graph. Thus, EVC has been a highly popular centrality measure in the social sciences ([45], [126], [14], [41], [38], [40], [127], [121], [16], [15]) (it is often referred to simply as centrality). As we demonstrate later in this chapter, one key shortcoming of EVC is its focus on (virtually) a single influential set of nodes that tend to cluster within a single neighborhood. In other words, EVC has the tendency of identifying a set of influential nodes that are all within the same region of a graph. This shortcoming may not represent a major issue for many social science problems and Internet appli- cations, such as PageRank, where EVC has been used extensively [72]. Meanwhile, when dealing with massive networks/ graphs, it is hardly the case that there is a sin- gle neighborhood of influential nodes; rather, there are usually multiple infiucultial neighborhoods most of which are not detected or identified by EV C. In order to identify influential neighborhoods, there is a need to associate such neighborhoods with some form of an objective measure of centrality that can be evaluated and searched for. To that end, one can think of a centrality plane that is overlaid over the underlying graph under consideration. This centrality plane may contain multiple centrality score maxima, each of which is centered on an influential neighborhood. 192 Local Centrality («~— Maximas Centrality Figure 9.1: This figure shows a graph on the lower plane, overlayed with another plane of the interpolated surface plot of node centrality scores. The centrality planes typically exhibit a number of peaks or local maxima. Nodes that have centrality score higher than other nodes are located under a centrality peak and are more central than any of their neighbors. We use the term hubs to refer to nodes forming centrality maxima. Figure 9.1 illustrates this concept. Thus, these hubs form the kernel of influential neighborhoods in networks. Hence, our focus in this research is on identifying influential neighborhoods rather than influential nodes. We will show that EVC has a tendency to be too narrowly focused on a dominating neighborhood. To this end, we introduce a new measure of centrality that we call principal component centrality (PCC) that gradually widens the focus of EVC in a controlled manner. More importantly, PCC provides a general framework for transforming graphs into a spectral space analogous to popular signal transforms that operate on random signals. In this chapter, we give a brief review of common centrality measures accom- 193 panied by a critique of their application to wireless network topologies. we then introduce PCC, a node centrality measure that is inspired by the Karhunen Loeve transform (KLT) and principal component analysis (PCA). In essence, PCC is a gen— eral transform of graphs that can provide vital insight into the centrality and related characteristics of such graphs. Similar to the KLT of a signal, the proposed PCC of a graph gives a form of cou‘lrmct representation that identifies influential nodes and more importantly influential neighborhoods. Hence, PCC provides an elegant graph transform framework that outperforms EVC. In particular, early in this chapter, we demonstrate EVCs shortcoming by using both EVC and PCC to compute node cen- tralities in a network small enough to allow meaningful illustration. This is followed by a thorough description of PCC, and its utility in transforming massive real-world networks / graphs. we also develop the equivalence of an inverse PCC transform that attempts to reconstruct a reprlrseutation of the original graph from its influential neighborhoods. The rest of this chapter is organized as follows. Section 9.2 gives a background review of existing centrality measures for graphs, highlights problems in EVC and motivates our development of a new node centrality. Section 9.3 defines the PCC measure of centrality. Section 9.4 describes in detail the advantages, mathematical interpretation, visualization and the effect of varying number of features of PCC. Section 9.5 concludes the chapter. 9.2 Background Let A denote the adjacency matrix of a graph G (V, E) consisting of the set of nodes V =_— (01,122,223, . . . ,vN} of size N and set of undirected edges E. When a link is present between two nodes u- and vj both A27 j and A j,’i are set equal to 1 and set to l 0 otherwise. Let F (0,) denote the neighborhood of vi, the set of nodes vi is connected 194 to directly. 9.2.1 Degree Centrality The degree centrality of a node in a graph is a measure of the relative importance to the graph’s connectivity. The degree centrality of a node is defined as the number of edges incident on it. Nodes with more incident edges have higher degree centrality than nodes with fewer incident edges. If di denotes the degree of node u,- then its degree centrality is computed by: N “‘1 (9.1) Degree centrality is a measure of a node’s rate of dissemination (of an infection) in the immediate short term. It has the advantage that its computation does not require nodes to exchange information. However, it has two significant disadvantages; 1. Without an exchange of centrality information with other nodes, it is not pos- sible to interpret and evaluate an individual node’s centrality relative to that of others. 2. Degree centrality does not take into account the centrality of its neighbors. 9.2.2 Closeness Centrality The closeness centrality of a node is defined as the mean length of geodesic paths to all other nodes. Intuitively, nodes occupying a more central location within the graph are expected to have shorter paths. Closeness centrality is a measure of the rate at which a node can spread an infection to all reachable nodes. Closeness is a suitable measure of centrality when the flow of commodity in the network follows 195 geodesic paths. Closeness centrality is a good measure of the average detection time in a network with flows of non-replicating commodity following geodesic paths. 9.2.3 Betweenness Centrality The betweenness centrality of a. node is defined as the fraction of geodesic paths (shortest paths) out of all geodesic paths between all pairs of nodes passing through that node. Thus, nodes located on more geodesic paths have a higher betweenness centrality than nodes located on fewer geodesic paths. Intuitively, since the subprob- leln optimality principal holds for the shortest path problem, a node’s location on a geodesic path implies close proximity to all other nodes on that path. A node’s betweenness can be interpreted as a measure of disruption caused when the node is removed from the network. Like closeness, betweenness too assumes that the flow of commodity is along geodesics. Betweenness centrality is a good measure of the av- erage probability of detection of flows in a network with non-replicating commodity following geodesic paths. 9.2.4 Eigenvector Centrality Eigenvector centrality (EVC) is a relative score recursively defined as a function of the number and strength of connections to its neighbors and as well as those neighbors’ centralities. Let 17(1) be the EVC score of a node vi. Then, :I:(i)=;’\- Z we) J'EFW) 1 N j=1 196 Figure 9.2: A spatial graph of 200 nodes. Node colors are indicative of the range in which their EVC falls. Here A is a constant. Equation 9.2 can be rewritten in vector form equation 9.3 where x = {x(1),:1:(2), z(3), . . . ,$(N)}’ is the vector of EVC scores of all nodes. x = §Ax Ax = Ax (9-3) This is the well known eigenvector equation where this centrality takes its name from. A is an eigenvalue and x is the corresponding eigenvector of matrix A. Obvi- ously several eigenvalue/eigenvector pairs exist for an adjacency matrix A. The EVC of nodes are defined on the basis of the Perron eigenvalue A A (the Perron eigenvalue 197 is the largest of all eigenvalues of A and is also called the principal eigenvalue). If A is any other eigenvalue of A then AA > |A|. The eigenvector x = {20(1), 33(2), . . . ,11:(N)}’ corresponding to the Perron eigenvalue is the Perron eigenvector or principal eigen- vector. Thus the EVC of a node 1), is the corresponding element 2(1) of the Perron eigenvector x. Note that when the adjacency matrix A is symmetric all elements of the principal eigenvector x are positive. As mentioned above, EVC is widely used in the social sciences ( [82], [127], [14], [42], [40], [41], [128], [126], [16], [15]) and is often referred to simply as centrality. EVC does not suffer from the same problems as degree, closeness and betweenness centralities. In computing a node’s EVC it takes into consideration its neighbors’s EVC scores. Because of its recursive definition, EVC is suited to measure nodes’ power to influence other nodes in the network both directly and indirectly through its neighbors. Connections to neighbors that are in turn well connected themselves are rated higher than connections to neighbors that are weakly connected. Like close- ness and betweenness, the EVC of a node provides a network-wide perspective. At the same time it can take advantage of distributed methods of computing eigenvec- tors / eigenvalues of a matrix but does not have to bear the overhead of excess network traffic. Sankaralingam [108], Kohlschiitter [69] and Canright, EngQi-Monsen and Je— lasity [20], Bischof [12], Bai [8] and Tisseur [121] proposed some parallel algorithms for computing eigenvectors and eigenvalues of adjacency matrices. 9.2.5 The Need for a New Centrality Measure In the preceding sections we highlighted some of the key characteristics of the most common measures of centrality. Our discussion left us with only one viable measure of centrality that takes into consideration the centrality scores of a node’s neighbors and which provides a network-wide perspective, i.e. EVC. EVC has been used extensively 198 to great effect in the study and analysis of a wide variety of networks that are shown to exhibit small-world and scale-free properties. In [21] Canright and Engo-Monsen correlated EVC with the instantaneous rate of spread of contagion on a Gnutella network peer-to-peer graph, a social network of students in Oslo, a collaboration graph of researchers at Telenor R&D and a snapshot of a collaboration graph of the Santa Fe Institute. In [90] Newman analyzed the use of EVC in a lexical network of co-occuring words in Reuters newswire stories. In [22] Carreras et al. used EVC to study the spread of epidemics in mobile networks. They used three sets of traces collected by Intel Cambridge, a trace of the public transportation network from the DieselNet project at the University of h-lassachusetts at Amherst and mobility and interaction traces from MIT’s Reality Mining project. Now consider the graph in figure 9.2. It consists of 200 nodes and is typical of networks of stationary WSN as well as mobile \VSNS such as the cellphone based Nokia SensorPlanet project ([95], [62]). Its nodes are assigned one of six colors from the adjacent color palette. Each of the six colors represents one of six bins of a histogram spanning, in uniform step sizes, the range from the smallest to the largest EVCs. As the legend accompanying figure 9.2 shows, blue represents the lowest EVCs and red the highest. We make the following observations: 1. EVCs are tightly clustered around a very small region with respect to the total size of the network and drops off sharply as one moves away from the node of peak EV C. 2. EV C is unable to provide much centrality information for the vast majority of nodes in the network. 3. The position of the peak EVC node appears somewhat ‘arbitrary’ because a visual inspection shows that almost equally significant clusters of nodes can be 199 a 50 z .............................. _Adjacency Matrix C [:J Laplacian Matrix 3 a) 40 _ ---------------------- Averaged — Adjacency Matrix 3' 8. 3 - - - Averaged — Laplacian Matrix : a) 20 .................. ‘ ......... ‘ ........ ‘. ........ ‘ .......... L _' ' LI. : E 0 . -1O -5 0 5 10 15 20 25 30 A. l i_ 1 ....................................................... ‘_ z a N . . ‘. I \ 0.5 ............. , ‘. i P ...... — Adjacency Matrix ___ ‘ I l I Laplacian Matrix S fi 3 Averaged - Adjacency Matrix 3 ‘- : - - - Averaged — Laplacian Matrix 0- _u 0 i l 1 i N 0 50 100 150 200 P Figure 9.3: [Top] Histogram of eigenvalues of adjacency matrix and Laplacian matrix A of network in figure 9.2; [Bottom] Cumulative sum of the sequence of eigenvalues of adjacency matrix and Laplacian matrix of network in figure 9.2 when sorted in descending order of magnitudes. In both figures the lines plotted in red color are averages of 50 networks generated randomly with the same parameters. visually spotted in other locations in the graph. Counter to intuition, the high EVC cluster is connected to the rest of the network by a single link. 9.3 Principal Component Centrality The EVC of a node is recursively defined as a measure of centrality that is proportional to the number of neighbors of a node and their respective EVCs. As we saw in section 9.2.4, the mathematical expression for the vector of node EVCs is equivalent to the principal eigenvector. Our motivation for PCC as a new measure of node centrality 200 Figure 9.4: Reconstructed topologies of the graph from figure 9.2 using only the first 1, 2, 3, 5, 10, 15, 50 and all 200 eigenvectors. may be understood by looking at EVC through the lens of the KLT. When the KLT is derived from an N x N covariance matrix of N random variables, the principal eigenvector is the most dominant feature vector, i.e. the direction in N -dimensional hyperspace along which the spread of data points is maximized. Similarly, the second eigenvector (corresponding to the second largest eigenvalue) is representative of the second most significant feature of the data set. It may also be thought of as the most significant feature after the data points are collapsed along the direction of the principal eigenvector. When the covariance matrix is computed empirically from a set of data points, the eigendecomposition is the well known PCA [38]. Since we are operating on the adjacency matrix derived from graph data we call the node centrality proposed in this research PCC. In a covariance matrix, a non-zero entry with a ’large’ magnitude at positions (2',j) and (3,1) is representative of a strong relationship between the i-th and j-th random variables. A non—zero entry in the 201 adjacency matrix representing a link from one node to another is, in a broad sense, also an indication of a ’relationship’ between the two nodes. Based on this understanding we draw an analogy between graph adjacency matrix and covariance matrix. In the preceding section we described various centrality measures from litera- ture. Among them, EVC is the node centrality most often used in the study of social networks and other networks with small-world properties. While EVC as- signs centrality to nodes according to the strength of the most dominant feature of the data set, PCC takes into consideration additional, subsequent features. We de- fine the PCC of a node in a graph as the Euclidean distance/t2 norm of a node from the origin in the P-dimensional eigenspace formed by the P most significant eigenvectors. For a graph consisting of a single connected component, the N eigen- values MN 2 [Agl _>_ _>_ |AN| = 0 correspond to the normalized eigenvectors x1,x2, . . . ,xN. The eigenvector/ eigenvalue pairs are indexed in order of descending magnitude of eigenvalues. When P = 1, PCC equals a scaled version of EVC. Unlike other measures of centrality, the parameter P in PCC can be used as a tuning pa- rameter to adjust the number of eigenvectors included in the PCC. The question of selection of an appropriate value of P will be addressed in subsequent subsection 9.4.4. Let X denote the N x N matrix of concatenated eigenvectors X = [x1x2 . ..xN] and let A = [A1A2 . . . A N], be the vector of eigenvalues. Furthermore, if P < N and if matrix X has dimensions N x N, then X Nx p will denote the submatrix of X consisting of the first N rows and first P columns. Then PCC can be expressed in matrix form as: cp = \/((AXNXP) 9 (*A‘XNxP))11”><1 (9.4) The ‘G’ operator is the Hadamard (or entrywise product or Schur product) op- 202 erator. Equation 9.4 can also be written in terms of the eigenvalue and eigenvector matrices A and X, of the adjacency matrix A: CP 2 l/(XNxP @XNxP) (APX1GAPXIA (9-5) It is important to note a major difference between a traditional ”signal transform” under KLT as compared with the proposed PCC ”graph transform”. First, recall that, under KLT, a transform matrix T is derived from a covariance matrix C; and then the eigenvector-based transform T is applied on any realization of the random signal that has covariance C. Meanwhile, under the proposed PCC, the adjacency matrix A plays a dual role: at one hand, it plays the role of the covariance matrix of the KLT; and on the other hand, one can think of A as being the ”signal” that is represented compactly by the PCC vector C p. Effectively, the adjacency matrix A represents the graph (i.e., ”signal”) that we are interested in analyzing; and at the same time A is used to derive the eigendecomposition; and hence, we have the dual role for A. Later, we will develop the equivalence of an inverse PCC, and we will see this dual role of the adjacency matrix A again. 9.4 Evaluation 9.4.1 Interpretation of Eigenvalues The definition of FCC is based on the graph adjacency matrix A. For a matrix A of size N x N its eigenvectors x,- for 1 S i g N are interpreted as N-dimensional features (feature vectors) of the set of N —dimensional data points represented by their covariance (adjacency) matrix A. The magnitude of an eigenvalue corresponding to an eigenvector provides a measure of the importance and prominence of the feature 203 represented by it. The eigenvalue A, is the power of the corresponding feature x,- in A. An alternative representation of a graph’s topology is the graph Laplacian matrix which is frequently used in spectral graph theory [28]. The graph Laplacian can be obtained from the adjacency matrix by setting the diagonal entries of the adjacency matrix to AM 2 — Z§v=1n7éj Am, i.e. a diagonal entry in a Laplacian matrix is the negative of the sum of all off-diagonal entries in the same row in the adjacency matrix. This definition applies equally to weighted and unweighted graphs. The graph Laplacian is always positive-semidefinite which means all of its eigenvalues are non- negative with, at least one eigenvalue equal to 0. The adjacency matrix, however, does not guarantee positive semidefiniteness and typically has several negative eigenvalues. This is the reason the ordering of features is based on magnitudes of eigenvalues. The bar chart at the top of figure 9.3 plots histograms of eigenvalues for both adjacency and Laplacian matrices of the network in figure 9.2. But why then, did we not use the Laplacian matrix in the first place? The reason is that the eigendecomposition of the adjacency matrix yields greater energy compaction than that of the Laplacian. The middle plot in figure 9.3 shows the normalized, cumulative function of the sorted sequence of eigenvalue powers. The line for the eigenvalue derived from the adjacency matrix rises faster than that of the Laplacian matrix. The adjacency matrix’ curve indicates that 25%, 50% and 75% of total power is captured by the first 15 (7.5%), 44 (22%) and 89 (44.5%) features, respectively. In contrast, the Laplacian matrix’ eigendecomposition shows that the same power levels are contained in its first 26 (13%), 61 (30.5%) and 103 (51.5%) features, respectively. Thus eigendecomposition of the adjacency matrix of graphs offers more energy compaction, i.e. a set of features of the adjacency matrix captures more energy than the same number of features of the corresponding Laplacian matrix. 204 C15 - 3D Spectral Drawing 0 high I 0 low -3 2 x, 01 ° x2e Figure 9.5: Spectral drawing of graph in three dimensions using entries of x1, x2, and X3 for the three coordinate axes. Nodes are colored according to their C15 PCC. 9.4.2 Interpretation of Eigenvectors EVC interprets the elements of the Perron-eigenvector XI of adjacency matrix A as measures of corresponding nodes’ centralities in the network topology (see section 9.2.4). Research on scale-free network topologies has demonstrated EVC’s useful— ness. However, when applied to large spatial graphs of uniformly, randomly deployed nodes such as the one in figure 9.2, EVC fails to assign significant scores to a large fraction of nodes. For a broader understanding that encompasses all eigenvectors we revert to the interpretation of eigenvectors as features. One way of understanding PCC is in terms of PCA [38], where PCC takes part of its name from. PCA finds the eigenvectors x1,x2, X3, . . . ,x N and eigenvalues of G’s adjacency matrix A. Ev- ery eigenvector represents a feature of the adjacency matrix. To understand how these feature vectors are to be interpreted in graphical terms, refer to equation 9.6 205 which uses eigenvectors and eigenvalues to reconstruct an approximation A P of the adjacency matrix A. Reconstruction can be performed to varying degrees of accu- racy depending on P, the number of features/ eigenvectors used. If we set P = N in equation 9.6 (all eigenvectors/ eigenvalues are used), the adjacency matrix can be reconstructed without losses (see He [45]). Here, A denotes the diagonal matrix of eigenvalues sorted in descending order of magnitude on the diagonal (from upper left corner to lower right corner). ~ A T AP = XNXPAPXNXNXN A1 0 0 A 0 A2 0 where A = 0 0 - - - A N To illustrate, consider the unweighted, undirected graph G' (V, E) shown in figure 9.2 with adjacency matrix A. A’s entries are either 0 or 1. However, this is not necessarily true for A p, the version of the matrix reconstructed using the P most significant eigenvectors. The entries in A P will very likely contain a lot of fractions. Therefore, before viewing the recovered topology in the reconstructed adjacency ma- trix A P its entries have to be thresholded. Prior to plotting the topology, we rounded values less than 0.5 down to 0 and round values larger than or equal to 0.5 up to 1. Figure 9.4 plots the adjacency matrix reconstructed from the most significant 1, 2, 3, 5, 10, 15, 50 and all 200 feature vectors. The plot for A1 shows that the recov- ered topology information is highly localized to the vicinity of nodes with the highest EVC. The plot using A2 adds another highly connected but still very localized cluster to the network. Adding more feature vectors extends the set of connected nodes in 206 200 150 150 g $100 3100 g 9 9 50 O 0 2 4 0 0 2 4 0,0) 020) (a) (b) Figure 9.6: PCC of nodes in network of figure 9.2 when computed using first (a) 1 and (b) 2 eigenvectors. The histograms accompanying each graph plot show the dis- tribution of PCC of their nodes. The lineplot in the histogram represents the average PCC histograms of 50 randomly generated networks with the same parameters as the network in figure 9.2. various parts of the network. As more eigenvectors are added to the computation of PCC it has the effect of increasing the resolution of centrality scores in nodes lying in less well connected regions of the network. 207 100 a a s s a s 50 e 2 LL LL. 2 _ 4 O0 2 . 03o 050) (a) (b) Figure 9.7: PCC of nodes in network of figure 9.2 when computed using first (a) 3 and (b) 5 eigenvectors. The histograms accompanying each graph plot show the dis- tribution of PCC of their nodes. The lineplot in the histogram represents the average PCC histograms of 50 randomly generated networks with the same parameters as the network in figure 9.2. 9.4.3 Graphical Interpretation of PCC In this section we evaluate the usefulness of the PCC scores assigned to nodes of a network. Recall that a node’s PCC is its 62 norm in P—dimensional eigenspace. Perceptional limitations restrict us from redrawing the graph in any eigenspace with 208 30‘ “Z" «2‘ 20 x h |_ 10» “- 10» LL 0 2 n 0 2 - C100) C150) (a) (b) Figure 9.8: PCC of nodes in network of figure 9.2 when computed using first (a) 10 and (b) 15 eigenvectors. The histograms accompanying each graph plot Show the dis— tribution of PCC of their nodes. The lineplot in the histogram represents the average PCC histograms of 50 randomly generated networks with the same parameters as the network in figure 9.2. more than 3 dimensions. Figure 9.5 is a drawing of the graph in figure 9.2 in the 3- dimensional eigenspace formed by the 3 most significant eigenvectors of the adjacency matrix A. Nodes are colored according to their C15 PCC scores, derived from the 15 most significant eigenvectors, divided into 6 equally sized intervals between the lowest 209 A O A 0 Frequency Frequency N C? N 9 2 . 0500) (a) (b) Figure 9.9: PCC of nodes in network of figure 9.2 when computed using first (a) 50 and (b) all 200 eigenvectors. The histograms accompanying each graph plot show the distribution of PCC of their nodes. and highest PCC score. Based on the interpretation of PCC we expect nodes with higher (red) PCC scores to be located farther away from the origin at (0,0,0) than nodes with lower (blue) PCC scores. From figure 9.5 we can see that this is clearly the case. For clarification, the cluster of low-PCC nodes around the origin (0,0,0) is marked with a red, dashed oval. 210 9.4.4 Effect of Number of Features on PCC In this section we study the effect varying the number of eigenvectors P has on PCC. For an illustrated example we revert to the randomly generated network topology of 200 nodes in figure 9.2. We compute PCC while varying P from 1 through 2, 3, 5, 10, 15, 50 and 200. Figures 9.6a, 9.6b, 9.7a, 9.7b, 9.8a, 9.8b, 9.9a and 9.9b re-plot the network with nodes colored to indicate their PCC scores. The bin size for all histograms is set to 0.25. Recall that since PCC score at P = 1 are a scaled versions of EVC, the figure 9.6a. represents the baseline case of EVC. In figure 9.6a, EVC identifies a small cluster in the upper right corner as the nodes most central to the network. Note that ironically this cluster is separable from the larger graph by the removal of merely one link! On the other hand, clusters of nodes in the larger, better connected part of the graph are assigned EVC on the low end of the scale. As P is increased from figure 9.6b through 9.9b, more clusters of high PCC nodes pop up. As expected, the accompanying histograms below each graph plot show that this has the effect of increasing the variance of FCC scores. Adding successively more features/eigenvectors will have the obvious effect of increasing the sum total of node PCC scores, i.e. llxNCm > llxNCn when m > n. However, it is unclear how much PCC’S scores change as P is varied from 1 through N. In [20] Canright et al. use the phase difference between eigenvectors computed in successive iterations as a stepping criteria for their fully distributed method for computing the principal eigenvector. we use the phase angle between PCC vectors and EVC to study the effect of adding more features. We compute the phase angle 95(71) of a PCC vector using it features with the EVC vector as, C C «6(P) = arccos ( P - E ) . ICPI ICEI 211 O 50 100 150 200 P - # of eigenvectors Figure 9.10: Plot of phase angles g6 (in radians) of PCC vectors with the EVC vector for the graph in figures 9.6, 9.7, 9.8 and 9.9. Here, ‘9 denotes the inner product operator. The relationship of the phase angle with the number of features used in PCC for the network under consideration is plotted in figure 9.10. Initially, the function of phase angle (25 rises sharply and then levels off almost completely at 22 features. This means that, in this example, the relative PCCS of nodes cease to change with the addition of more features beyond the first 22 features. The phase angle plot may be used for determining how many features are sufficient for the computation of FCC of a network. 9.5 Conclusions We reviewed previously defined measures of centrality and pointed out their short- comings in general and EVC in particular. We introduced PCC, a new measure of node centrality. PCC is based on PCA and the KLT which takes the View of treating a graphs adjacency matrix as a covariance matrix. PCC interprets a node’s centrality as its 62 norm from the origin in the eigenspace formed by the P most significant feature vectors (eigenvectors) of the adjacency matrix. Unlike EVC, PCC allows the addition 212 of more features for the computation of node centralities. We explore two criteria for the selection of the number of features to use for PCC; a) The relative contribution of each feature’s power (eigenvalue) to the total power of adjacency matrix and b) Incremental changes in the phase angle of the PCC with P features and the EVC as P is increased. We also provide a visual interpretation of significant eigenvectors of an adjacency matrix. The use of the adjacency matrix is compared with that of the Laplacian and it is shown that eigendecomposition of the adjacency matrix yields significantly higher degree of energy compaction than does the Laplacian at the same number of features. We also investigated the effect of adding successive eigenvectors and the information they contain by looking at reconstructions of the original graph’s topology using a subset of features. In the future we intend to extend the definition of PCC so it can be applied to both directed and undirected graphs. Furthermore, we propose to formulate a distributed method for computing PCC along the lines of Canright’s method [20] for computing EVC in peer-to-peer systems. 213 Chapter 10 Conclusions 214 The following three sections list conclusions we learnt from the results of our research. 10. 1 Channel Modeling Our analysis and modeling of errors observed in IEEE 802.15.4 traces in chapters 3 and 4 leads us to make the following conclusions. 1. LQI and RSSI exhibit moderate negative correlation with the BER process (and strong positive correlation with each other). 2. LQI and RSSI can be used to reduce the variance of BER’s estimated PDF of packets failing the CRC. 3. The CSI driven BER model remains valid across a variety of physical environ- ments. 4. All IEEE 802.15.4 channels, regardless of channel selection or physical environ- ment, exhibit a memory length of at most 2 bits and 2 symbols, respectively. 5. Based on the correlation function and analysis for LRD we conclude that various estimates of Hurst parameter may or may not detect packet level memory in 802.15.4 channels. The memory, however, is not due to the channel’s inherent properties at those frequencies, but due to interference from IEEE 802.11b/ g traffic and beacon frames, i.e. if interference is periodic the channel appears to have memory, if it is not periodic there is no memory. 6. The Abry-Veitch and Whittle estimators’ consistent relative insensitivity to changes in average PER, average PLR, average CBER and interference across different traces leads us to conclude that they are better measures of the IEEE 802.15.4 channel’s inherent degree of LRD. 215 7. The aggregate variance, R/ S, periodogram, and absolute moment estimators’ strong dependence on average PER and average PLR leads us to conclude that these estimators are good detectors of in-band (WLAN) interference. 8. The average CBER to which a packet is subjected by a channel is inversely related to the average PER/average PLR. Thus, it appears that interference produces higher BERs in packets than do channel fades. 9. We introduced RMI as a standardized version of Shannon mutual information and apply it to the BER process captured in bit traces. We observe that interfer— ence free IEEE 802.15.4 channels are memoryless, while channels experiencing significant interference from IEEE 802.11b / g networks sharing the 2.4GHz ISM band, a common source of interference, have true memory lengths varying in the narrow range of 0 to 2sec. 10.2 Network Lifetime Our analysis and modeling of the network lifetime problem in wireless sensor networks (W SN) in chapters 5 and 6 leads us to make the following conclusions. 1. We propose a new definition of network lifetime consisting of the tuple of mean and variance of node power consumption rates in a WSN. This interpretation of network lifetime is more inclusive and considers the power consumption of sensors across the network. 2. We formulated the optimization problem for the new objective function in the form of a budget constrained QP and showed that a solution exists. The solution of the QP, however, has a high complexity. 216 3. As an alternative to the QP, we developed a greedy dynamic program formu- lation that chooses routes in a way that optimizes for our objective from sets of paths that would be considered sub-optimal in the shortest path sense. Four variants are developed based on the BED, BND, ED and ND algorithms for the discovery of alternative routes. 4. We also observe that the routes generated by the ND algorithm are very similar to those proposed in previously proposed load balancing techniques such as Back and de Veciana’s in [6]. Under a many-to—one traffic flow the same ND paths, when used in conjunction with DPA) yield the worst performance out of the four route discovery algorithms. 5. A statistical performance comparison of these four route discovery algorithms for networks of 100 nodes and A = 0 shows that on average the BND and BED in conjunction with the DPA yield the best performance. BND and BED yield reductions of up to 28% and 36% in variance of power consumption rates at the cost of raising average node power consumption by 15% and 21%, respectively. 6. The computational complexity of variants of the DPA vary from 0(NB) to 0(N4) which is significantly lower than the full search of the solution space which is of complexity 0(NlN). However, for randomly generated networks of 100 nodes we consistently observed that the time to run the DPA on a PC is of the order of a few seconds. 7. Analysis by means of diffusion plots verified that DPA reduced power consump— tion of sensors that experience highest power consumption under shortest path routing algorithms. Diffusion plots also Show that the reduction power con- sumption is highest under BND, followed closely by BED. 8. The resulting route selection method is one that is suitable for applications 217 with rnany-to—one traffic flows. Route discovery algorithms and DPA assume availability of global network topology information which is usually available at the base station. While this makes the DPA a centralized solution we envision it finding applications in critical infrastructure protection/control/monitoring, surveillance, and environmental/ agricultural monitoring applications with in— frequent topology changes. 10.3 WSN Topology Our analysis small-world properties of networks with range limited shortcuts, the application of cooperative communication and diversity combining concepts and cen- trality measures for W SNS in chapters 7, 8 and 9 leads us to make the following conclusions. 1. From the analytical model of characteristic path length and clustering coefficient we observed that for sufficiently dense networks characteristic path length can be reduced significantly by replacing a ,u z O(0.005 — 0.05) fraction of the local scale nodes by global scale nodes providing shortcuts in the network. 2. The order of [,L, the fraction of nodes that are designated shortcut nodes, is about the same as the value of 13, the rewiring probability, in \Natts’ small- world network construction method. 3. The model lends itself for the task of designing WSNS, e. g. determining the num- ber of shortcut nodes required to achieve a certain characteristic path length. 4. We demonstrate gPMSS by application to IEEE 802.15.4 SIMO channel traces and implementation on the Crossbow Imote2 sensor mote. We analyzed the performance of gPMSS in terms of PRR, retransmission attempts and power 218 10. consumption per delivered packet. We saw that for a setup with 3 receivers gPMSS raises the PRR from 22 — 30% to 73 — 76%, a relative increase of 150 — 245%. . we observe gPMSS reduces transmission power per correctly delivered packet by up to 68%. . We evaluated the effect of retry limit imposed by the IEEE 802.15.4 standard of the on the packet delivery rate that can be achieved. At the default retry limit of 3, (m = 4) gPMSS can achieve delivery rates of greater than 99%, against only 65 — 75% when gPMSS is not used. By making use of lossy links feasible, gPMSS can be used as a mechanism for adding shortcut links to enable small—world network topologies in WSNS. Shortcuts implemented by gPMSS will reduce characteristic path length and diameter of networks which facilitates service discovery and the routing of high priority data in a network. It has the advantage of not requiring any hardware modifications ([124] and [125]), or adding wired conuections([27] and [111]). gPMSS used at the base station can increase communication range and the number of sensors at 1 hop distance, thereby increasing the number of critical sensors. This extends the lifetime of nodes surrounding the base station in W'SNs subject to the funneling effect. The larger communication range allows more nodes to communicate with the base station directly and reduces the traffic load from nodes positioned closer to the base station. More generally, gPMSS can be used to connect weakly connected components of a network by adding more links between nodes farther apart. We conducted a review of pre-existing measures of node centrality and their shortcomings with regard to W SNs. We introduced PCC, a new measure of 219 node centrality. A node’s PCC can be interpreted as its 62 norm from the origin in the eigenspace formed by the P most significant feature vectors (eigenvectors) of the adjacency matrix. 11. While we see PCC as having wider applications, an immediate application of di- rect relevance is its use in identifying nodes for the placement of shared network resources, e.g. endpoints of shortcut links created through gPMSS. 12. To select an apprOpriate number of features for the computation of PCC we explored two methods. 0 The relative contribution of each additional feature’s power (eigenvalue) to the total power of adjacency matrix. The use of the adjacency matrix is compared with that of the Laplacian. We concluded that eigendecompo- sition of the adjacency matrix yields significantly higher degree of energy compaction than the Laplacian at the same number of features. However, the cumulative scree plot of neither matrix yields a clear cutoff region for the selection of number of features P to use for PCC. o Incremental changes in the phase angle of C P (PCC with P features) and C1 (EVC) as P is increased. We concluded that PCC reaches steady state \v'alues with the use of only 5 to 10% most significant features out of all available feature vectors. Selecting number of features P using the phase angle function d)(P) yields a very clear cutoff region. 220 BIBLIOGRAPHY [1] L. Adamic. The small world web. Lecture Notes in Computer Science, pages 443-452, 1999. [2] IF. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci. Wireless sensor networks: A survey. Computer Networks, 38(4):393—422, 2002. [3] L.A.N. Amaral, A. Scala, M. Barthelemy, and HE. Stanley. Classes of small-world networks. Proceedings of the National Academy of Sciences, page 200327197, 2000. [4] ANSI/IEEE. Ansi/ieee std 802, part 15.1: Wireless personal area network. Technical report, IEEE, 2002. [5] ANSI/IEEE. Ansi/ieee std 802, part 15.4: Low rate wireless personal area networks. Technical report, ANSI/IEEE, 2006. [6] SJ. Back and G. de Veciana. Spatial energy balancing in large—scale wireless multihop networks. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, 2005. [7] P. Bahl, A. Adya, J. Padhye, and A. Walman. Reconsidering wireless sys- tems with multiple radios. ACM SI G COMM Computer Communication Review, 34(5):39—~46, 2004. [8] Z. Bai, J. Demmel, J. Dongarra, A. Petitet, H. Robinson, and K. Stanley. The spectral decomposition of nonsymmetric matrices on distributed memory parallel computers. SIAM Journal on Scientific Computing, 18:1446—1461, 1997. [9] J. Barros and SD. Servetto. On the capacity of the reachback channel in wireless sensor networks. In IEEE Workshop on Multimedia Signal Processing, pages 408—411, 2002. [10] J. Beran. Statistics for Long-Memory Processes. Chapman & Hall/CRC, 1994. 221 [11] M. Bhardwaj and AP. Chandrakasan. Bounding the lifetime of sensor networks via optimal role assignment. In Proceedings of the 21 st Annual Joint Conference of the IEEE Computer and Communications Societies {INFOCOM}, 2002. [12] C. Bischof and Institute for Defense Analyses. Parallel Performance of a Sym- metric Eigensolver Based on the Invariant Subspace Decomposition Approach. Supercomputing Research Center: IDA, 1994. [13] B. Bollobas. Random Graphs. Cambridge University Press, 2001. [14] P. Bonacich. Power and centrality: A family of measures. American Journal of Sociology, 92:1170—1182, 1987. [15] P. Bonacich and P. Lloyd. Eigenvector—like measures of centrality for asymmet- ric relations. Social Networks, 23(3):191-201, 2001. [16] SP. Borgatti. Centrality and network flow. Social Networks, 27(1):55—71, 2005. [17] SP. Borgatti and MC. Everett. A graph-theoretic perspective on centrality. Social Networks, 28(4):466—484, 2006. [18] SP. Boyd and L. Vandenberghe. Convert optimization. Cambridge University Press, 2004. [19] DC. Brennan. Linear diversity combining techniques. Proceedings of the IEEE, 91(2):331-356, 2003. [20] G. Canright, K. Engo—Monsen, and M. Jelasity. Efficient and robust fully dis- tributed power method with an application to link analysis. Department of Computer Science, University of Bologna, Tech. Rep. UBLCS—2005-17, pages 2005—17, 2005. [21] GS. Canright and K. Engo-Monsen. Spreading on networks: A topographic view. ComPlerUs, 3(1-3):131—146, 2006. [22] I. Carreras, D. lViiorandi, G.S. Canright, and K. Engo-Monsen. Understanding the spread of epidemics in highly partitioned mobile networks. In Proceedings of the 1 st international conference on Bio inspired models of network, information and computing systems. ACM New York, NY, USA, 2006. [23] D. Cavalcanti, D. Agrawal, J. Kelner, and D. Sadok. Exploiting the small— world effect to increase connectivity in wireless ad hoc networks. In IEEE International Conference on Telecommunications, 2004. [24] SS. Chakraborty, E. Yli-Juuti, and M. Liinaharja. An arq scheme with packet combining. IEEE Communications Letters, 2(7):200~202, 1998. 222 [25] J .H. Chang and L. Tassiulas. Energy conserving routing in wireless ad-hoc networks. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies {Infocom}, 2000. [26] 8. Cheng and MC. Valenti. Macrodiversity packet combining for the ieee 802.11 a uplink. In Proceedings of the IEEE Wireless Communications and Networking Conference ( WCN C ’05 ), volume 1, 2005. [27] R. Chitradurga and A. Helmy. Analysis of wired short cuts in wireless sen- sor networks. In IEEE/ACS International Conference on Pervasive Services (ICPS ’04), pages 167—177, July 2004. [28] Fan R. K. Chung. Spectral Graph Theory (CBMS Regional Conference Series in Mathematics, No. 92) (Cbms Regional Conference Series in Mathematics). American Mathematical Society, February 1997. [29] R.K. Colwell and DJ. Futuyma. On the measurement of niche breadth and overlap. Ecology, 52(4):567—576, 1971. [30] T. Cormen, C. Leisersoon, and R. Rivest. Introduction to algorithms 2nd ed. MIT Press, Cambridge, MA, 2001. [31] RA. Costa and J. Barros. Dual radio networks: Capacity and connectivity. In Intl Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops (WiOpt’07), pages 1—6, 2007. [32] TM. Cover and J.A. Thomas. Elements of Information Theory. \Niley- Interscience New York, 2006. [33] Crossbow. MIB6UOCA, Ethernet Interface Board Datasheet. Crossbow Technol- ogy Inc., http://www.xbow.com/Products/productdetails.aspx?sid=179, 6020- 0055-04 rev a edition, Oct 2006. [34] Crossbow. MPR2400, ZigBee, 2.4 CH2, MI- CA2 Mote Datasheet. Crossbow Technology Inc., http: / / www.xbow.com / Products / productdetails.aspx?sid=164, 6020-0060- 04 rev a edition, Oct 2006. [35] Crossbow Technology. Crossbow Imote2 Datasheet, 6020-0117-02 rev a edition, April 2007. [36] T. Dimitar, F. Sonja, M. Jani, and G. Aksenti. Small world application layer for ad hoc networks. In Proceedings of T elekomunikacioni Forum Telfor, 2003. [37] S. Dixit, E. Yanmaz, and OK. Tonguz. On the design of self-organized cellular wireless networks. IEEE Communications Magazine, 43(7):86—93, 2005. 223 [38] R0. Duda, P.E. Hart, and DC. Stork. Pattern Classification. Wiley New York, 2nd edition, 2001. [39] H. Everett. Generalized lagrange multiplier method for solving problems of optimum allocation of resources. Operations Research, 11:399—417, 1963. [40] MG. Everett and SP. Borgatti. Extending centrality. Cambridge University Press, 2005. [41] LC. Freeman. A set of measures of centrality based on betweenness. Sociometry, 40(1):35—41, 1977. [42] N .E. Friedkin. Theoretical foundations for centrality measures. American Jour- nal of Sociology, 96(6):1478, 1991. [43] P. Gupta and PR. Kumar. The capacity of wireless networks. IEEE Transac- tions on Information Theory, 46(2):388—404, 2000. [44] J.A. Hartigan and MA. Wong. A k-means clustering algorithm. JR Stat. Soc. Ser. C—Appl. Stat, 28:100—108, 1979. [45] H. He. Eigenvectors and reconstruction. the electronic journal of combinatorics, 14(14):1, 2007. [46] A. Helmy. Small large-scale wireless networks: l\/Iobility-assisted resource dis- covery. Arriv preprint cs/0207069, 2002. [47] A. Helmy. Small worlds in wireless networks. IEEE Communications Letters, 7(10):490—492, 2003. [48] I. Howitt and J .A. Gutierrez. Ieee 802.15. 4 low rate-wireless personal area net- work coexistence issues. In Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC’OS’), volume 3, 2003. [49] J .P. Hubaux, T. Gross, J .Y. Le Boudec, and M. Vetterli. Toward self—organized mobile ad hoc networks: the terminodesproject. IEEE Communications Mag— azine, 39(1):118—124, 2001. [50] RF. i Cancho and RV. Sole. The small world of human language. Proceedings of the Royal Society B: Biological Sciences, 268(1482):2261—2265, 2001. [51] IEEE. Ieee 802.11b—1999, part 11: Wireless lan: Higher speed physical layer (phy) extension in the 2.4 ghz band. Technical report, IEEE, 2003. [52] M. U. Ilyas, M. Kim, and H. Radha. Reducing packet losses in networks of commodity ieee 802.15.4 sensor motes using cooperative communication and diversity combination. In Proceedings of the 28th IEEE International Confer- ence on Computer Communications {INFOCOM’OQ}, Rio de Janeiro, Brazil, April 2009. 224 [53] [54] W [58] [59] [60] [61] [62] Ml l64l M. U. Ilyas and H. Radha. Increasing network lifetime of an ieee 802.15. 4 wireless sensor network by energy efficient routing. In Proceedings of IEEE International Conference on Communications, 2006. M. U. Ilyas and H. Radha. Long range dependence of ieee 802.15.4 wireless channels. In Proceedings of the IEEE International Conference on Communi- , cations (ICC’OS), May 2008. M. U. Ilyas and H. Radha. Measurement based analysis and modeling of the error process in ieee 802.15.4 lr-wpans. In Proceedings of the 27th IEEE Confer- ence on Computer Communications (INFOCOM’UcS’). IEEE, IEEE, April 2008. M. U. Ilyas and H. Radha. Measuring packet-level memory length of 802.15.4 wireless channels with relative mutual information. In Proceedings of the IEEE International Conference on Communications (ICC ’08), May 2008. M. U. Ilyas and H. Radha. On measuring memory length of the error rate process in wireless channels. In Proceedings of the 42nd Annual Conf. on In- formation Sciences and Systems (CISS ’08), March 2008. C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: A scal- able and robust communication paradigm for sensor networks. In ACM/IEEE International Conference on Mobile Computing and Networking, pages 56-67. Boston, USA, 2000. SS. Iyengar and RR. Brooks. Distributed sensor networks. CRC Press, 2004. Z. Ji, Y. Yang, J. Zhou, M. Takai, and R. Bagrodia. Exploiting medium access diversity in rate adaptive wireless lans. In Intl conference on Mobile Camputing and Networking, pages 345—359. ACM New York, NY, USA, 2004. D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. Mobile Computing, 353(153-181):152, 1996. A. Kansal, M. Goraczko, and F. Zhao. Building a sensor network of mobile phones. In Proceedings of the 6th international conference on Information pro- cessing in sensor networks, page 548. ACM, 2007. T. Karagiannis, M. Faloutsos, and R. H. Riedi. Long-range dependence: now you see it, now you don’t! In Global Telecommunications Conference (GLOBE- COM’OQ), volume 3, 2002. S. Karande, S.A. Khayam, Y. Cho, K. Misra, H. Radha, J. Kim, and J.W. Hong. On channel state inference and prediction using observable variables in 802.11 b network. In Proceedings of the IEEE International Conference on Communications (ICC’07), pages 4554—4559, 2007. 225 [65] R. Khanna, H. Liu, and H.-H. Chen. Self-organization of sensor networks us- ing genetic algorithms. In Proceedings of IEEE International Conference on Communications, 2006. [66] S. A. Khayam and H. Radha. Linear—complexity models for wireless mac-to—mac channels. Wireless Networks, 11(5):543—555, 2005. [67] S. A. Khayam and H. Radha. Constant-complexity models for wireless channels. In Proceedings of the 25th Annual Joint Conf. on the IEEE Computer and Communications Societies (INFOCOMO6), 2006. [68] SA. Khayam, S. Karande, H. Radha, and D. Loguinov. Performance analysis and modeling of errors and losses over 802.11 b lans for high-bit-rate real-time multimedia. Signal Processing: Image Communication, 18(7):575—595, 2003. [69] C. Kohlschiitter, P. Chirita, and W. Nejdl. Efficient parallel computation of pagerank. Lecture Notes in Computer Science, 39362241, 2006. [70] A. Konrad, B.Y. Zhao, A.D. Joseph, and R. Ludwig. A markov-based channel model algorithm for wireless networks. Wireless Networks, 9(3):189-199, 2003. [71] L. Krishnamachari, D. Estrin, and S. Wicker. The impact of data aggregation in wireless sensor networks. In Proceedings of the 22nd International Conference on Distributed Computing Systems Workshops, pages 575—578, 2002. [72] AN. Langville, C.D. Meyer, and P. FernAndez. Googles pagerank and beyond: the science of search engine rankings. The Mathematical Intelligencer, 30(1):68- 69, 2008. [73] V. Latora and M. Marchiori. Efficient behavior of small-world networks. Phys- ical Review Letters, 87(19):198701-1—198701—4, 2001. [74] V. Latora and M. Marchiori. Is the boston subway a small-world network? Physica A: Statistical Mechanics and its Applications, 314(1-4):109-113, 2002. [75] P. Levis, S. Madden, J. Polastre, R. Szewczyk, K. Whitehouse, A. Woo, D. Gay, J. Hill, M. Welsh, and E. Brewer. TinyOS: An Operating System for Sensor Networks, volume -. Springer Verlag, 2005. [76] J. Lin. Divergence measures based on the Shannon entropy. IEEE Transactions on Information Theory, 37(1):145—151, 1991. [77] S. Lin, J. Zhang, G. Zhou, L. Gu, J.A. Stankovic, and T. He. Atpc: adaptive transmission power control for wireless sensor networks. In Proceedings of the 4th International Conf. on Embedded Networked Sensor Systems, pages 223— 236. ACM Press New York, NY, USA, 2006. 226 [78] R. Madan and S. Lall. Distributed algorithms for maximum lifetime routing in [79} [80] l81l [82] [83] l84l [87] [88] [89] wireless sensor networks. In Proceedings of the IEEE Global Telecommunications Conference (GLOBECOM), volume 2, 2004. S. Madden, M.J. Franklin, J .M. Hellerstein, and W. Hong. Tag: a tiny aggrega- tion service for ad-hoc sensor networks. In Proceedings of the ACM Symposium on Operating System Design and Implementation (OSDI’OQ), 2002. D. Marco, E.J. Duarte-Melo, M. Liu, and D.L. Neuhoff. On the many-to-one transport capacity of a dense wireless sensor network and the compressibility of its data. In Proceedings of the 2nd International Workshop Information Processing in Sensor Networks (IPSN’OS’), Palo Alto, CA, USA, April 22—23, 2003. Springer, 2003. D. Marco and D.L. Neuhoff. Reliability vs. efficiency in distributed source coding for field-gathering sensor networks. In Proceedings of the 3rd Inter- national symposium on Information processing in sensor networks (IPSN’OI), pages 161—168. ACM Press New York, NY, USA, 2004. S. Milgram. The small world problem. Psychology Today, 2(1):60—67, 1967. A. Miu, J.G. Apostolopoulos, W. Tan, and M. Trott. Low-latency wireless video over 802.11 networks using path diversity. In Proceedings of the IEEE International Conference on Multimedia 65 Errpo, volume 3, pages 441—444, July 2003. A. Miu, H. Balakrishnan, and CE. Koksal. Improving loss resilience with multi- radio diversity in wireless networks. In Proceedings of the The 11th Annual International Conference on Mobile Computing and Networking (MobiCom), pages 16—30. ACM, Aug-Sep 2005. A. Miu, G. Tan, H. Balakrishnan, and J. Apostolopoulos. Divert: fine-grained path selection for wireless lans. In Proceedings of the 2nd International confer- ence on Mobile systems, applications, and services, pages 203-216. ACM New York, NY, USA, 2004. A.F. Molisch, K. Balakrishnan, CC. Cheng, S. Emami, A. Fort, J. Karedal, J. Kunisch, H. Schantz, U. Schuster, and K. Siwiak. Ieee 802.15. 4a channel model-final report. IEEE P, 151802—1504, 2006. J .M. Montoya and RV. SolE. Small world patterns in food webs. Journal of Theoretical Biology, 214(3):405—412, 2002. C. Moore and M.E.J. Newman. Epidemics and percolation in small—world net- works. Physical Review E, 61(5):5678-5682, 2000. C. Moore and M.E.J. Newman. Exact solution of site and bond percolation on small-world networks. Physical Review E, 62(5):7059—~7064, 2000. 227 [90] [91] [92] [931 [981 {99] [100] [101] [102] M.E.J. Newman. Analysis of weighted networks. Physical Review E, 70(5):56131, 2004. M.E.J. Newman, C. Moore, and DJ. Watts. Mean-field solution of the small- world network model. Physical Review Letters, 84(14):3201—3204, 2000. M.E.J. Newman and DJ. Watts. Scaling and percolation in the small-world network model. Physical Review, 60(6):7332—7342, 1999. G. T. Nguyen, B. Noble, R. H. Katz, and M. Satyanarayanan. A trace-based approach for modeling wireless channel behavior. In Proceedings of the Winter Simulation Conf. 1996, pages 597—604, 1996. A. Ortega and K. Ramchandran. From rate—distortion theory to commercial image and video compression technology. IEEE Signal Processing Magazine, 15(6y20—22,1998. B.P. Pal and P. Scientist. Sensorplanet: An open global research framework for mobile device centric wireless sensor networks. In M obiS ensors: NSF Workshop on Data Management for Mobile Sensor Networks, Pittsburgh, 2007. S. A. Pandit and R. E. Amritkar. Characterization and control of small-world networks. Physical Review, 60(2):1119—1122, 1999. S. Pattern, B. Krishnamachari, and R. Govindan. The impact of spatial correla- tion on routing with compression in wireless sensor networks. In Proceedings of the 3rd International symposium on Information processing in sensor networks (IPSN’OI), pages 28—35. ACM Press New York, NY, USA, 2004. M. Penrose. Random Geometric Graphs. Oxford University Press, 2003. C. E. Perkins and P. Bhagwat. Highly dynamic destination—sequenced distance- vector routing (dsdv) for mobile computers. In Proceedings of the Conf. on Com- munications architectures, protocols and applications {SIGCOMM’QI}, pages 234—244. ACM Press New York, NY, USA, 1994. C. E. Perkins and E. M. Royer. Ad~hoc on—demand distance vector routing. In Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, volume 2, pages 90—100. Feb, 1999. J. Polastre, R. Szewczyk, and D. Culler. Telos: enabling ultra—low power wireless research. In Proceedings of the 4th International Symposium on Information Processing in Sensor Networks { IPSN ’05 ), pages 364—369, 2005. S. Pollin, M. Ergen, M. T immers, A. Dejonghe, L.'Van der Perre, I. Moerman, F. Catthoor, and A. Bahai. Distributed cognitive coexistence of 802.15. 4 with 802.11. In Proceedings of the lst International Conference on Cognitive Radio Oriented Wireless Networks and Communications, pages 1-5, 2006. 228 [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] H. Radha, M. Vetterli, and R. Leonardi. Image compression using binary space partitioning trees. IEEE Transactions on Image Processing, 5:1610—1624, 1996. T. S. Rappaport. Wireless Communications Principles and Practice. Prentice Hall PTR Upper Saddle River, NJ, 2002. C. Reis, Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Measurement- based models of delivery and interference in static wireless networks. ACM SIGCOMM Computer Communication Review, 36(4):51-62, 2006. B. Ruhnau. Eigenvector-centrality a node-centrality? Social Networks, 22(4):357—365, 2000. A. Sankar and Z. Liu. Maximum lifetime routing in wireless ad—hoc networks. In Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (Infocom), volume 2, 2004. K. Sankaralingam, S. Sethumadhavan, and J .C. Browne. Distributed pagerank for p2p systems. In High Performance Distributed Computing, 2003. Proceed- ings. 12th IEEE International Symposium on, pages 58-68, 2003. GM. Schuster and AK. Katsaggelos. Rate-Distortion Based Video Com- pression: Optimal Video Frame Compression and Object Boundary Encoding. Kluwer Academic Publishers, 1997. P. Sen, S. Dasgupta, A. Chatterjee, PA. Sreeram, G. Mukherjee, and SS. Manna. Small-world properties of the indian railway network. Physical Review E, 67(3):36106, 2003. G. Sharma and R. Mazumdar. Hybrid sensor networks: a small world. In ACM Intl Symposium on Mobile Ad Hoc Networking and Computing, pages 366—377. ACM Press New York, NY, USA, 2005. A. Sikora and V.F. Groza. Coexistence of ieee802. 15.4 with other systems in the 2.4 ghz-ism—band. In Proceedings of IEEE Instrumentation and Measurement Technology Conference (IMTC05), volume 3, pages 1786—1791, 2005. S. Singh, M. Woo, and CS. Raghavendra. Power—aware routing in mobile ad hoc networks. In Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, pages 181—190, 1998. D. Slepian and J. Wolf. Noiseless coding of correlated information sources. IEEE Transactions on Information Theory, 19(4):471—480, 1973. K. Srinivasan, P. Dutta, A. Tavakoli, and P. Levis. Some implications of low power wireless to ip networking. In Proceedings of the 5th Workshop on Hot Topics in Networks (HotNets-V), 2006. 229 [116] K. Srinivasan and P. Levis. Rssi is under appreciated. In Proceedings of the 3rd Workshop on Embedded Networked Sensors {EmNets’06), 2006. [117] W. Stallings. Wireless Communications Ed Networks. Prentice-Hall, Inc. Upper Saddle River, NJ, USA, 2004. [118] G.J. Sullivan and T. Wiegand. Rate-distortion optimization for video compres- sion. IEEE Signal Processing Magazine, 15(6):74—90, 1998. [119] AS. Tanenbaum. Computer Networks. Prentice Hall PTR, 2002. [120] TI and Chipcon. Chipcon AS SmartRF CC2420 Preliminary Datasheet (rev [122] [123] [124] [126] [127] [128] [129] [130] 1.2), 2004-06-09. TI Chipcon, 1.2 edition, June 2004. F. Tisseur and J. Dongarra. A parallel divide and conquer algorithm for the sym- metric eigenvalue problem on distributed memory architectures. SIAM Journal on Scientific Computing, 2012223, 1999. H.L. Van Trees. Detection, Estimation, and Modulation Theory Part I. MIT Press, Cambridge, MA, 1968. MC. Valenti. Improving uplink performance by macrodiversity combining pack- ets from adjacent access points. In Proceedings of the IEEE Wireless Commu- nications and Networking Conference (WCNC’OS’), volume 1, 2003. C.Y. Wan, A.T. Campbell, and J. Crowcroft. A case for all-wireless, dual- radio virtual sinks. In Intl Conf on Embedded Networked Sensor Systems, pages 267—268. ACM Press New York, NY, USA, July 2004. C.Y. Wan, S.B. Eisenman, A.T. Campbell, and J. Crowcroft. Siphon: overload traffic management using multi-radio virtual sinks in sensor networks. In Intl Conf on Embedded Networked Sensor Systems, pages 116—129. ACM Press New York, NY, USA, 2005. S. W’asserman and K. Faust. Social network analysis: Methods and applications. Cambridge University Press, 1994. DJ. Watts. Networks, dynamics, and the small-world phenomenon. American Journal of Sociology, 105(2):493—527, 1999. DJ. Watts. Small Worlds: The Dynamics of Networks between Order and Randomness. Princeton University Press, 1999. DJ. Watts and SH. Strogatz. Collective dynamics of small-world networks. Nature, 393:440—442, 1998. P. W horiskey. Instant-messagers really are about six degrees from kevin bacon. Washington Post, page A01, August 2 2008. 230 [131] GP. Williams. Chaos Theory Tamed. Joseph Henry Press, 1997. [132] [133] [134] [135] [136] [137] C. Won, J .H. Youn, H. Ali, H. Sharif, and J. Deogun. Adaptive radio channel allocation for supporting coexistence of 802.15. 4 and 802.11 b. In Proceedings of the Vehicular Technology Conference (Fall), 2005. A. Woo, T. Tong, and D. Culler. Taming the underlying challenges of reliable multihop routing in sensor networks. In Proceedings of the Jst International Conf. on Embedded Networked Sensor Systems, pages 14~27. ACM Press New York, NY, USA, 2003. CR. Woo, P. Kheradpour, D. Shen, and D. Katabi. Beyond the bits: coop- erative packet recovery using physical layer information. In Proceedings of the 13th annual ACM international conference on Mobile computing and network- ing (MobiCom), pages 147—158. ACM Press New York, NY, USA, September 2007. L. Xiao, M. Johansson, and SP. Boyd. Simultaneous routing and resource allocation via dual decomposition. IEEE Transactions on Communications, 52(7):1136-1144, 2004. DC. Yoon, S.Y. Shin, W.H. Kwon, and HS. Park. Packet error rate analysis of ieee 802.11 b under ieee 802.15.4 interference. In Proceedings of the 63rd IEEE Vehicular Technology Conference (VTC’Od-Spring), volume 3, 2006. M. Zuniga and B. Krishnamachari. Analyzing the transitional region in low power wireless links. In Proceedings of the Ist Annual IEEE Communica- tions Society Conf. on Sensor and Ad Hoc Communications and Networks (SECON’04)., volume 2004, pages 517—526, 2004. 231