Energy-ecient Algorithm Design for Wireless Sensor Networks by Vahid Shah-Mansouri B.Sc., Electrical and Computer Engineering, University of Tehran, Iran, 2003 M.Sc., Electrical Engineering, Sharif University of Technology, Iran, 2005 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY in The Faculty of Graduate Studies (Electrical and Computer Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) August 2011 c Vahid Shah-Mansouri, 2011 Abstract Wireless sensor networks (WSNs) are composed of inexpensive sensor devices called sensor nodes. Sensors have limited power supply, computational capabilities, and memory. Dif- ferent types of sensors can measure either temperature, light, sound, or pressure from the environment. Because the sensors have short transmission range, the generated data are gathered via multihop transmissions at a central processor called a sink. In this thesis, we propose several power ecient algorithms for WSNs. First, we formulate the lexicographically optimal commodity lifetime routing problem. We propose the lexicographically optimal node lifetime algorithm, which is suitable for practical implementation. Simulation results show that our proposed algorithm can in- crease the network lifetime compared to other schemes in the literature. Second, we study the problem of supporting multicast trac in WSNs with network coding. We formulate the maximum-lifetime minimum-resource coding subgraph problem to study the lifetime-resource tradeo. Results show that the network lifetime can be substantially increased using our algorithm. Next, we consider the problem of designing feedback mechanisms for WSNs using ran- dom linear network coding (RLNC). For an intermediate node, we determine the time at which the node can stop transmission of a particular ow. We propose novel link-by-link and end-to-end feedback mechanisms for RLNC with buer sharing. Simulation results show that link-by-link feedback is more power-ecient compared to end-to-end feedback. Then, we study the passive loss inference problem in WSNs using RLNC. By inspecting ii Abstract the contents of packets at the sink, the sink can estimate the path loss rates from the sources and intermediate nodes. We propose a passive loss inference with RLNC algorithm. Simulation results show that our algorithm can identify the status of a higher number of links compared to a Bayesian inference algorithm. Finally, we study the problem of cardinality estimation in radio frequency identication systems with several readers. We introduce exclusive estimators to estimate the number of tags located exclusively in the zone of a reader. Then, we propose cardinality estimation algorithms. Our simulation results show that the variance of our proposed estimation algorithms increases linearly with the number of readers while it increases exponentially for existing algorithms. iii Preface I am the rst author and principal contributor of all chapters. All chapters are co-authored with Dr. Vincent W.S. Wong, who supervised the research. Chapter 2 is also co-authored with Dr. Amir-Hamed Mohsenian-Rad, who contributed in formulating the problem as a mixed integer programming problem. The following publications describe the work completed in this thesis. In some cases, the conference papers contain materials overlapping with the journal papers. Journal Papers Accepted/Published Vahid Shah-Mansouri and Vincent W.S. Wong, \Cardinality Estimation in RFID Systems with Multiple Readers," IEEE Trans. on Wireless Communications, vol. 10, no. 5, pp. 1458 - 1469, May 2011. Vahid Shah-Mansouri and Vincent W.S. Wong, \Lifetime-Resource Tradeo for Mul- ticast Trac in Wireless Sensor Networks," IEEE Trans. on Wireless Communica- tions, vol. 9, no. 6, pp. 1924 - 1934, June 2010. Vahid Shah-Mansouri and A. Hamed Mohsenian-Rad and Vincent W.S. Wong, \Lex- icographically Optimal Routing for Wireless Sensor Networks with Multiple Sinks," IEEE Trans. on Vehicular Technology, vol. 58, no. 3, pp. 1490 - 1500, March 2009. iv Preface Journal Paper Submitted Vahid Shah-Mansouri and Vincent W.S. Wong, \Feedback Mechanism for Random Linear Network Coding with Buer Sharing in Lossy Wireless Sensor Networks," to be submitted. Conference Papers Published Vahid Shah-Mansouri and Vincent W.S. Wong, \Link Loss Inference in Wireless Sensor Networks with Randomized Network Coding," in Proc. of IEEE Global Com- munications Conference (Globecom), Miami, FL, December 2010. Vahid Shah-Mansouri and Vincent W.S. Wong, \Anonymous Cardinality Estimation in RFID Systems with Multiple Readers," in Proc. of IEEE Global Communications Conference (Globecom), Honolulu, HI, December 2009. Vahid Shah-Mansouri and Vincent W.S. Wong, \Maximum-Lifetime Coding Sub- graph for Multicast Trac in Wireless Sensor Networks," in Proc. of IEEE Global Telecommunications Conference (Globecom), New Orleans, LA, November/December 2008. Vahid Shah-Mansouri, Hamed Mohsenian-Rad, and Vincent W.S. Wong, \Multicom- modity Lifetime Routing for Wireless Sensor Networks with Multiple Sinks," in Proc. of IEEE International Conference on Communications (ICC), Beijing, China, May 2008. Vahid Shah-Mansouri and Vincent W.S. Wong, \Distributed Maximum Lifetime Routing in Wireless Sensor Networks Based on Regularization," in Proc. of IEEE Global Telecommunications Conference (Globecom), Washington, DC, November 2007. v Preface Vahid Shah-Mansouri and Vincent W.S. Wong, \Bounds for Lifetime Maximization with Multiple Sinks in Wireless Sensor Networks," in Proc. of IEEE Pacic Rim Conference on Communications, Computers and Signal Processing (Pacrim), Victo- ria, BC, Canada, August 2007. vi Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviii Dedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xx 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Wireless Sensor Networks (WSNs) . . . . . . . . . . . . . . . . . . . . . . 1 1.1.1 Wireless Sensor Network Terminology . . . . . . . . . . . . . . . . 3 1.2 Network Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 Network Tomography . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 RFID Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Mathematical Background . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.1 Convex Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 9 vii Table of Contents 1.4.2 Linearization Technique . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.3 Regularization Technique . . . . . . . . . . . . . . . . . . . . . . . 14 1.5 Contributions and Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.6 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Lexicographically Optimal Routing for WSNs with Multiple Sinks . . 20 2.1 Lexicographically Optimal Commodity Lifetime (LOCL) Algorithm . . . . 23 2.1.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.3 LOCL Algorithm: First Step . . . . . . . . . . . . . . . . . . . . . 26 2.1.4 LOCL Algorithm: Subsequent Steps . . . . . . . . . . . . . . . . . 31 2.2 Lexicographically Optimal Node Lifetime (LONL) Algorithm . . . . . . . 34 2.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.2.2 Distributed Implementation . . . . . . . . . . . . . . . . . . . . . . 37 2.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.1 Performance of LOCL Algorithm . . . . . . . . . . . . . . . . . . . 39 2.3.2 Performance Comparisons between LOCL, LONL, MLMS, and LMM Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5 Analytical Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.5.1 Proof of Lemma 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.5.2 Proof of Lemma 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.5.3 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3 Lifetime-Resource Tradeo for Multicast Trac in WSNs . . . . . . . 50 3.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.1.1 System Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 55 viii Table of Contents 3.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.2.1 Maximum Lifetime Minimum Resource Problem . . . . . . . . . . 59 3.2.2 Limit the Rate of Coding Operations . . . . . . . . . . . . . . . . . 70 3.2.3 Limit the Number of Coding Devices . . . . . . . . . . . . . . . . . 71 3.2.4 Minimize the Number of Coding Devices . . . . . . . . . . . . . . . 72 3.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.3.1 Varying the Tuning Parameter . . . . . . . . . . . . . . . . . . . 73 3.3.2 Varying the Number of Sinks jDsj . . . . . . . . . . . . . . . . . . 76 3.3.3 Varying the Number of Sources jSj . . . . . . . . . . . . . . . . . . 77 3.3.4 Comparison between MLMR and EMR Algorithms . . . . . . . . . 78 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4 Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs 82 4.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.2 Transmission Rate Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.2.1 When Can Node i Stop Transmission of Flow f? . . . . . . . . . . 89 4.2.2 Determine the Time fi . . . . . . . . . . . . . . . . . . . . . . . . 92 4.2.3 Transmission Rate of Innovative Packets After Time fi . . . . . . 94 4.3 Feedback Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.3.1 Link-by-Link Feedback Mechanism . . . . . . . . . . . . . . . . . . 98 4.3.2 End-to-End Feedback Mechanism . . . . . . . . . . . . . . . . . . . 99 4.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5 Link Loss Inference in WSNs with RLNC . . . . . . . . . . . . . . . . . . 110 5.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.1.1 Network Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 ix Table of Contents 5.1.2 Random Linear Network Coding (RLNC) . . . . . . . . . . . . . . 113 5.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.2.1 Path Loss Estimation . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.2.2 Identiability Problem . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 5.3.1 Number of Identiable Links . . . . . . . . . . . . . . . . . . . . . 121 5.3.2 Performance Comparison . . . . . . . . . . . . . . . . . . . . . . . 122 5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5 Analytical Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.5.1 Proof of Lemma 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 6 Cardinality Estimation in RFID Systems with Multiple Readers . . . 127 6.1 System Model and Problem Statement . . . . . . . . . . . . . . . . . . . . 129 6.1.1 Notations and Model . . . . . . . . . . . . . . . . . . . . . . . . . 129 6.1.2 Multiple Counting Problem . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Asynchronous Multiple Reader Cardinality Estimation . . . . . . . . . . . 133 6.2.1 Asynchronous Exclusive Estimator . . . . . . . . . . . . . . . . . . 133 6.2.2 A-MRCE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 135 6.2.3 Estimation Error and Discussion . . . . . . . . . . . . . . . . . . . 138 6.3 Synchronous Multiple Reader Cardinality Estimation (S-MRCE) . . . . . 140 6.3.1 Synchronous Exclusive Estimator . . . . . . . . . . . . . . . . . . . 140 6.3.2 S-MRCE Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 6.4.1 Performance Evaluation for Exclusive Estimators . . . . . . . . . . 147 6.4.2 Performance Evaluation for A-MRCE and S-MRCE Algorithms . . 151 6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 x Table of Contents 6.6 Analytical Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.6.1 Proof of Theorem 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 156 6.6.2 Proof of Theorem 6 . . . . . . . . . . . . . . . . . . . . . . . . . . 159 7 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.1 Research Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 7.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 163 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 xi List of Tables 3.1 Average number of links performing network coding. . . . . . . . . . . . . 79 xii List of Figures 2.1 A sample WSN with two sinks. . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 LOCL algorithm for network with dierent number of sinks: (a) Minimum commodity lifetime; (b) Average number of iterations in LOCL algorithm. 40 2.3 Lifetime of commodities for LOCL algorithm with dierent number of sources. 41 2.4 Lifetime of commodities for LOCL algorithm when there are single and dierent types of sinks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.5 Average normalized minimum lifetime in LONL algorithm versus . . . . . 43 2.6 Lifetime of commodities for LOCL, LONL, LMM, and MLMS algorithms in a network with four sinks. . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.7 Lifetime of nodes for LONL, LMM, and MLMS algorithms for a network with four sinks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1 Sample network with the source node s and two sinks (d1, d2). . . . . . . . 60 3.2 Network with three sinks (d1, d2, d3) and one source node s with data generation rate of 2 units per second. (a) Information ow values, (b) coding subgraph (actual rate values), (c) coding ow values, (d) multipath packet transmission. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.3 Average network lifetime under dierent values of . . . . . . . . . . . . . . 74 3.4 Total rate of performing network coding under dierent values of . . . . . 75 3.5 Network lifetime versus coding operation rate. . . . . . . . . . . . . . . . . 76 xiii List of Figures 3.6 Network lifetime under dierent number of sinks ( = 104). . . . . . . . . 77 3.7 Total rate of coding operations under dierent number of sinks ( = 104). 78 3.8 Network lifetime for dierent number of sources ( = 104). . . . . . . . . 79 3.9 Total rate of coding operations under dierent number of sources ( = 104). 80 3.10 Network topology: (a) one copy, (b) three copies. . . . . . . . . . . . . . . 81 4.1 A network tree with two sources, one intermediate node i, and one sink. Packets of ows 1 and 2 are generated by source s1 and s2, respectively. . . 90 4.2 Normalized average power consumption versus generation size K for = 2. 103 4.3 Normalized average power consumption versus parameter . . . . . . . . . 104 4.4 The normalized decoding delay between RLNC with and without buer sharing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 4.5 Normalized average power consumption versus the number of sources for = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.6 Normalized average power consumption versus the number of nodes for = 2.108 5.1 A sample WSN with ve sources, namely 1, 2, 3, 4, and 7. . . . . . . . . . 114 5.2 Average number of links whose rates determined using PLI-RLC algorithm. 122 5.3 Comparison of false detection for PLI-RLC algorithm and Bayesian inference algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.1 An RFID system with two readers r1 and r2. nr1 = 6, nr2 = 7, N = 11, f = 10, and p = 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Network topologies: (a) Three readers, and (b) Ten readers. . . . . . . . . 146 6.3 Mean of estimation error for dierent number of interrogationsM , (a) asyn- chronous exclusive estimator, and (b) synchronous exclusive estimator. . . 147 xiv List of Figures 6.4 Standard deviation of estimation error for dierent number of interrogations M when using an asynchronous exclusive estimator. . . . . . . . . . . . . . 148 6.5 Standard deviation of estimation error for dierent number of interrogations M when using the synchronous exclusive estimator. . . . . . . . . . . . . . 149 6.6 The mean of estimation error for varying number of tags, asynchronous and synchronous exclusive estimators. . . . . . . . . . . . . . . . . . . . . . . . 150 6.7 Operational range of asynchronous and synchronous exclusive estimators for varying persistence probabilities. . . . . . . . . . . . . . . . . . . . . . . . . 151 6.8 Standard deviation of error for varying persistence probabilities: (a) asyn- chronous exclusive estimator, (b) synchronous exclusive estimator. . . . . . 152 6.9 Comparison of A-MRCE and S-MRCE in terms of standard deviation of error.153 6.10 Comparing dierent algorithms in terms of interrogation time (number of time slots), (a) mean of estimation error, and (b) standard deviation of estimation error. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 6.11 Comparing the standard deviation of estimation error for A-MRCE, S- MRCE, EZB, and LoF algorithms. . . . . . . . . . . . . . . . . . . . . . . 155 xv List of Abbreviations A-MRCE Asynchronous Multiple Reader Cardinality Estimation ARQ Automatic Repeat Request EMR Evolutionary Minimum Resource EZB Enhanced Zero Based FDMA Frequency Division Multiple Access FEC Forward Error Correction LMM Lexicographical Max-Min Fair LOCL Lexicographically Optimal Commodity Lifetime LOCLR Lexicographically Optimal Commodity Lifetime Routing LoF Lottery Frame LONL Lexicographically Optimal Node Lifetime LONLR Lexicographically Optimal Node Lifetime Routing LONPR Lexicographically Optimal Normalized Power Consumption Routing LP Linear Program MAC Medium Access Control MIP Mixed-Integer Program ML Maximum Likelihood MLMR Maximum Lifetime Minimum Resource MLMR Maximum Lifetime Multiple Sinks xvi List of Abbreviations MLST Maximum Lifetime Steiner Tree NP Non-deterministic Polynomial-time RFID Radio Frequency Identication RLNC Random Linear Network Coding S-MRCE Synchronous Multiple Reader Cardinality Estimation TDMA Time Division Multiple Access WSN Wireless Sensor Network xvii Acknowledgments First and foremost, I oer my sincerest gratitude to my supervisor, Dr. Vincent Wong, for his invaluable advice, insightful guidance, and enormous patience. He has improved the quality of my research and presentation by his constructive comments from the early stages of my research until the very end. He has supported me and encouraged me throughout my PhD study. He introduced me to new ways of thinking, taught me technical writing, and provided me with excellent research topics. I would like to express my gratitude to Dr. Victor Leung and Dr. Robert Schober for their support and help during my PhD program and Dr. Hamed Mohsenian-Rad for his constructive suggestions and guidance. I would also like to thank the members of my doctoral committee for their time and eort. I am also thankful to my fellow labmates and friends at the Communications lab of the Department of Electrical and Computer Engineering at the University of British Columbia who inspired me along the way, especially Mr. Mohammad MohammadNia, Mr. Ehsan Bayaki, Mr. Ali Nezampour, Mr. Keivan Ronasi, and Mr. Man-Hon Cheung. I thank my friends at the University of British Columbia, Mr. Ali Mahmoudzadeh, Ms. Monir Hajiaghayi, and Ms. Maryam Beigi for their continuous support. Lastly, and most importantly, I wish to thank my mom for her support. Without her, I could not achieve this success and nish this road. To her, I dedicate this thesis. I would also like to thank my sister Afsaneh and my brother Hamed. This work was supported by the Natural Sciences and Engineering Research Coun- xviii Acknowledgments cil (NSERC) of Canada, Bell Canada, MITACS, and the University of British Columbia Graduate Fellowship. xix Dedication With love, to my mom. xx Chapter 1 Introduction Wireless sensor networks (WSNs) and radio frequency identication (RFID) systems are two important wireless technologies that have a wide variety of applications and provide limitless future potentials. They consist of thousands of small inexpensive devices with radio frequency technology to provide wireless communication. Because the devices are inexpensive, they have several restrictions including limited power supply and memory storage. Therefore, simplicity and power eciency are two major design goals in such systems. Moreover, the large number of wireless devices requires scalable algorithms. The conventional wireless protocols used for data transmission, collection, and relaying in ad hoc and mesh networks may not be applicable in WSNs and RFID systems. In this thesis, we consider the problem of protocol design for WSNs and RFID systems. In the next subsections, we introduce WSNs and RFID systems and describe the directions of our work. Then, we summarize the mathematical tools that we used in this thesis. 1.1 Wireless Sensor Networks (WSNs) Recent advances in low power integrated circuits, wireless communications, and micro- electro-mechanical systems have sped up the development of various types of low cost wireless sensors, which are the building blocks of WSNs [1]. In WSNs, each sensor node has the capability to sense the environment (e.g., temperature, pressure, light, acoustic), process the data and transmit data packets. The sensors are also capable of relaying infor- 1 Chapter 1. Introduction mation of other sensors. WSNs have a wide range of applications including environment and habit monitoring, home automation, health care applications, and trac control [2]. A WSN is a self-organizing network composed of a large number of sensor nodes de- ployed in a geographical area of interest. The generated information of various sensor nodes is gathered at central processors in the system called sinks. Each source node may transmit its data towards one or multiple sinks at the same time. Due to the short trans- mission range of sensor nodes, multihop communication is exploited instead of single hop communication used in infrastructure-based networks. Wireless sensor nodes are low cost, battery-powered communication devices with limited power supply, memory, and computational capabilities. Because there is a large number of sensor devices in an environment, it is not practical to replace the battery when a sensor node runs out of power. Therefore, it is of interest to prolong the lifetime of the sensors by minimizing the power consumption [3, 4]. Dierent denitions have been proposed for the lifetime of WSNs. The most commonly used denition of lifetime is proposed in [5, 6], where lifetime is dened as the time at which the rst sensor node runs out of energy. Using this denition of lifetime, the maximum lifetime routing problem is formulated as a linear programming problem [6]. However, this problem only considers the case that the information is gathered at a single sink. For the case that several sinks are responsible in data collection, one can dene dierent lifetimes for the data ows towards the various sinks. Since intermediate nodes may relay packets of dierent ows, the maximum lifetime routing problem needs to be restated for WSNs with multiple sinks. In Chapter 2, we study this problem and formulate a mixed integer programming problem to nd the maximum lifetime routing solution for WSNs with multiple sinks. 2 Chapter 1. Introduction 1.1.1 Wireless Sensor Network Terminology In this subsection, we brie y introduce the terminology used in the next four chapters for WSNs. A WSN consists of several sensor nodes with wireless communication capability and one ro several sinks. A source node is a sensor node generating information sent towards the sink(s). The information are sensed by the sensor node from the environment. The source may or may not process data before transmission. A sink in practice is a device with wireless capability and higher computational power with no energy limit compared to the sensor nodes. The sink is responsible for gathering the information from the sources. Intermediate nodes or relay nodes are the sensor nodes which relay information of other sensors towards the sink. A source node can act as an intermediate node to relay packets of other sources as well. Therefore, a source node can be an intermediate node as well. The data ow from various sources towards a sink is called a commodity. An intermediate node may relay packets of various commodities at the same time. A session is referred to the data ow from one source to one or multiple sinks. In Chapters 2 and 3, we consider multipath end-to-end communication between a source and the sink(s). This means, sources and intermediate nodes are allowed to transmit the generated and received packets towards the sink(s) via multiple concurrent paths. The portion of data transmitted on various paths can be dierent in this case. However, in Chapters 4 and 5, we consider single path end- to-end communication. In this case, there is only one path connecting every source node to the sink. This type of end-to-end communication results in a tree network topology. 1.2 Network Coding Network coding refers to the notion of performing coding (e.g., binary addition, XOR) on the content of the packets at intermediate network devices. A network device performs 3 Chapter 1. Introduction network coding when it combines incoming packets which have to reach dierent sinks and creates a coded packet which has to reach the same set of sinks. For multicast and broadcast trac, network coding can lead to substantial improvement in network throughput of wired and wireless networks [7, 8, 9, 10, 11, 12]. It has been shown in [7] that the max- ow min- cut bound on multicast capacity is achievable if nodes are allowed to perform network coding. Li et al. [13] showed that linear codes are sucient to achieve this multicast capacity. It has been shown that random codes can achieve the desired capacity and facilitate distributed implementation [14, 15]. In addition to the throughput gain, network coding can reduce power consumption and congestion by reducing the total number of packets transmitted in the network for unicast and multicast trac. Dierent upper bounds have been derived in [16, 17, 18, 19] for the energy gain of network coding. Consider a directed acyclic graph G = (V;E) modeling the network, where V and E are the set of nodes and links, respectively. Assume that the links have unit capacity. Consider the problem of multicasting from one source to N receivers. Assume that the min-cut capacity from the source to each receiver is h. The source has h packets to transmit to all the receivers which are vectors over nite led Fq. Let Ps = p1s; : : : ; p h s denote the set of source packets. Consider link e 2 E. Let set In(e) denote the set of incoming links to the parent node of link e. Consider a coding vector c(e) = c1(e); : : : ; cjIn(e)j(e) with length jIn(e)j. Each element of the coding vector belongs to the nite eld Fq. Let pi for i = 1; : : : ; jIn(e)j denote the packet received from the i-th input link to the parent node of link i. Then, the following packet is transmitted on link e pe = jIn(e)jX i=1 ci(e)pi: (1.1) This is called linear network coding. If all the network nodes perform linear network coding, receiver j receives h packets denoted as vector = (1; : : : ; h). This vector can be 4 Chapter 1. Introduction represented as a linear combination of source packets = AjPs, where Aj is the transfer matrix from the source to the receiver j with size h h. If intermediate nodes pick the random coecient randomly from the nite eld Fq and the eld size is large enough, the matrix Aj is full rank and the receiver can extract the source packets successfully [20]. The problem of minimum cost multicast for both wired and wireless networks is studied in [21]. In [21], the wireless network is modeled as a hypergraph, which represents the broadcast nature of the wireless links. The performance of network coding using the hypergraph model is investigated in [22]. The problem of supporting multicast over coded packet networks can be divided into two disjoint design problems. The rst problem determines the nodes in the network that perform network coding, which is also referred in the literature to as the problem of determining the coding subgraph. The second problem determines the code that should be used on the coding subgraph. Dierent factors may aect the problem of constructing the coding subgraph in a wireless network. The power consumption, the lifetime of the network, and the rate of performing network coding are aected by the coding subgraph. The problem of constructing a coding subgraph which minimizes power consumption is studied in [21] for wireless networks. The problem of minimizing the rate at which network coding is performed for wired networks is studied in [23]. In Chapter 3, we study the problem of constructing the coding subgraph for WSNs while we jointly maximize the network lifetime and minimize the rate of performing network coding. For a multihop communication session with lossy links, it is shown that if intermediate nodes store the received packets and combine the buered packets to transmit new packets, the reliability of end-to-end communication can be improved. If the coding operations are linear and the coecients used to create coded packets are random variables, then the scheme is called random linear network coding (RLNC). It is shown that RLNC can achieve 5 Chapter 1. Introduction the packet-level (i.e., max- ow min-cut) capacity of a unicast session in the presence of lossy links [24], [25]. To reduce the time required for the sink to decode the packets, the source divides the generated packets into groups called generations. The source(s) and intermediate nodes perform coding operations on the packets of one generation. The sink can decode the packets of one generation as soon as it has enough packets for the decoding. The source(s) and intermediate nodes stop transmission of packets of one generation as soon as they receive a feedback control packet indicating that the sink can decode the packets of that generation. The intermediate nodes can also generate the feedback for their upstream nodes. The feedback mechanism has a direct impact on power consumption of the intermediate nodes. Therefore, it is of interest to design feedback mechanisms that minimize the power consumed to deliver a generation of packets to the sink. In Chapter 4, we design power ecient feedback mechanisms for WSNs using RLNC. We assume that each intermediate node stores the packets of dierent ows towards the sink in a shared buer. We analyze and study the behavior of RLNC with buer sharing and propose two types of feedback mechanisms, namely link-by-link and end-to-end feedback mechanisms. 1.2.1 Network Tomography For both wireless and wired networks, it is of interest to monitor the behavior of the network, identify the link status, and estimate the delay and loss rate of dierent links. Such a technique is called network tomography or network monitoring in the literature. Network tomography for wired and wireless networks has received much attention recently [26, 27, 28, 29, 30]. Network monitoring is especially important for WSNs as the informa- tion can allow sensor nodes to make decisions on routing and to bypass the links which are either congested or prone to failure. Network monitoring can be performed either in an active or passive manner [27]. Active 6 Chapter 1. Introduction network monitoring refers to the case where probe packets are transmitted by some chosen source nodes and are gathered from the sinks. Although active monitoring schemes may reveal more information about the link loss rates, they utilize additional network resources such as bandwidth and energy. On the other hand, for passive network monitoring, infor- mation from the received data packets can allow the sink to infer the link loss information [26]. Passive monitoring schemes are more attractive for WSNs because of the limited power supply in these networks [31, 32]. RLNC used for data collection in WSNs provides a tool for monitoring. The link identication problem in coded packet networks is dierent from routed packet networks. In a coded packet network, the loss rate of a chosen path is the maximum loss rate of all the links of that path [20]. Therefore, it can be infeasible to infer the loss rate of the intermediate links by simply observing the path loss rate from the source node towards the sink. This behavior of the coded packet networks makes the link identication problem more challenging. However, we can benet from the coding operations performed at the intermediate nodes and extract information about the path loss rate from the intermediate nodes to the sink. In Chapter 5, we study the problem of passive loss inference in WSNs using RLNC. By inspecting the contents of the received coded packets at the sink and adopting the subspace properties of network coding, we propose an estimation technique to estimate the path loss rates not only from the source nodes but also from several intermediate nodes to the sink. 1.3 RFID Systems RFID systems are increasingly being deployed as automated identication systems. These systems are expected to play an important role in various applications such as warehouse and supply chain management, object tracking, and patients' monitoring in health care 7 Chapter 1. Introduction facilities [33, 34, 35]. An RFID system consists of a set of readers and several objects. Each object is equipped with a small computer chip, called a tag. Using these inexpensive tags, every object can be uniquely identied. RFID tags can be categorized into passive and active tags. A passive tag uses backscatter modulation; its transmission power is derived from the signal of the interrogating reader [34, 36]. Passive tags can operate in dierent frequency bands. Low-frequency tags operate in the 124-135 kHz band and have an operating range of up to 0.5 m. Ultra high frequency tags, which operate at either 860-960 MHz or 2.45 GHz, have a range in the order of 10 m. Active tags require a power source (e.g., a battery) for data transmission and have a larger range (> 100 m). In an RFID system with one reader and several tags, since the reader and the tags share the same wireless channel, tag-to-tag collision can occur when multiple tags transmit signals simultaneously to the same reader. This prevents the reader from recognizing any tag. Various tag anti-collision protocols are proposed in [37, 38, 39, 40, 41, 42, 43, 44]. An ecient Aloha-based tag anti-collision scheme has also been standardized recently by EPCglobal in [45]. The interrogation time is divided into time slots and called interrogation frame. The reader begins each interrogation round by informing all the tags about the frame size. Each tag then chooses a time slot at random and transmits its identier to the reader. If the frame size is large enough, the probability of tag-to-tag collision can be reduced signicantly. Tag estimation is widely used as a preliminary phase in ALOHA-based interrogation techniques [46, 47, 48]. Readers can adjust the frame size based on the estimation of tag population. Another application of tag estimation techniques, which has recently received attention, is the anonymous tracking of objects [49, 50]. In order to preserve the privacy and anonymity of the tagged users, it may not be necessary to identify each individual user in some RFID applications. Instead, the goal is to estimate the total number of 8 Chapter 1. Introduction tags (or users) in the system. This is called the cardinality estimation (or tag population estimation) problem in RFID systems. The potential applications include estimating the number of attendants in large exhibitions and conferences when each attendant is equipped with an RFID tag, and urban trac monitoring at streets and intersections when cars are equipped with RFID tags. In several RFID applications (e.g., for inventory checking in a large-scale warehouse), it is necessary to deploy several readers to achieve complete interrogation coverage and also to improve read rate and correctness. Since there may be multiple tags in the overlapping coverage area of neighboring readers, the cardinality estimation techniques used for single reader systems are not accurate enough for use in multiple readers systems. In Chapter 6, we study the problem of anonymous cardinality estimation for RFID systems with multiple readers. We propose two estimation methods that are useful under dierent circumstances. 1.4 Mathematical Background In this section, we brie y introduce mathematical frameworks which are used in the rest of this thesis. 1.4.1 Convex Optimization Consider the following optimization problem minimize x2X f0(x) subject to fi(x) 0; 8 i = 1; : : : ; Ni gi(x) = 0; 8 i = 1; : : : ; Ne; (1.2) 9 Chapter 1. Introduction where x is the vector of optimization variables (i.e., x = (x1; : : : ; xN) 2 X ). The function f0 : RN ! R is the objective function, fi : RN ! R for i = 1; : : : ; Ni are the inequality constraint functions, and gi : RN ! R for i = 1; : : : ; Ne are the equality constraint functions. The inequality and equality constraints together determine the feasible region of the optimization problem. If problem (1.2) is convex, the global optimal solution of the problem can be obtained using optimization theory. The key feature of a convex optimization problem is that local optimality implies global optimality. Problem (1.2) is convex if [51] 1. X is a convex set, 2. fi(x) is convex for i = 0; : : : ; Ni, 3. gi(x) is ane for i = 1; : : : ; Ne. The set X is convex if for any x1; x2 2 X and 2 [0; 1], (x1 + (1 )x2) 2 X . A function h(x) : X ! R is convex on X if for any x1; x2 2 X and 2 [0; 1] h(x1 + (1 )x2) h(x1) + (1 )h(x2): (1.3) A function h(x) : X ! R is ane if it has the form h(x) = Ax + b, where A 2 R1N and b 2 R. The Lagrangian function of problem (1.2) is dened by introducing Lagrange multipliers = (1; : : : ; Ni) and = ( 1; : : : ; Ni) as [51] L(x;; ) = f0(x) + NiX i=1 ifi(x) + NeX i=1 igi(x): (1.4) The dual function is obtained using the Lagrangian multiplier as q(; ) = inf x2X L(x;; ): (1.5) 10 Chapter 1. Introduction The dual function is concave even if the primal problem (i.e., problem (1.2)) is not convex. The dual problem is dened as maximize q(; ) subject to i 0; for i = 1; : : : ; Ni: (1.6) Let f ? and q? denote the optimal value of the primal problem (1.2) and dual problem (1.6), respectively. Then, we always have q? f ? regardless of the convexity of the primal problem. Under favorable circumstances, including convexity of the primal problem, we have q? = f ?. This is called strong duality. Suppose that optimization variable x has m components x1; : : : ;xm of dimensions n1; : : : ; nm, respectively. Consider the following optimization problem minimize x2X mX i=1 fi(xi) subject to mX i=1 gij(xi) 0; 8 j = 1; : : : ; Ni mX i=1 hij(xi) = 0; 8 j = 1; : : : ; Ne; xi 2 Xi; 8 i = 1; : : : ;m (1.7) where fi : Xi !R, gij : Xi !R, and hij : Xi !R are given functions. The dual problem of problem (1.8) can be written as maximize ; mX i=1 qi(; ) subject to 0; (1.8) 11 Chapter 1. Introduction where qi(; ) = inf xi2Xi n fi(xi) + PNi j=1 igij(xi) + PNe j=1 ihij(xi) o . Moreover, 0 means that all the elements of vector are greater than or equal to zero. The optimization involved in the calculation of the dual function has been decomposed into m simpler opti- mization. This separation technique is widely used to distributively solve an optimization problem in a network. If m denote the number of nodes in the network, each node i can solve a decomposed dual problem. The subgradient method is a method to nd the minimum value for a nondierentiable convex function. It is similar to the ordinary gradient method for dierentiable functions with some exceptions. In the subgradient method, the step sizes can be xed. Unlike the ordinary gradient method, the subgradient method is not a descent method which means the function value can increase. The subgradient method is slower than Newton's method, but it is much simpler and can be applied to a far wider variety of problems. By combining the subgradient method with dual decomposition technique, it is sometimes possible to develop a simple distributed algorithm for a problem. Suppose f : Rn ! R is convex. To minimize the function f(x) using the subgradient method, we can use an iterative approach where at iteration k + 1 we have, xk+1 = xk k(xk); (1.9) where (xk) is any subgradient of f(x) at xk, and k is the step size of iteration k. The subgradient of function f at x is any vector that satises the inequality f(y) f(x) + T (y x);8 y 2 Rn. A typical step size for the subgradient method is non- summable diminishing step size (i.e., k approaches zero while P k k approaches innity). The step size approaches zero as k grows in this case while the summation of the step sizes is unbounded. A typical example of this step size is k = = p k, where > 0 is a given constant. 12 Chapter 1. Introduction In problem (1.2), if functions fi(x); 8 i = 0; : : : ; Ni and gi(x); 8 i = 1; : : : ; Ne are ane functions of the form fi(x) = a Tx+ b; 8 i = 0; : : : ; Ni; gi(x) = c Tx+ d; 8 i = 1; : : : ; Ne; (1.10) where a and c are vectors of size N , and b and d are scalar values, then the resulting problem is a linear programming problem. Linear programming problems can be solved in polynomial time, which makes them one of the most practical optimization problems. Var- ious optimization techniques including the simplex method and the interior point method can be used to solve linear problems eciently [51]. 1.4.2 Linearization Technique Consider a non-negative real variable x and a binary variable a. The product of these variables can be replaced by a new real variable z. The value of z corresponds to the value of x and a as follows: z = 8><>: 0; if a = 0,x; if a = 1. (1.11) Assume that xmax is an upper bound for the real variable x. The desired correspondence between x, a, and the new variable z is obtained by requiring that [52]: 0 z x; x xmax(1 a) z xmaxa: (1.12) 13 Chapter 1. Introduction 1.4.3 Regularization Technique Consider the following convex optimization problem with variable x: minimize f0(x) subject to fi(x) 0; i = 1; : : : ;m x 0; (1.13) where f0 and fi's can be linear or nonlinear functions. Let p ? denote the optimal value (i.e., minimum value) achieved at an optimal solution x?. That is, p? = f0(x ?). Now consider the following optimization problem: minimize f0(x) + (x) subject to fi(x) 0; i = 1; : : : ;m x 0: (1.14) Mangasarian et al. [53] proved that if problem (1.13) is a linear programming problem, for any convex function (x) and for all values of below some positive threshold, the optimal solutions of the regularized problem (1.14) are also the optimal solution in problem (1.13). Recently in [54], Friedlander et al. extended this work and proved that when the problem is nonlinear, the result still holds. They showed that this threshold is the inverse of the 14 Chapter 1. Introduction Lagrange multiplier of the second inequality constraint in the following problem: minimize (x) subject to fi(x) 0; i = 1; : : : ;m f0(x) p? x 0: (1.15) They proved that this problem always has a Karush-Kuhn-Tucker (KKT ) point. Thus, the threshold always exists. 1.5 Contributions and Results This thesis covers several aspects of energy-ecient protocol design for WSNs. The results are divided into four chapters for WSNs. In the last chapter, we consider the problem of cardinality estimation in RFID systems. The contributions in each chapter are as follows. In Chapter 2, we extend the maximum lifetime routing problem which was originally proposed for WSNs with single sink to the case that there are multiple sinks in the system. In the maximum lifetime routing problem, the goal is to nd a routing so- lution such that the lifetime of the network is maximized. For a WSN with multiple sinks, the data ows towards dierent sinks are called commodities. We dene the lifetime for each commodity individually and formulate the lexicographically optimal commodity lifetime routing problem. We aim to maximize the lifetime of all the commodities with emphasis on commodities with lower lifetime. A stepwise central- ized algorithm, called the lexicographically optimal commodity lifetime algorithm, is proposed which can obtain the optimal routing solution and lead to lexicographical fairness among commodity lifetimes. We then show that under certain assumptions, 15 Chapter 1. Introduction the lexicographical optimality among commodity lifetimes can be achieved by pro- viding lexicographical optimality among node lifetimes. This motivates us to propose our second algorithm, called the lexicographically optimal node lifetime algorithm, which is suitable for practical implementation in contrast to the commodity lifetime solution. Simulation results show that the dierence of both schemes in terms of the commodity lifetime is negligible especially when there are few sinks in the system. The work in Chapter 2 is published in [55, 56, 57, 58]. In Chapter 3, we study the problem of supporting multicast trac in WSNs with network coding. We formulate the maximum-lifetime minimum-resource coding sub- graph problem and study the tradeo between network lifetime and network resources used for coding operations. Our objective is to jointly maximize the network lifetime and minimize the number of packets undergoing network coding when the cost of performing coding varies. We propose the coding ow variables and the maximum lifetime minimum resource (MLMR) algorithm which enable us to determine the type of operations (e.g., forwarding, replication, coding) performed in each sensor node and also the rate at which these operations are performed. Results show that for WSNs with four sinks, the network lifetime can be increased up to 25% using our proposed MLMR algorithm compared with the classical multicast with Steiner tree. The network lifetime and the total rate of performing network coding can also be in- creased by 20% and 30%, respectively, when compared with another algorithm which uses network coding without taking into account the broadcast nature of wireless links. The work in Chapter 3 is published in [59, 60]. In Chapter 4, we consider the use of random linear network coding (RLNC) for wireless sensor networks (WSNs). We study the problem of feedback mechanism design for RLNC where each intermediate node uses a shared buers for various ows 16 Chapter 1. Introduction that it relays. For an intermediate node in the network tree topology, we determine when the node can stop transmission of a particular ow. We analytically show that reducing the transmission rate at this time does not change the rate at which the node transmits the coded packets that carry new information for the downstream neighbor. We propose a novel link-by-link feedback mechanism. In this mechanism, every intermediate node generates a feedback control packets for its upstream neighboring node. We propose three dierent types of end-to-end feedback mechanisms for RLNC with buer. In end-to-end feedback mechanisms, the sink is responsible for generating feedback control packets for all the nodes in the network. Simulation results show that the link-by-link feedback mechanism has better performance in terms of power consumption than the end-to-end feedback mechanism. The results also show the performance gain of using buer sharing compared to RLNC without buer sharing in terms of power consumption. They also show the tradeo between the power consumption and delay when buer sharing is employed in the network. In Chapter 5, we study the passive loss inference problem in WSNs while the data collection is performed using RLNC. We show that by inspecting the content of the coded packets at the sink (i.e., destination), one can estimate the path loss rates not only from the source nodes but also from various intermediate nodes to the sink. By utilizing such information at the sink, we determine the set of links whose loss rates can be identied. We propose a passive loss inference with RLNC (PLI-RLNC) algorithm to estimate the link loss rates. Results show that in coded packet WSNs, our proposed algorithm can identify the status of a higher number of links compared to a Bayesian inference algorithm. The work in Chapter 5 is published in [61]. In Chapter 6, we consider the anonymous cardinality estimation problem in RFID systems. To achieve complete system coverage and increase the accuracy of measure- 17 Chapter 1. Introduction ment, multiple readers with overlapping interrogation zones are deployed. We study the problem under two dierent circumstances. First, we assume that the readers cannot perform interrogations synchronously. This models the case when the readers are not equipped with accurate clocks or synchronization imposes a high overhead. Under such condition, we propose an asynchronous exclusive estimator to estimate the number of tags that are exclusively located in the zone of a selected reader. By using this estimator, we propose an asynchronous multiple-reader cardinality esti- mation (A-MRCE) algorithm. In the second scenario, we assume that readers can perform interrogations synchronously. We propose a synchronous exclusive estima- tor and a synchronous multiple-reader cardinality estimation (S-MRCE) algorithm to estimate the total number of tags. For the exclusive estimators, we show that they are asymptotically unbiased and we derive upper bounds on the variance of error. We validate our analytical model via simulations. Results show that although the A-MRCE algorithm enjoys the asynchronous operation of the readers, it performs worse than the S-MRCE algorithm in terms of estimation error. Compared to the enhanced zero-based (EZB) and lottery frame (LoF) algorithms, the variance of the estimation error for both A-MRCE and S-MRCE algorithms increases linearly with the number of readers, while it increases exponentially for EZB and LoF algorithms. The work in Chapter 6 is published in [62, 63]. 1.6 Thesis Organization The rest of the thesis is organized as follows. In Chapter 2, we study the maximum lifetime routing problem for WSNs with multiple sinks. We present our stepwise centralized algorithm called the lexicographically optimal commodity lifetime algorithm which obtain a routing solution leading to lexicographical fairness among commodity lifetimes. We 18 Chapter 1. Introduction also propose the lexicographically optimal node lifetime algorithm, which is suitable for practical implementation in contrast to the commodity lifetime solution. In Chapter 3, we formulate the maximum-lifetime minimum-resource coding subgraph problem for multicast trac in WSNs. We study the tradeo between network lifetime and network resources used for coding operation. We propose the coding ow variables that enable us to determine the type of operations performed in each sensor node. Then, we present the maximum lifetime minimum resource algorithm used to jointly maximize the network lifetime and minimize the resources used for network coding. In Chapter 4, we present our feedback mechanisms for WSNs using RLNC. We model and analyze the rate at which intermediate nodes transmit coded packets which carry new information when shared buers are used to store the packets of various ows. We propose link-by-link and end-to-end feedback mechanisms based on the proposed models. In Chapter 5, we investigate the problem of passive loss inference in WSNs while RLNC is used for data collection. We propose a passive loss inference with RLNC algorithm to estimate the link loss rates in the network. In Chapter 6, we study the anonymous cardinality estimation problem in an RFID system with several readers. We study the problem under two dierent circumstances. First, we assume that the readers cannot perform interrogations synchronously. We propose an asynchronous exclusive estimator and an asynchronous multiple-reader cardinality estimation algorithm. Next, we assume that readers can perform interrogations synchronously. We propose a synchronous exclusive estimator and a synchronous multiple-reader cardinality estimation algorithm to estimate the total number of tags. Finally, Chapter 7 contains discussions of main results, conclusions, and proposals of future research directions. Each of the main chapters in this thesis is self-contained and included in separate journal articles or conference papers. A review of the related work is given for each chapter accordingly. The notations are dened separately for each chapter. 19 Chapter 2 Lexicographically Optimal Routing for Wireless Sensor Networks with Multiple Sinks Sensor nodes are inexpensive battery-powered devices with wireless capability. One of the design objectives for WSNs is to prolong the lifetime of the network [64]. There are various ways to dene the lifetime of a WSN. It can be dened as the time at which the rst node runs out of energy [65]. This time is equivalent to the time at which the rst routing path is disconnected [66]. In [67], the lifetime is dened as the time at which the maximum number of times a certain data collection function can be carried out. In [68, 69], it is dened as the time at which a region within the WSN is not covered by any nodes. The maximum lifetime routing problem is formulated as a linear programming problem in [65], [5], and [6]. In [70], a distributed algorithm based on dual decomposition is proposed to solve the linear maximum lifetime problem. In [71], the maximum lifetime problem is extended by considering a variable-length TDMA (time division multiple access) frame in the MAC (medium access control) layer. In [72], the utility-lifetime tradeo in the maximum lifetime problem is studied by considering the source rates as variables in the system. In [73], the same problem is studied by considering the scheduling constraints of the link data rates. In [74], the maximum lifetime routing problem is studied for the networks with multiple commodities. A heuristic method is proposed which can achieve a 20 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks Sink 1 Sink 2 First commodity Second commodity Source Source Source Source Relay nodes Figure 2.1: A sample WSN with two sinks. solution close to the optimal solution. In [75], an iterative algorithm is proposed to obtain a lexicographic max-min node lifetime solution. In [76], an iterative centralized algorithm is proposed to nd a Pareto-optimal routing solution for WSNs. As the size of the network increases, it becomes inecient (in terms of power consump- tion) and sometimes impossible (in terms of network capacity) to gather all information into a single sink node. To tackle this problem, one can increase the number of sinks [56, 77, 78, 79, 80, 81]. A sample WSN with two sinks is illustrated in Fig. 2.1, with each source node sending data to the nearest sink. WSNs with multiple sinks have recently received increasing attention. In [77], a multi-sink WSN architecture is proposed where the network is partitioned into clusters. All the sources in a cluster are assigned to send data to the sink designated to that particular cluster. A multi-drain (multi-sink) sensor network is considered in [78]. Data from each source are logged in two distinct drains in order to increase the resiliency to drain failure. In [56], upper and lower bounds for the optimal solution of the multiple sink problem are obtained. It is shown that the bounds are tight for networks with a large number of nodes. In [57], we studied the problem of 21 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks fair resource allocation among dierent commodities in multiple sinks WSNs. The set of nodes sending data to a particular sink is called a commodity. The lifetimes of commodities in a network with multiple sinks are not independent. By changing the routing ows, we can increase or decrease the lifetime for each commodity. One important issue is how to obtain a routing solution that provides fairness among dierent commodity lifetimes. This is the main focus in this chapter. Our proposed algorithms are based on lexicographic optimization (see Section 2.1.1) to achieve fairness. The contributions of this chapter are as follows: We consider the commodity lifetime problem in a WSN with multiple sinks. We formulate this problem as a sequence of optimization problems. We propose a stepwise centralized algorithm, called the lexicographically optimal commodity lifetime (LOCL) algorithm, which lexicographically maximizes the life- time of commodities. By using the LOCL algorithm, for a WSN with four sinks, the average normalized commodity lifetime increases by 100% and 35% compared to maximum lifetime with multiple sinks (MLMS) [74] and lexicographical max-min fair (LMM) [75] algorithms, respectively. We show that, under certain assumptions, a lexicographically optimal commodity life- time problem can be reduced to a lexicographically optimal node lifetime problem. This problem can be solved in polynomial time. We propose the lexicographically optimal node lifetime (LONL) algorithm to solve this problem using a dual decom- position technique. The LONL algorithm is simpler for implementation and more interesting for practical deployment. The rest of this chapter is organized as follows: In Section 2.1, we present the problem formulation and describe our proposed LOCL algorithm. In Section 2.2, we propose the 22 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks LONL algorithm and provide its distributed implementation using the dual decomposi- tion technique. The performance comparisons between LOCL, LONL, MLMS, and LMM algorithms are presented in Section 2.3. A summary is given in Section 2.4. 2.1 Lexicographically Optimal Commodity Lifetime (LOCL) Algorithm In this section, we rst introduce the notations. The lifetime of the commodity and the lexicographically ordered commodity lifetime vectors are dened. We then present the stepwise LOCL algorithm. 2.1.1 System Model Consider a WSN where the sensor nodes are randomly scattered over the coverage area. Each sensor node has limited energy. Nodes can cooperate to relay data towards the sinks. The commodities and the nodes can be considered as the users and resources of the system, respectively. Each sink uses the system resources to gather information within the sensing area. The source nodes in a commodity utilize the energy of the intermediate nodes in the network for a multi-hop transmission towards the sink. Since each node is battery powered, resources in the system are limited. Thus, a fair resource allocation is needed. Our objective is to obtain a routing ow that fairly shares the system resources among commodities. The lexicographic optimality is used as the notion of fairness among the lifetimes of the commodities. Let V denote the set of sensor nodes and C denote the set of sinks collecting information from the network. The data rate generated by source node i to sink k 2 C is denoted by Ski . The total data rate generated by source node i is denoted by Si and is equal to 23 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks P k2C S k i . Let Ni be the set of neighbors of node i 2 V . Let xkij denote the data rate of commodity k 2 C transmitted from node i to node j 2 Ni. The aggregate data rate for the unidirectional logical link from node i to j 2 Ni is denoted by xij and is equal to P k2C x k ij. For notation simplicity, we stack up all xij and denote it as vector x. Let pij denote the power consumed in node i 2 V for transmission of one bit of infor- mation to node j 2 Ni. The maximum data rate between nodes i and j is denoted by Rij. It depends on the capacity of the link and the MAC protocol being used. Let Ei represent the initial energy of node i. The lifetime of sensor node i, Ti(x), is dened as follows: Ti(x) = EiX j2Ni pij X k2C xkij : (2.1) The lifetime of commodity k is dened as the time at which the rst path is disconnected between one of the sources and sink k 2 C. This time is equal to the time at which the rst node carrying information for sink k runs out of its energy. The lifetime of commodity k 2 C under data ow vector x is dened as follows: T k(x) = min ( Ti(x) j i 2 V and X j2Ni xkij > 0 ) ; (2.2) where condition P j2Ni x k ij > 0 assures that node i relays packets of commodity k. A vector T = (T 1; T 2; ; T jCj) is called a lexicographically ordered commodity lifetime vector if T 1 T 2 T jCj. That is, all the elements in the vector are sorted (or arranged) in ascending order. The commodity lifetime vector TÌ‚ is lexicographically greater than vector ~T if and only if there exists i such that TÌ‚ i > ~T i, and for all j < i we have TÌ‚ j = ~T j. As an example, if TÌ‚ = (2; 2; 5; 8) and ~T = (2; 2; 4; 9), then TÌ‚ is lexicographically greater than ~T. Two vectors are lexicographically equal if all of the elements of these two vectors are equal. 24 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks A vector is lexicographically optimal in a set if it is the lexicographically greatest vector in the set. As an example, for the set f(1; 3; 7; 8); (2; 2; 5; 8); (2; 2; 4; 9); (2; 2; 3; 10)g, the vector (2; 2; 5; 8) is the lexicographically optimal vector. Note that for any compact set of Rm, there exists only one lexicographically optimal vector [82]. 2.1.2 Problem Formulation In the LOCL algorithm, the goal is to determine the routing paths and ow rates (i.e., data ow vector x) that lead to the lexicographically optimal feasible lifetime vector. The LOCL algorithm is a stepwise algorithm. In the rst step, the minimum commodity lifetime in the network is maximized. This step may have an innite number of optimal routing solutions. In the second step, among the solutions from the rst step, a solution is chosen that maximizes the second minimum commodity lifetime. The second step may also have an innite number of optimal solutions. In general, in step n of the LOCL algorithm, among the solutions from step (n1), the solution is chosen that maximizes the nth minimum commodity lifetime. In other words, in step n, the nth minimum commodity lifetime is maximized while all lower commodity lifetimes are being maximized. The routing solution in the last step lexicographically maximizes the lifetime of all commodities. Note that the number of steps is equal to or less than the number of commodities. The optimal routing solution in the last step is the lexicographically optimal commodity lifetime routing (LOCLR) solution: Denition 1. A routing ow is LOCLR if the vector of lifetimes of commodities under this routing ow is the lexicographically greatest feasible commodity lifetime vector. LOCLR is the solution of the LOCL algorithm or equivalently the optimal solution of the last step of this algorithm. The last step of the LOCL algorithm may have more than one (i.e., an innite number of) optimal solutions. 25 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks Proposition 1 The lexicographically optimal commodity lifetime vector is unique but the LOCLR solution is not necessarily unique. As we mentioned earlier, the lexicographically optimal commodity lifetime vector in a set is unique [82]. Results in [75] showed that in a lifetime maximization problem, it is possible to have an innite number of optimal solutions. An example can be found in [55]. This example can be extended for the networks with multiple sinks or commodities. 2.1.3 LOCL Algorithm: First Step We now present the rst step of the LOCL algorithm and describe how it can be converted to a linear mixed-integer programming problem. In the rst step, the minimum commodity lifetime is maximized. The problem is as follows: maximize min k2C T k(x) subject to X j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CX k2C xkij Rij; 8 i 2 V ; j 2 Ni xkij 0; 8 i 2 V ; j 2 Ni; k 2 C: (2.3) The rst set of constraints is the ow conservation for each commodity in all of the nodes. The second set of constraints is the data rate limits on each link. The objective function of problem 2.3 is not convex. Therefore, we perform a series of change of variables. To obtain a linear objective function, we introduce an auxiliary scalar variable t, which is a lower bound for the lifetime of the minimum commodity: t minx; k2C T k(x) ) t T k(x); 8 k 2 C: (2.4) 26 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks The objective is to maximize t. Substituting (2.2) in (2.4), and (2.4) in (2.3), the problem becomes maximize t subject to t T k; 8 k 2 C T k = min i2V ( Ti j Ti = Ei=( X j2Ni pij X m2C xmij ) and X j2Ni xkij > 0 ) ; 8 k 2 CX j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CX k2C xkij Rij; 8 i 2 V ; j 2 Ni xkij 0; 8 i 2 V ; j 2 Ni; k 2 C: (2.5) The second constraint in problem (2.5) can be replaced by T k EiP j2Ni P m2C pijx m ij if X j2Ni xkij > 0; 8 i 2 V : (2.6) We replace T k and t by their respective inverses: qk = 1=T k and q = 1=t. The objective is changed from maximizing t to minimizing q. Problem (2.5) can now be written as minimize q subject to qk q; 8 k 2 CX j2Ni X m2C pijx m ij Eiqk; if X j2Ni xkij > 0;8 i 2 V ; k 2 CX j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CX k2C xkij Rij; 8 i 2 V ; j 2 Ni xkij 0; 8 i 2 V ; j 2 Ni; k 2 C: (2.7) 27 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks The second constraint in problem (2.7) is conditional. To obtain a closed-form for this constraint, we multiply both sides of the inequality by ( P j2Ni x k ij). The new constraint is X j2Ni xkij ! X j2Ni X m2C pijx m ij ! X j2Ni xkij ! Eiq k; 8 i 2 V ; k 2 C: (2.8) In (2.8), if P j2Ni x k ij = 0, then both left hand side and right hand side become 0. IfP j2Ni x k ij > 0, then constraint (2.8) is equivalent to: P j2Ni P m2C pijx m ij Eiqk. There- fore, constraint (2.8) is equivalent to the second constraint in (2.7). The constraint in (2.8) is a nonconvex constraint. We use a series of change of variables to replace this constraint with several linear constraints. We introduce an auxiliary boolean variable bki = 8><>: 0; if P j2Ni x k ij = 0 1; if P j2Ni x k ij > 0; (2.9) where bki is equal to 1 when node i carries information of commodity k. We can then map the new boolean variable to rate variables as follows P j2Ni x k ijP j2Ni Rij bki ; 8 i 2 V ; k 2 C: (2.10) Constraint (2.8) can now be written as follows bki X j2Ni X m2C pijx m ij bkiEiqk; 8 i 2 V ; k 2 C: (2.11) This constraint is still nonlinear. We use a linearization technique and convert this con- straint to a set of linear constraints. Details of the linearization technique can be found in 28 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks Section 1.4.2. We dene two new variables ki = b k i X j2Ni X m2C pijx m ij ; 8 i 2 V ; k 2 C ki = b k iEiq k; 8 i 2 V ; k 2 C: (2.12) Constraint (2.11) can be written as ki Ei ki ; 8 i 2 V ; k 2 C: (2.13) A set of constraints is added for each new variable and node i and commodity k 0 ki P j2Ni P m2C pijx m ij ;P j2Ni P m2C pijx m ij (1 bki )Pmaxi ki ; ki bkiPmaxi ; 0 ki qk; qk qkmax(1 bki ) ki qkmaxbki ; (2.14) where Pmaxi = P j2Ni pijRij, and q k max is a loose upper bound for q k. We re-write problem (2.7) with new variables. In this problem, the variables are q, qk, xkij, x m ij , b k i , k i , and k i , 29 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks while Ski , Rij, Ei, pij, P max i , and q k max are the constants: minimize q subject to qk q; 8 k 2 CX j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CP j2Ni x k ijP j2Ni Rij bki ; 8 i 2 V ; k 2 C ki Ei ki ; 8 i 2 V ; k 2 C 0 ki X j2Ni X m2C pijx m ij ; 8 i 2 V ; k 2 CX j2Ni pij X m2C xmij (1 bki )Pmaxi ki ; 8 i 2 V ; k 2 CX k2C xkij Rij; 8 i 2 V ; j 2 Ni ki bkiPmaxi ; 8 i 2 V ; k 2 C 0 ki qk; 8 i 2 V ; k 2 C qk qkmax(1 bki ) ki qkmaxbki ; 8 i 2 V ; k 2 C xkij 0; bki 2 f0; 1g; 8 i 2 V ; j 2 Ni; k 2 C: (2.15) Because of the linearity of the objective function, it is possible to have an innite number of optimal lifetime solutions. To obtain a unique set of commodities with minimum lifetime in this step and the subsequent steps, one can use the regularization method. Details of the regularization method can be found in Section 1.4.3. The regularization term used in problem (2.15) is the Euclidean norm of the commodity inverse lifetime vector which isP k2C qk 2 . Therefore, the objective function for the regularized problem is minimize q + X k2C qk 2 ; (2.16) 30 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks where is the regularization parameter. The work in [53] and [54] proved that when is less than a certain threshold, the optimal solutions of the regularized problem form a subset of the optimal solutions of the problem before regularization. 2.1.4 LOCL Algorithm: Subsequent Steps The rst step in the LOCL algorithm is a linear mixed-integer program (MIP). The feasible set in the second step of the LOCL algorithm is the optimal solution set of the rst step. Similarly, the feasible set in the third step is the optimal solution of the second step, and so on. We call the mixed integer programming problem in step n MIP-n. The following lemma characterizes the feasible region for the problem in step n: Lemma 1 The feasible region of problem MIP-n is nonempty if there exists at least one path between each source and its associated sink. The proof of this lemma is presented in Section 2.5.1. This lemma guarantees that the feasible region in each step, which is the optimal solution set in the previous step, is nonempty. Assume that the minimum lifetime in the rst step (problem (2.15)) is T 1? and the optimal value (inverse of minimum commodity lifetime) is q1?. Let P1 be the set of com- modities that the rst constraint in problem (2.15) is active for them. In the second step, the minimum lifetime among all the commodities except the members of P1 (i.e., CnP1) is maximized subject to the condition that the lifetime of the commodities in P1 is also being maximized. The problem in the second step is similar to problem (2.3) while the objective is modied to be as maximize min k2CnP1 T k(x): 31 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks Also, there is a constraint on the maximization of minimum lifetime. The constraint is T l T 1?; 8 l 2 P1: The problem in the nth step can be formulated with similar changes in the objective function and by including the additional constraints. Let T h? denote the maximum achiev- able value for the hth minimum commodity lifetime (obtained from the hth step). Let Ph denote the set of commodities that their lifetimes are equal to T h? in the hth step. We have Ph = fk j T k = T h? and k 2 Cn Sh1 l=1 Plg. The problem in the nth step is as maximize mink2CnSn1h=1 Ph T k(x) subject to T l T h?; 8 l 2 Ph; h = 1; : : : ; n 1X j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CX k2C xkij Rij; 8 i 2 V ; j 2 Ni (2.17) xkij 0; 8 i 2 V ; j 2 Ni; k 2 C: By letting qh? = 1=T h?, the same series of changes that are applied to problem (2.3) can be applied to problem (2.17). The mixed integer programming problem in step n (i.e., 32 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks MIP-n) is as follows: minimize q subject to qk q; 8 k 2 Cn n1[ h=1 Ph ql qh?; 8 l 2 Ph; h = 1; : : : ; n 1X j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CP j2Ni x k ijP j2Ni Rij bki ; 8 i 2 V ; k 2 C ki Ei ki ; 8 i 2 V ; k 2 C 0 ki X j2Ni X m2C pijx m ij ; 8 i 2 V ; k 2 C (2.18)X j2Ni pij X m2C xmij (1 bki )Pmaxi ki ; 8 i 2 V ; k 2 CX k2C xkij Rij; 8 i 2 V ; j 2 Ni ki bkiPmaxi ; 8 i 2 V ; k 2 C 0 ki qk; 8 i 2 V ; k 2 C qk qkmax(1 bki ) ki qkmaxbki ; 8 i 2 V ; k 2 C xkij 0; bki 2 f0; 1g; 8 i 2 V ; j 2 Ni; k 2 C: Algorithm 2.1 shows the stepwise LOCL algorithm to determine the LOCLR solution. Algorithm 2.1 Stepwise LOCL Algorithm (Centralized) 1: Set n := 1 2: While Sn h=1Ph 6= C 3: Solve MIP-n. 4: Set qn? := Optimal value of MIP-n. 5: Set Pn := fk j qk = qn? and k 2 Cn Sn1 h=1 Phg. 6: Set n := n+ 1. 7: End 33 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks The MIP-1 is problem (2.15). The MIP-n (for n > 1) is problem (2.18). The number of steps in the stepwise LOCL algorithm is less than or equal to the number of commodities. Each iteration of Algorithm 2.1 includes an NP-hard problem. There are ecient commercial software (such as CPLEX [83] and MOSEK [84]) to solve linear mixed-integer problems. Most of them use branch-and-bound algorithm [85]. The linear mixed-integer problem in the nth step of Algorithm 2.1 has jCjjVj binary variables, jCj(2jVj + jLj) real variables, jCj(8jVj + n) inequality constraints, and jCjjVj equality constraints, where L is the set of links in the network. Notice that the computational complexity of a linear mixed-integer problem grows exponentially with the number of its integer (in our case binary) variables [86]. Thus, problem (2.18) can be solved in practice for small-scale and medium-scale WSNs. Next, we propose our second algorithm which is particularly useful for practical deployments of large scale WSNs. 2.2 Lexicographically Optimal Node Lifetime (LONL) Algorithm In (2.2), we dened the lifetime of a commodity k to be the time at which the rst node carrying information in commodity k runs out of energy. In a WSN with a large number of sensor nodes, if the sensor nodes and the sinks are uniformly distributed in the coverage area and all the sensor nodes have the same amount of initial energy, then the rst node which runs out of its energy in commodity k is most likely to be one of the neighbors of sink k. In the rst stage, some sensor nodes that are closer to the sinks will most likely run out of energy. Since they are neighbors of the sinks, they usually carry only information belonging to their commodities. Therefore, their lifetimes are independent of each other. If the above assumptions are valid, then the lexicographically optimal commodity lifetime 34 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks problem can be reduced to a lexicographical optimal node lifetime problem. In this section, we show how to solve the latter in a distributed manner. The proposed algorithm is called the lexicographically optimal node lifetime (LONL) algorithm. Compared to the LOCL algorithm in the previous section, the LONL algorithm is simpler for implementation and more practical for deployment. 2.2.1 System Model Given the list of nodes' lifetimes from equation (2.1), we can determine the corresponding lexicographically ordered node lifetime vector such that T1 T2 TjVj. The concepts of lexicographical ordering and lexicographically greater than are the same as what we dened in Section 2.1.1. Denition 2. A routing is Lexicographically Optimal Node Lifetime Routing (LONLR) if the node lifetime vector under this routing ow is the lexicographically greatest among all feasible node lifetime vectors. We call the inverse of the lifetime of each node the normalized power consumption of the node. Let gi denote the normalized power consumption of node i. The normalized power consumption of node i under data ow vector x = fxkijg is gi(x) = P j2Ni pij P k2C x k ij Ei : (2.19) For simplicity, the vector g = fgig is used to denote the normalized power consumptions of all the nodes. Denition 3. A routing ow is Lexicographically Optimal Normalized Power Con- sumption Routing (LONPR) ow if the normalized power consumption vector under this 35 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks routing ow is the lexicographically smallest feasible normalized power consumption vector. Using the concept of LONPR, we can express the following lemma: Lemma 2 The nodes' lifetimes vectors under LONLR ow (Denition 2) and LONPR ow (Denition 3) are lexicographically equal. The proof of this lemma is provided in Section 2.5.2. It shows that the ith minimum lifetime is equal to the inverse of the ith maximum normalized power consumption for all values of i = 1; : : : ; jVj. We now formulate a convex optimization problem, which leads to the LONPR solution. Consider a convex function f(:) and the following problem: minimize X i2V f(gi) subject to X j2Ni (xkij xkji) = Ski ; 8 i 2 V ; k 2 CX j2Ni pij X k2C xkij = Eigi; 8 i 2 V (2.20)X k2C xkij Rij; 8 i 2 V ; j 2 Ni xkij 0; 8 i 2 V ; j 2 Ni; k 2 C; Problem (2.20) has jVj(jCj+1) (real) variables, jLj(jCj+1) inequality constraints, and jVj(jCj + 1) equality constraints. Since all the constraints are linear and the objective function is convex, the optimization problem in (2.20) is a convex programming problem. There are several schemes that can be used to solve convex optimization problems. They include the gradient projection methods, interior point method, and primal-dual method [87]. Note that the convex programming algorithms have polynomial complexity. That is, 36 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks the run time is no greater than a polynomial function of the problem size (2jVj+jLj)(jCj+1). The theorem below relates problem (2.20) and the LONPR solution. Theorem 1 If h(x) is a dierentiable increasing convex function, then the routing solution of problem (2.20) with f(x) = h(x) approaches the LONPR solution as !1. The proof of this theorem is presented in Section 2.5.3. It can be shown that the LONPR ow solution is not necessarily unique. However, all of the solutions lead to a unique lexicographically ordered node lifetime vector. Based on Theorem 1, the optimal solution of problem (2.20) is the LONPR solution. Based on Lemma 2, the LONPR and LONLR ow solutions lead to the same node lifetime vector. Therefore, the solution of problem (2.20) is indeed the LONLR solution. Problem (2.20) is a tractable convex problem which can be solved in polynomial time. We now propose a distributed solution for this problem. 2.2.2 Distributed Implementation In this section, we present a distributed algorithm to solve problem in (2.20). The technique that we use is dual decomposition [87], which has also been used in [70, 88]. Problem (2.20) is referred as the primal problem. We rst introduce Lagrange multipliers ki for the rst equality constraints in (2.20). The other constraints are local constraints in each node and do not need to be relaxed. The Lagrangian function L(g;x;) is L(g;x;) = X i2V f(gi) + X i2V X k2C ki X j2Ni xkij xkji Si! = X i2V f(gi) + X j2Ni X k2C xkij ki kj X k2C ki Si : 37 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks From the Lagrangian, the dual function and the dual problem can be dened. A sub- gradient algorithm [87] can be used to solve the dual problem. The subgradient algorithm is an iterative algorithm. In iteration , given ki (), k j () for j 2 Ni, and the local information (pij, Ei, Rij), each node i updates x k ij() and g k i () by solving the following problem: minimize f(gi()) + X j2Ni X k2C xkij() ki () kj () X k2C ki ()Si subject to X j2Ni pij X k2C xkij() = Eigi();X k2C xkij() Rij; 8 j 2 Ni xkij() 0; 8 j 2 Ni; k 2 C: (2.21) Algorithm 2.2 shows the distributed LONL algorithm performed in node i. Algorithm 2.2 LONL Algorithm in Node i (Distributed) 1: Set := 1 2: While not converged 3: Solve problem (2.21) to obtain gi() and x k ij() for j 2 Ni, k 2 C. 4: Exchange the values of xkij() with neighboring nodes j 2 Ni. 5: Set ki ( + 1) := k i () () Si P j2Ni xkij() xkji() . 6: Exchange the values of ki ( + 1) with neighboring nodes j 2 Ni. 7: := + 1. 8: End In the above algorithm, () is a positive diminishing step size and is chosen as 1 +1 . The convergence of Algorithm 2.2 is guaranteed by the subgradient method [87]. 38 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 2.3 Performance Evaluation In this section, we evaluate the performance of our proposed LOCL and LONL algorithms. We assume a deterministic path loss model. The power consumed for transmission of one bit from node i to node j (i.e., pij) is 1+ 2d 4 ij, where dij is the physical distance of nodes i and j [6]. We choose 1 = 1 and 2 = 0:1. Each source generates 1 kbps of information. The initial energy of each source node Es is 3 J while the initial energy of non-source node i (i.e., Ei) is 1 J. Nodes use TDMA to access the shared communication channel. The time slots are assigned equally and statically to the dierent links, which have interference with each other. The maximum link rate Rij is 250 kbps for all logical links. 2.3.1 Performance of LOCL Algorithm In the rst experiment, we show the performance of employing multiple sinks. There are 30 sensor nodes randomly deployed in a 50 m 50 m square eld. The transmission range of each node is 10 m. Eight nodes are randomly chosen as the source nodes. Each source sends data to its (physically) closest sink. Fig. 2.2(a) shows the normalized minimum commodity lifetime in the network versus the number of sinks. Each sink is located in one of the four corners in the eld. Results are averaged over 100 simulation runs. The values are normalized with respect to the lifetime of the network with only one sink. Simulation results preditc that the lifetime increases almost linearly as the number of sinks is increased. It can be seen that the minimum commodity lifetime in the network when there are four sinks is almost 500% more compared to the network with one sink. The benet of increasing the number of sinks is evident. Fig. 2.2(b) shows the number of steps performed in the LOCL algorithm versus the number of sinks in the network. When there are four sinks in the network, the average number of steps is about 3.5. This shows the average number of times that the MIP problem should be solved to achieve the optimal solution. 39 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 1 2 3 4 0 1 2 3 4 5 6 7 Number of sinks N or m al iz ed m in im um c om m od ity lif et im e (a) 1 2 3 4 0 0.5 1 1.5 2 2.5 3 3.5 Number of sinks Av er ag e nu m be r o f i te ra tio ns (b) Figure 2.2: LOCL algorithm for network with dierent number of sinks: (a) Minimum commodity lifetime; (b) Average number of iterations in LOCL algorithm. Next, we investigate the performance of the LOCL algorithm with a dierent number of sources. The other simulation settings are the same as in the previous experiment. Fig. 2.3 shows the average normalized commodity lifetime for the commodities under dierent number of sources. When the number of sources increases, the lifetime of each commodity decreases. In this experiment, we assume that there are four dierent types of sources in the network, two sensors of each type. For example, there can be two temperature sensors, 40 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 1 2 3 4 1 1.5 2 2.5 3 3.5 4 Commodity number N or m al iz ed lif et im e of c om m od itie s LOCL with 4 sources LOCL with 8 sources LOCL with 12 sources Figure 2.3: Lifetime of commodities for LOCL algorithm with dierent number of sources. two pressure sensors, two humidity meter sensors, and two air ow sensors. One sink is assigned to gather information for each data type. Sensors are then required to send data to the corresponding sink. Fig. 2.4 shows the normalized lifetime of the commodities. We compare the results when there are dierent types of sensors and the case that each source sends data to the nearest sink. When there are dierent types of sources and all sources are randomly deployed in the sensor area, there are more common nodes among commodities. The correlation between dierent commodities increases. Also, the data packets are traversed over longer paths. Therefore, the lifetime of commodities decreases compared to the case where each node sends data to the nearest sink. 41 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 1 2 3 4 1 1.5 2 2.5 3 3.5 4 Commodity number N or m al iz ed c om m od ity lif et im e Single type of sources Different types of sources Figure 2.4: Lifetime of commodities for LOCL algorithm when there are single and dierent types of sinks. 2.3.2 Performance Comparisons between LOCL, LONL, MLMS, and LMM Algorithms To perform the simulation for the LONL algorithm, we need to choose a function h(gi) a and parameter . We set h(gi) = gi. To choose , we set up an experiment. The network topology is similar to the network used in the rst experiment with two sinks. We increment the value of starting from 1 and solve problem (2.20). Fig. 2.5 shows the average normalized minimum lifetime in the network for 100 simulation runs versus dierent values of . It can be seen that when > 8, the dierence between consecutive lifetime values is less than 1%. We choose = 10 for the subsequent simulation runs. The objective function in problem (2.20) is chosen as f(gi) = g i . To compare our LOCL and LONL algorithms with the existing algorithms in the lit- erature, we implemented the algorithms proposed in [74] and [75]. We solve the corre- 42 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 2 4 6 8 10 12 1 1.2 1.4 1.6 1.8 2 2.2 2.4 2.6 2.8 3 Î³ N or m al iz ed m in im um lif et im e Figure 2.5: Average normalized minimum lifetime in LONL algorithm versus . sponding mixed integer programming problems by using the MOSEK [84] optimization toolbox. There are four sinks and eight sources in the network. In [74], the problem of network lifetime maximization is modeled as a concurrent multi-commodity ow optimiza- tion problem. The problem can be extended to consider the multi-sink case. We modify this algorithm and assume that each source sends data to the closest sink. Note that this makes the comparison to be fair. When there is one sink, this problem is equal to the maximum lifetime routing problem proposed in [65]. We call the modied algorithm the maximum lifetime routing for network with multiple sinks (MLMS). A lexicographical max-min fair (LMM) algorithm is proposed in [75]. This algorithm determines a schedule for the routing ows. We extend this algorithm for WSNs with multiple sinks. We compare the results of LOCL with the rst routing ow of LMM method. Notice that the LOCL algorithm provides one routing ow but not a schedule of routing ows for the network. Since both LOCL and LONL algorithms provide one routing 43 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks ow, we compare these algorithms with the rst routing ow in the schedule of LMM. Fig. 2.6 compares the lifetime of commodities between LOCL, LONL, MLMS, and LMM algorithms. Results show that for the minimum commodity lifetime, all four algorithms provide the same lifetime. For the other commodities, the LOCL algorithm provides a higher lifetime. The dierence between LOCL and LONL algorithms is due to the fact that after the rst node runs out of its energy, the LOCL algorithm tries to maximize the next commodity lifetime while the LONL algorithm tries to maximize the second node lifetime. The second node does not necessarily belong to the second commodity. This happens for the subsequent commodities and leads to dierent results for LOCL and LONL algorithms. The dierence increases as the commodity number increases. The lifetimes for the commodities obtained from the MLMS algorithm are almost equal because this algorithm only maximizes the minimum lifetime in the network. For the LMM algorithm, the rst routing ow from the schedule is compared. Fig. 2.7 compares the lifetime of nodes under LONL, MLMS, and LMM algorithms. The LONL algorithm maximizes the lifetime of all the nodes in the network and consequently has better performance. The LMM algorithm has a better performance compared to the MLMS algorithm. In the MLMS algorithm, only the minimum lifetime is maximized and therefore the lifetimes of other nodes are almost equal. 2.4 Summary Multiple sinks can be employed in a WSN to increase the lifetime of the network. In this chapter, we formulated two algorithms to fairly share the network resources among various commodities and nodes in the system using the concept of lexicographical fairness. We rst proposed the centralized LOCL algorithm to obtain the exact lexicographically optimal solution. LOCL is a stepwise algorithm. In each step, a linear mixed-integer 44 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 1 2 3 4 1 1.5 2 2.5 Commodity number N or m al iz ed lif et im e of c om m od itie s LOCL LONL LMM MLMS Figure 2.6: Lifetime of commodities for LOCL, LONL, LMM, and MLMS algorithms in a network with four sinks. programming problem is being solved. Our second algorithm, called the LONL algorithm, is distributed. It can obtain the optimal solution under certain assumptions, and the sub-optimal solutions in general. The LONL algorithm is easier for implementation and more practical for deployments. Simulation results showed that both LOCL and LONL algorithms have better performance compared to some existing schemes. 2.5 Analytical Proofs 2.5.1 Proof of Lemma 1 We use mathematical induction to prove this lemma. If there is at least one path between each source and its associated sink, the feasible set of problem MIP-1 is nonempty. Con- sequently, the optimal set is also nonempty. If the feasible region of problem MIP-n is 45 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks 1 2 3 4 5 6 7 8 9 10 1 1.5 2 2.5 Node number N or m al iz ed lif et im e of n od es LONL LMM MLMS Figure 2.7: Lifetime of nodes for LONL, LMM, and MLMS algorithms for a network with four sinks. nonempty then its optimal set is nonempty. Since the feasible set of problem MIP-(n+ 1) is the optimal set in problem MIP-n, therefore it is nonempty. 2.5.2 Proof of Lemma 2 We use mathematical induction to prove the following parts: 1. The inverse of the minimum lifetime is equal to the maximum normalized power consumption. 2. If the inverse of the ith minimum lifetime is equal to the ith maximum normalized power consumption, then the inverse of the (i + 1)th minimum lifetime is equal to the (i+ 1)th maximum normalized power consumption. 46 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks Both parts can be proved by contradiction. We only prove part one; the proof for the second part can be derived in a similar manner. Let T1 denote the minimum lifetime (i.e., the maximum achievable value for the minimum lifetime) and g1 denote the maxi- mum normalized power consumption (i.e., the minimum achievable value for the maximum normalized power consumption). Now assume that g1 6= 1T1 . If g1 > 1T1 , it means that it is possible to reduce maximum normalized power consumption to 1 T1 while we have assumed that g1 is the minimum achievable value for the maximum normalized power consumption, which is a contradiction. If g1 < 1 T1 , it means that it is possible to reduce maximum normalized power consumption to 1 T1 while we have assumed that g1 is the minimum achievable value for the maximum normalized power consumption which is a contradiction. It is also a contradiction. 2.5.3 Proof of Theorem 1 The set of constraints in problem (2.20) constructs a closed convex set. Let gmaxi be a loose upper bound for the normalized power consumption of node i 2 V . Let g denote the vector of normalized power consumption and g represent the optimal value of problem (2.20) when f(x) = (h(x)) . The closed feasible set and the loose upper bound constraint construct a compact feasible set for g . Since g is a sequence in a compact set, there exists a subsequence of , f m;m 1g, such that g m converges to some g? as m ! 1, where g? is the limit point of g m . We prove that g? is the lexicographically smallest normalized power consumption vector and is unique. Proof by contradiction: Assume that g? is not the lexicographically optimal solution and g0 is the lexicographically optimal vector. g0 is lexicographically less than g?. It means that, there exists i such that g?j = g 0 j for all j < i and g ? i > g 0 i. Let = g ? i g0i. From the convergence of g m to g?, there exists m0 such that for all m m0, g mn is in the 47 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks -neighborhood of g?n for all n 2 V : g?n g mn g?n + : (2.22) Consider the expression Am dened by: Am = jVjX n=1 (fm (g 0 n) fm (g mn )) ; (2.23) where fm(x) = (h(x)) m . From the optimality of g m , we have Am 0. Since for the values of n < i, the members of two vectors are equal, we have Am = fm (g 0 i) fm (g mi ) + jVjX n=i+1 (fm (g 0 n) fm (g mn )) : (2.24) Since the function fm(x) > 0, we have Am fm (g0i) fm (g mi ) + jVjX n=i+1 fm (g 0 n) = fm (g mi ) + jVjX n=i fm (g 0 n) : (2.25) The vector g0 is lexicographically ordered. Thus, for all n > i; g0n < g 0 i, we have Am fm (g mi ) +Mfm(g0i); (2.26) where M = jVj i+ 1. We know that g0i = g?i . We also use equation (2.22) to obtain Am fm(g?i ) +Mfm(g?i ) = fm(g?i ) 1Mfm(g ? i ) fm(g?i ) : (2.27) 48 Chapter 2. Lexicographically Optimal Routing for WSNs with Multiple Sinks Since can be any number, we choose it such that < . The last term is equal to fm(g ? i ) fm(g?i ) = h(g?i ) h(g?i ) m ; (2.28) where h(x) is an increasing function. When m ! 1 (i.e., m ! 1), this term tends to zero. Therefore, Am 1, which is a contradiction. Note that our proof is related to that of Lemma 3 in [89]. In [89], Mo et al. considered utility maximization problems and proved a similar theorem for max-min fairness; how- ever, here we consider the normalized power consumption minimization problem and the lexicographically optimal is the notion of fairness. 49 Chapter 3 Lifetime-Resource Tradeo for Multicast Trac in Wireless Sensor Networks The focus of this chapter is on constructing the coding subgraph for multicast trac in WSNs. WSNs consist of battery-powered low cost wireless sensor nodes. Sensor nodes typically have limited energy supply, memory and computational capability. Sensor nodes performing network coding require additional capabilities. For example, they need to have more computational capability and memory to perform coding, especially when there is a large number of sessions in the network. Moreover, further complexity is incurred and more power is consumed when network coding is performed in the application layer. Current sensor devices either do not have these capabilities or they can be costly to implement. Hence, it is advantageous to either minimize the rate of network coding operation or limit the number of devices performing network coding in the network. The problem of choosing the minimum set of nodes to perform network coding is NP-hard [90] in general. However, we show that the problem of minimizing the rate of network coding operations can be formulated as a linear programming problem. As mentioned in Chapter 1, the problem of supporting multicast over coded packet networks can be divided into two disjoint design problems. The rst problem determines the nodes in the network that perform network coding, which is also referred in the liter- 50 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs ature as the problem of determining the coding subgraph. The second problem determines the code that should be used on the coding subgraph. A linear programming formulation is used in [21] to construct the minimum cost coding subgraph. A distributed algorithm is proposed in [91] to construct the maximum utility coding subgraph. It has been shown that random codes are useful in achieving the desired capacity and facilitating distributed implementation [14, 92]. For the problem of determining the minimum resource coding subgraph, results in [93] show that for acyclic networks with two sources, the number of nodes required to perform network coding is always less than the number of sinks. However, the results cannot be extended to an arbitrary number of sources. The problem of maximizing network throughput while using the minimum set of nodes to perform network coding is inherently an NP-hard problem. In [90], a heuristic based on a genetic algorithm is used to nd a sub- optimal solution. In [23], the problem of minimizing network coding resources for wired networks is formulated as a linear programming problem. The objective is to minimize the rate at which packets undergo coding in the network. Although this method can provide a distributed solution, it cannot be applied to wireless networks with broadcast links. The problem of constructing the multicast tree for routed packet networks is equivalent to the problem of nding the Steiner tree, which is NP-complete. Due to the complexity of this problem, several heuristics are proposed. A multicast incremental power algorithm is proposed in [94] to construct a multicast tree for wireless networks while exploiting the broadcast nature of the wireless links. Interestingly, the problem of constructing the coding subgraph can be formulated as a linear programming problem for coded packet networks. This problem can be solved in polynomial time and it is suitable for distributed implementation. In this chapter, we formulate the maximum-lifetime minimum-resource (MLMR) coding 51 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs subgraph problem to support multicast trac in WSNs with network coding. We propose an MLMR algorithm to determine the rate of performing network coding in each sensor node. The contributions of this chapter are as follows: We propose the coding ow variables, which are a new representation for the set of information ow and actual rate variables. The coding ow variables enable us to determine the type of operation(s) (i.e., forwarding, replication, or network coding) performed in each wireless sensor node. These variables can also determine the rate of performing network coding and replication in each sensor node. We formulate a linear programming optimization problem for joint maximization of the network lifetime and minimization of the rate of performing network coding. We propose the MLMR algorithm which enables us to study the tradeo between maximizing the network lifetime and minimizing the rate of coding operations. We present two model extensions including the case when the objective is to minimize the number of sensors performing network coding and the case when only a xed number of sensor nodes are capable of performing network coding. We investigate the lifetime-resource tradeo in the network. Simulation results show that the network lifetime can considerably be improved when the cost of performing network coding is relatively low compared to the case that this cost is high for intermediate nodes in the network. The rest of this chapter is organized as follows: In Section 3.1, we introduce the no- tations and system model. In Section 3.2, we describe our proposed coding ow variables and formulate the joint maximum lifetime minimum resource coding subgraph problem. We present our proposed MLMR algorithm. The model extensions are also described. In 52 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs Section 3.3, we evaluate the performance of our proposed MLMR algorithm and compare it with three other algorithms [23], [95], [96]. A summary is given in Section 3.4. 3.1 System Model We represent the WSN as a hypergraph, which can eectively model the broadcast nature of wireless links. Let H = (V ;A) denote a directed hypergraph, where V is the set of nodes and A is the set of hyperarcs. Let Ni denote the set of neighbors of node i 2 V . We assume that is given in the network. In can be calculated by the sink using the geographical information of the sensor node. A hyperarc is a pair (i;J ) representing a broadcast link from node i to the subset of neighboring nodes J Ni. Let Ii denote the power set (i.e., the set of all subsets of a given set) of set Ni except the empty set. The set of hyperarcs in the network can be represented as A = f(i;J ) j i 2 V ; J 2 Iig: Let Aini denote the set of all incoming hyperarcs of node i 2 V . These are the hyperarcs including node i as the destination: Aini = f(j; I) 2 A j i 2 Ig: The cardinality of hyperarc (i;J ) is equal to jJ j, which is the number of elements in set J . Let S denote the set of source nodes in the network and Ds denote the set of sinks to which source s 2 S sends data. We call source s with its respective sinks as session s. Let gsdiJ j denote the information ow rate of session s from node i to node j 2 J through hyperarc (i;J ) towards sink d 2 Ds. Let zsiJ denote the actual rate at which the data of 53 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs session s is sent on hyperarc (i;J ). This variable represents the data rate sent on hyperarc (i;J ) after performing coding at node i. The actual rate vector z = fzsiJ g is called the coding subgraph of the network. When node i performs network coding on packets of session s, it combines several incoming packets of this session destined for dierent sinks and transmits one coded packet. Such a coded packet should reach all the sinks that the original packets had been destined for. This happens by means of replication on the route of the coded packet to the sinks of session s. Node i sends a packet on hyperarc (i;J ) with cardinality greater than one if the packet needs to reach dierent sinks through dierent neighbors in set J . In case that the coded packet is sent on a hyperarc and this coded packet traverses dierent routes to the sinks, replication is not performed. The following lemma shows that it is not necessary to consider all the hyperarcs in the network graph to obtain the coding subgraph. Lemma 3 It is not necessary to consider hyperarcs with cardinality greater than jDsj (i.e., the number of sinks of session s) to obtain the coding subgraph of session s. Proof For session s 2 S, let bsDiJ denote a packet sent on the hyperarc (i;J ) destined for the sinks in D Ds. For node i and outgoing hyperarc J 2 Ii, the coded packet bsDiJ is created by combining several packets as follows: bsDiJ = X j2J !ijb sDj ij ; (3.1) where b sDj ij is a packet of session s destined for the set of destinations in Dj Ds and it is sent from node i to j if hyperarc (i;J ) is not used. If jDjj > 1, then the packet bsDjij is a coded packet. !ij is the coding coecient (chosen from a Galois eld) that node i used for packet b sDj ij . We notice that set D is the union of sets Dj (i.e., D = S j2J Dj). Since the packets destined for the same destinations cannot be combined, the sets Dj 54 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs should be disjoint for dierent j 2 J . The number of such packets is jJ j while the number of destinations in session s is jDsj. Hence, the maximum number of packets which are combined can be at most jDsj (i.e., jJ j jDsj). Therefore, node i does not send any packet on hyperarc (i;J ) if jJ j > jDsj (i.e., zsiJ = 0). Consequently, it is not necessary to consider these hyperarcs to obtain the coding subgraph of session s. Based on Lemma 3 and the denition of A, Aini , and Ii, for session s, we dene the following sets: ~As = f(i;J ) j (i;J ) 2 A; jJ j jDsjg; (3.2) ~Ain;si = f(j; I) j (j; I) 2 Aini ; jIj jDsjg; i 2 V (3.3) ~Isi = fJ 2 Ii j jJ j jDsjg; i 2 V : (3.4) In WSNs, each node has a large number of neighboring nodes while the number of sinks gathering information in each session is limited. Therefore, the number of variables in the system can be considerably reduced by removing the hyperarcs with cardinality greater than jDsj. 3.1.1 System Constraints There are several constraints in our problem formulation. Let rs denote the data generation rate by source node s 2 S. The ow conservation constraint in node i 2 V for data sent from source s towards sink d 2 Ds is X J~Isi X j2J gsdiJ j X (j;I)2 ~Ain;si gsdjIi = i; (3.5) 55 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs where i = 8>>>><>>>>: rs; if i = s; rs; if i = d; 0; otherwise: This constraint guarantees that the outgoing information ow rate from node i is equal to the input rate plus the rate of information generated by node i for session s. By the ow-sharing property of network coding and the broadcast nature of a wireless channels, the actual ow rate on each hyperarc needs only be the maximum of the individual sinks ows. The actual rate constraint for session s on hyperarc (i;J ) can be expressed as [21] zsiJ X j2J gsdiJ j; 8 d 2 Ds: (3.6) We extend the protocol interference model in multi-hop wireless networks to hyper- graph. Let (i; j) and (i; j) denote the communication range and interference range be- tween nodes i and j, respectively. Let (i;J ) = maxj2J (i; j) and (i;J ) = maxj2J (i; j) denote the communication range and interference range between node i and the farthest node in set J , respectively. Two hyperarcs (i1;J1) and (i2;J2) interfere with each other (i.e., cannot be active simultaneously) if any of the following conditions are satised: (a) i1 = i2, (b) there exists j 2 J1 such that (i2; j) (i2;J2), (c) there exists j 2 J2 such that (i1; j) (i1;J1). The concept of contention graph and maximal clique [97] can also be extended to a hypergraph. In a contention hypergraph, each node corresponds to a hyperarc. There is an edge between two hyperarcs if they cannot be active simultaneously. The maximal cliques in a hypergraph can be determined accordingly. Let C denote the ordered set of all maximal cliques, with Ck representing the kth element in set C. The link scheduling 56 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs constraints are X f(i;J ); s j (i;J )2Ck; s2S; and (i;J )2 ~Asg zsiJ =ciJ k; k = 1; : : : ; jCj (3.7) and jCjX k=1 k 1; (3.8) where k represents the fraction of time that hyperarcs in set Ck can be active, ciJ = minj2J cij is the capacity of hyperarc (i;J ), and cij is the capacity of the link between node i and j. The network lifetime is dened as the time when the rst node runs out of its energy [6, 70, 98]. Whenever a sensor node is no longer operational, the coding subgraph is updated based on the new network topology and the remaining energy of the active sensor nodes. Nodes employ power control to save energy. The transmission power of a sender is adjusted based on the distance of the two nodes. Let Ei denote the initial energy of node i and piJ represent the power consumed to transmit one bit of data on hyperarc (i;J ). This is equal to the power consumed to transmit data to the farthest node in set J . Thus, piJ = maxj2J pij, where pij is the power consumed to transmit one bit of data from node i to j. For node j to receive the bit successfully, it requires that the received power pr = pt=d(i; j) a > 2, where d(i; j) is the distance between nodes i and j, a is the path loss exponent with 2 a 4, and 2 is a threshold value. The total transmit power is given by [6, 70, 95, 98]: pij = 1 + 2d(i; j) a, where 1 is the power consumed in the transmitter circuitry. Given the maximum transmission power pmax, the corresponding communication range (i; j) can be determined. 57 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs Given Ei and piJ , the lifetime of node i under actual rate vector z = fzsiJ g is i(z) = EiP s2S P J2~Isi piJ z s iJ ; 8 i 2 V : (3.9) Let q denote an upper bound on the inverse of the lifetime of all the nodes (i.e., 1=i(z) q, for all i 2 V). Minimizing the variable q is equivalent to maximizing the minimum node's lifetime in the network (i.e., max mini2V i(z) = min q). Using equation (3.9), the network lifetime constraint can be expressed as X s2S X J2~Isi piJ zsiJ Eiq; 8 i 2 V : (3.10) Considering the constraints introduced on the information ow rate and the actual rate variables, the coding subgraph of the network is characterized in [7, Theorem 2], which we reproduce here, slightly adapted: Theorem 2 The actual rate vector z = fzsiJ g is part of the set constructed by the con- straints (3.5)(3.8) and (3.10) if and only if there exists a network code for each session s that sets up a multicast connection at a rate arbitrarily close to rs. Since designing codes for optimal inter-session coding for practical wireless networks is an active and open research area, we restrict network coding operation within sessions (i.e., intra-session coding) in this chapter. The only relation between various sessions is imposed by the link scheduling constraint in (3.7)-(3.8). In practice, random linear network coding can achieve the rate of multicast connection rs while it can be performed distributively in the network. Nodes on the coding subgraph which are responsible for network coding select the coding coecients randomly from a Galois eld GF(2u) and combine the incoming packets with the corresponding rate. Sinks can decode the received packets with probability close to one for large values of u [99]. 58 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 3.2 Problem Formulation Our goal is to formulate the joint problem of maximizing the network lifetime and min- imizing the rate of performing coding operations. On one hand, higher rates of coding operations require more resources and capabilities in the system. On the other hand, a larger number of packets undergoing network coding reduce the total number of packet transmissions in the network. This decreases the average power consumption. Conse- quently, network lifetime can be increased when the rate of coding operations increases. To formulate this problem, it is necessary to determine the rate of coding operations at each network device. The information ow and actual rate variables alone are not sucient to determine the corresponding rates on the incoming and outgoing hyperarcs of each node. 3.2.1 Maximum Lifetime Minimum Resource Problem In this section, we introduce a new set of variables which allows us to determine the type of the operations and the rate at which these operations are performed by each node. Let Ps denote the power set of Ds except the empty set. For simplicity, we label the sinks of session s by positive integers. For example, if session s has three sinks, then Ds = f1; 2; 3g and Ps = ff1g; f2g; f3g; f1; 2g; f1; 3g, f2; 3g; f1; 2; 3gg. For hyperarc (i;J ), we x the ordering of the nodes in J . Let jm denote the mth member of J . We now introduce the coding ow variables nsiJ . We show that using this variable, one can obtain the rate of performing coding at each sensor node. For session s, hyperarc (i;J ), and P1; : : : ; PjJ j 2 Ps, let nsiJ (P1; : : : ; PjJ j) represent the rate of transmission of packets which are forwarded towards sinks in set Pm by neighbor jm for m = 1; : : : ; jJ j. These packets have to reach the sinks in set SjJ j m=1 Pm via dierent neighbors of node i. The size of the coding variable for each hyperarc depends on the cardinality of the hyperarc. For example, for hyperarc (i;J ) with cardinality two, the coding ow variable is nsiJ (P1; P2), 59 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs h1 s h2 h3 d1 d2 Figure 3.1: Sample network with the source node s and two sinks (d1, d2). where P1 and P2 2 Ps. For illustration purpose, consider Fig. 3.1. Nodes h1 and h2 has two outgoing links while node h3 has one outgoing hyperarc. Node s is the source and nodes d1 and d2 are the sinks. Assume that node h3 sends one packet per second towards d1 and one packet per second towards d2. Node h3 can combine these packets and send one packet over hyperarc (h3;J ) where J = fd1; d2g. Then, we have nsiJ (P1; P2) = 1, where P1 = fd1g and P2 = fd2g. A coded packet is routed towards a sink only from one path. It implies that for coding ow variable nsiJ (P1; : : : ; PjJ j), the sets P1; : : : ; PjJ j are disjoint (i.e., Pa \Pb = ; for a; b = 1; : : : ; jJ j; a 6= b). Let P siJ denote the set of all disjoint subsets of Ps with jJ j members. Let P siJ (d;m) denote the set of members of P s iJ while d 2 Pm. These sets can be dened as follows: P siJ = f(P1; : : : ; PjJ j) j P1; : : : ; PjJ j 2 Ps and Pa \ Pb = ; for a; b = 1; : : : ; jJ j; a 6= bg; 60 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs P siJ (d;m) = f(P1; : : : ; PjJ j) 2 P siJ j d 2 Pmg; m = 1; : : : ; jJ j: (3.11) For example, consider hyperarc (i;J ) with cardinality two (i.e., J = fj1; j2g) and session s with two sinks, namely sink 1 and 2. Then, we have P siJ = f(f1g; f2g); (f2g; f1g)g, P siJ (1; 1) = P s iJ (2; 2) = f(f1g; f2g)g, and P siJ (1; 2) = P siJ (2; 1) = f(f2g; f1g)g. We now show how to relate the information ow variables gsdiJ j to the coding ow vari- ables nsiJ . For simplicity, we assume that the size of each packet isM bits. The information ow variable gsdiJ jm is equal to the packet size (i.e.,M) times the total rate at which packets which have to reach sink d of session s through neighbor jm (i.e., 8 nsiJ (P1; : : : ; PjJ j) while d 2 Pm). The relation between coding ow and information ow variables can be expressed as gsdiJ jm =M X (P1;:::;PjJ j)2P siJ (d;m) nsiJ (P1; : : : ; PjJ j): (3.12) For illustration purpose, consider the following example. Assume that there are three sinks in session s, namely 1; 2; 3. For hyperarc (i;J ) with cardinality two (i.e., J = fj1; j2g), equation (3.12) can be written for sink 1 and neighbors j1 and j2 as follows: gs1iJ j1 M = X (P1;P2)2P siJ (1;1) nsiJ (P1; P2) (3.13) = X fP1;P22Ps j P1\P2=;; 12P1g nsiJ (P1; P2) = nsiJ (f1g; f2g) + nsiJ (f1g; f3g) + nsiJ (f1g; f2; 3g) + nsiJ (f1; 2g; f3g) +nsiJ (f1; 3g; f2g); 61 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs gs1iJ j2 M = X (P1;P2)2P siJ (1;2) nsiJ (P1; P2) (3.14) = X fP1;P22Ps j P1\P2=;; 12P2g nsiJ (P1; P2) = nsiJ (f2g; f1g)+nsiJ (f3g; f1g)+nsiJ (f2; 3g; f1g) + nsiJ (f3g; f1; 2g) +nsiJ (f2g; f1; 3g): The actual rate of hyperarc (i;J ) is the summation of the rate of packet transmissions towards all the sinks (i.e., all the coding ow variables of that hyperarc multiplied by the packet size) as: zsiJ =M X (P1;:::;PjJ j)2P siJ nsiJ (P1; : : : ; PjJ j): (3.15) Consider the following example. Assume that there are three sinks in session s, namely 1; 2; 3. Consider hyperarc (i;J ) with cardinality two (i.e., J = fj1; j2g). The actual rate on this hyperarc is the summation of all coding ow variables multiplied by the packet size as follows: zsiJ = M nsiJ (f1g; f2; 3g) + nsiJ (f2g; f1; 3g) + nsiJ (f3g; f1; 2g) + nsiJ (f1; 2g; f3g) +nsiJ (f1; 3g; f2g) + nsiJ (f2; 3g; f1g) : Fig. 3.2 shows a sample network with three sinks and one source node. The source is generating information with a rate of 2 units per second and the data is sent towards all three sinks. The packet size is assumed to be one. The information ow, actual rate, and coding ow values of all hyperarcs plus the paths that packets travel are shown on each hyperarc. Equations (3.12) and (3.15) imply that the information ow and actual rate variables 62 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 2 s 5 7 d1 d3 4 6 (a) (1,1,0) (0,1,1) (0,1,0) (1,0,0) (0,0,1) (0,0,1) (1,0,0) (0,1,0) (0,0,1)(1,0,0) (1,1,0) (0,1,1) (0,1,0) (0,0,1)(1,0,0) (0,1,0) d2 31 2 s 3 5 7 d1 d3 1 4 6 d2 1 1 1 1 1 1 11 1 1 11 (b) s 5 d1 d3 1 4 d2 n({1,2},{3})=1 n({1},{2,3})=1 n({3})=1n({1})=1 n({2})=1n({2})=1 n({1})=1 n({3})=1n({1,2})=1 n({2,3})=1 n({1},{2})=1 n({2},{3})=1 76 (c) 2 3 2 s 3 5 7 d1 d3 1 4 6 b1 b2 b1 b1 b2 b2b1+2b2 2b1+b2 2b1+b2 b1b2 d2 (d) b1+2b2 Figure 3.2: Network with three sinks (d1, d2, d3) and one source node s with data generation rate of 2 units per second. (a) Information ow values, (b) coding subgraph (actual rate values), (c) coding ow values, (d) multipath packet transmission. are dependent variables while the coding ow variables are independent variables. We keep these dependent variables since they make the presentation of the formulation clear and easier to understand. The coding ow variables provide information on the packet transmission rates for dierent disjoint sets of sinks on each hyperarc. We can determine the type of operation performed in node i by inspecting variables nsiJ . Let s i (R) denote the total rate at which node i sends coded packets which have to reach sinks in set R 2 Ps on the outgoing 63 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs hyperarcs. Let siJ (R) denote the rate at which these packets are sent on hyperarc (i;J ). Variable si (R) is the summation of variables s iJ (R) over all outgoing hyperarcs of node i (i.e., (i;J ); J 2 ~Isi ). The coding ow variable nsiJ (P1; : : : ; PjJ j) is dened as the rate at which packets which have to reach sinks in set S m Pm are sent over hyperarc (i;J ). Therefore, the rate at which node i sends coded packets which have to reach sinks in set R 2 Ps over hyperarc (i;J ) is equal to the summation of coding ow variables nsiJ (P1; : : : ; PjJ j) such that S m Pm = R. This can be expressed as si (R) = X J2~Isi siJ (R) = X J2~Isi X f(P1;:::;PjJ j)2P siJ j S m Pm=Rg nsiJ (P1; : : : ; PjJ j): (3.16) Let si (R) denote the rate at which node i receives coded packets which have to reach the sinks in set R 2 Ps. This is equal to the summation of rate of those packets over all incoming hyperarcs of node i (i.e., (j; I) 2 ~Ain;si ). For hyperarc (j; I), which is an incoming hyperarc of node i, the coding variable nsjI(P1; : : : ; PjIj) contains the information of sinks in set R for node i if there exists v 2 f1; : : : ; jIjg such that i = Iv (i.e., i is the vth member of set I) and Pv = R. Therefore, we have si (R) = X (j;I)2 ~Ain;si X f(P1;:::;PjIj)2P sjI j v2f1;:::;jIjg; Pv=R; i=Ivg nsjI(P1; : : : ; PjIj): (3.17) Variables si (R) and s i (R) represent the rate at which node i sends and receives packets destined for the sinks in set R. The value of si (R) is less than s i (R) if node i combines received packets destined for sinks in set R and creates a coded packet. On the other hand, the value of si (R) is greater than s i (R) if node i replicates a coded packet towards the sinks in set R. From these variables, we can determine the rate at which node i performs coding or replication on the packets destined for dierent sets of sinks. Let T s denote the set of all collections of two or more disjoint subsets of Ps. Any replication or 64 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs coding operation performed at each node corresponds to one of the members of T s. Node i performs replication with respect to set T 2 T s if it transmits jT j copies of a coded packet to jT j dierent neighbors. Each copy is transmitted towards the sinks in a member of T . Node i performs coding with respect to set T if it combines jT j incoming packets which have to reach sinks in members of T and sends one coded packet. For example, for a network with three sinks, we have T s = fff1g; f2gg; ff1g; f3gg; ff2g; f3gg; ff1g; f2; 3gg, ff2g; f1; 3gg; ff3g; f1; 2gg; ff1g; f2g; f3ggg. If node i receives three packets which have to reach sinks 1, 2, and 3 and creates one coded packet which have to reach the sinks in set f1; 2; 3g, then it performs coding with respect to set ff1g; f2g; f3gg. As another example, assume that node i receives one packet which has to reach the sinks in set f1; 2; 3g and replicates two packets. One of the packets is sent towards sinks f1; 2g and the other one is sent towards sink 3. In this case, node i performs replication with respect to set ff1; 2g; f3gg. Let si (T ) and s i (T ) denote the rate of performing replication and network coding with respect to set T 2 T s, respectively. The nal step in determining the rate of performing network coding is to relate variables si (T ) and s i (T ) to variables s i (R) and s i (R). In general, for node i 2 V , session s 2 S, and set R 2 Ps, we have si (R) si (R) = X fT2T s j R2Tg si (T ) si (T ) X fT2T s j [t2T t=Rg si (T ) si (T ) : (3.18) Equation (3.18) which quanties the amount of coding and replication operations is a ow conservation constraint. In (3.18), the output rate minus the input rate is equal to the rate at which packets are generated for packets which have similar destinations. In (3.18), the left hand side is the dierence between the output and input rate for the packets which have to reach the sinks in set R. On the right hand side, the term P fT2T s j R2Tg s i (T ) denotes the rate of replication operations creating outgoing packets that have to reach the sinks in 65 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs set R, the term P fT2T s j R2Tg s i (T ) denotes the rate of coding operations performed on incoming packets that have to reach the sinks in set R, the term P fT2T s j [t2T t=Rg s i (T ) denotes the rate of replication operations performed on incoming packets that have to reach the sinks in set R, and the last term P fT2T s j [t2T t=Rg s i (T ) denotes the rate of coding operations creating outgoing packets that have to reach the sinks in set R. As an example, consider the network in Fig. 3.2 (d). The source transmits two packets b1 and b2 towards the sinks. Node 2 performs routing, nodes 6 and 7 broadcast received packets using the corresponding outgoing hyperarc, nodes 1 and 3 replicate packets, and nodes 4 and 5 perform network coding. Node 1 receives b1 destined for sinks d1 and d2. It replicates one copy of the packet to sink d1 and one to node 4. The second packet should reach sink d2. For this node, we have 1(ff1g; f2gg) = 1. Similarly, we have 3(ff2g; f3gg) = 1 for node 3. Node 4 receives packet b1 destined for d2 and packet b2 destined for d1. It combines these packets using coding coecients 1 and 2 for b1 and b2, respectively. A coded packet is transmitted to node 6. Therefore, we have 4(ff1g; f2gg) = 1. Similarly, node 5 uses coding coecients 2 and 1 to combine b1 and b2, respectively. We have 7(ff2g; f3gg) = 1 for node 3. Note that in (3.18), the outgoing and incoming rates of packet transmission and recep- tion (i.e., si (R) and s i (R), respectively) are given. These rates are obtained using the coding ow variables in (3.16) and (3.17). Moreover, equations (3.12) and (3.15) relate the coding ow variables to the actual rate and information ow rate. Therefore, if the actual rate and ow information rate satisfy the constraints in (3.5)(3.8) and (3.10), then the rates of coding and replication obtained from (3.18) will also satisfy those constraints. From Theorem 2, it is guaranteed that there exists a network code achieving these rates. Linear random network coding can be used to achieve the rates obtained from (3.18). As an example, we show how linear random network coding can be used in the network 66 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs while nodes perform both coding and routing. Consider the network in Fig. 3.1. Assume that the source transmits two packets per second towards sinks d1 and d2. One of them is sent via node h1 and the other is sent via node h2. Nodes h1 and h2 replicate those packets to node h3 and also to sinks d1 and d2, respectively. Every second, node h3 receives two dierent packets destined for sinks d1 and d2. Node h3 can either use network coding and transmit one coded packet on a hyperarc including sinks d1 and d2, or it can perform routing and transmit them separately. Assume that as a solution of problem (3.20), the rate of performing network coding at node h3 is 1/2 per second. In this case, node h3 transmits a coded packet every two seconds while transmitting two separate packets at other times. The coded packet is constructed by randomly selecting two coecients and combining two packets using the coecients. In this case, node h3 performs both network coding and routing with rate 1/2. Equation (3.18) shows a linear relation between variables si and s i and also s i and si . This equation is internal to each node. Both the input and output coding rates and the rate of coding and replications are variables of the joint problem. Therefore, given si and s i , the values of s i and s i cannot be uniquely determined using this set of linear equations. We select the objective function of the joint problem such that we can nd the optimal rate of coding operations among feasible solutions. The total rate of performing network coding is X s2S X i2Vnfsg X T2T s si (T ): Note that source s does not perform coding on the packets that it generates. In the maximum lifetime minimum resource coding subgraph problem, the objective is to minimize q + X s2S X i2Vnfsg X T2T s si (T ); (3.19) 67 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs where is the cost of performing network coding. The unit of depends on the unit of i in (3.5). The value of the tuning parameter determines the eect of each part in the joint objective function. The feasible set of the joint coding subgraph problem is constructed by equations (3.5), (3.7), (3.8), (3.10), (3.12), and (3.15)(3.18). Problem (3.20) is the maximum lifetime minimum resource coding subgraph problem. This is a linear programming problem. It can be solved by various techniques such as the simplex 68 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs method. minimize q + X s2S X i2Vnfsg X T2T s si (T ) subject toX J~Isi X j2J gsdiJ j X (j;I)2 ~Ain;si gsdjIi = i; 8 i 2 V ; d 2 Ds; s 2 S X f(i;J ); s j (i;J )2Ck; s2S; and (i;J )2 ~Asg zsiJ =ciJ k; k = 1; : : : ; jCj; jCjX k=1 k 1;X s2S X J2~Isi piJ zsiJ Eiq; 8 i 2 V gsdiJ jm M = X (P1;:::;PjJ j)2P siJ (d;m) nsiJ (P1; : : : ; PjJ j); 8 (i;J ) 2 ~As;m = 1; : : : ; jJ j; d 2 Ds; s 2 S zsiJ =M X (P1;:::;PjJ j)2P siJ nsiJ (P1; : : : ; PjJ j); 8 (i;J ) 2 ~As; s 2 S (3.20) si (R) = X J2~Isi X f(P1;:::;PjJ j)2P siJ j S m Pm=Rg nsiJ (P1; : : : ; PjJ j); 8 i 2 V ; s 2 S; R 2 Ps si (R) = X (j;I)2 ~Ain;si X f(P1;:::;PjIj)2P sjI j v2f1;:::;jIjg; Pv=R; i=Ivg nsjI(P1; : : : ; PjIj); 8 i 2 V ; s 2 S; R 2 Ps si (R) = s i (R) + X fT2T s j R2Tg si (T ) si (T ) X fT2T s j [t2T t=Rg si (T ) si (T ) ;8R 2 Ps; i 2 V ; s 2 S nsiJ (P1; : : : ; P s jJ j) 0; si (T ) 0; si (T ) 0; k 0; q 0; 8 (i;J ) 2 ~As; (P1; : : : ; P sjJ j) 2 Ps; T 2 T s; s 2 S; k = 1; : : : ; jCj: From Theorem 2, it follows that the solution of problem (3.20) is the maximum lifetime minimum resource coding subgraph for an asymptotically achievable rate for multicast sessions. Although all the nodes are capable of performing network coding, only some of them perform network coding in the optimal coding subgraph. 69 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs In problem (3.20), only variables nsiJ , q, s i , s i , and k are independent variables. Variables gsdiJ j, z s iJ , s i , and s i are auxiliary variables used to simplify the notation and formulation. Also, the second, third, fourth, and fth constraints can be removed if the variables gsdiJ j, z s iJ , s i , and s i are replaced by variable n s iJ , accordingly. Thus, the number of constraints and variables of the problem can further be reduced. The number of con- straints in problem (3.20) and the number of independent variables nsiJ , s i , s i increase linearly with the number of sessions jSj and the number of nodes jVj, and they increase exponentially with the number of the sinks jDsj of each session s 2 S. Thus, our formula- tion is suitable for networks with a large number of sessions while each session has a small number of sinks. Algorithm 3.1 below is the MLMR algorithm for determining the coding subgraph in the network. Algorithm 3.1 - MLMR Algorithm 1: Collect topology information (including V and A), set of sources S, and set of sinks Ds. 2: Determine the ordered set of all maximal cliques C in the hypergraph. 3: Set variable equal to the cost of performing network coding. 4: Solve problem (3.20) to obtain nsiJ , s i , s i , k, and q. 5: Forward the values of nsiJ to each sensor node i 2 V . We now describe how to extend the formulation proposed earlier to model some prob- lems. 3.2.2 Limit the Rate of Coding Operations Because of limited computational capabilities and memory, the rate at which intermediate nodes can perform network coding is limited in practice. For an intermediate node i, this depends on the resources available at the node and it is dierent for various nodes. The total rate at which intermediate node i performs network coding is P s2S P T2T s s i (T ). The maximum lifetime coding subgraph problem with limited coding rates can be formulated by 70 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs setting = 0 in the objective function of problem (3.20) and by including the following constraint to this problem: X s2S X T2T s si (T ) i; 8i 2 V ; (3.21) where i is the maximum rate at which node i can perform coding operations. We notice that constraint (3.21) is a linear constraint. Therefore, the maximum lifetime coding subgraph problem with a limited coding rates is a linear programming problem which can be eciently solved by using various polynomial time algorithms. 3.2.3 Limit the Number of Coding Devices Sometimes only a xed number of sensor devices in the WSN are capable of performing network coding. In this case, there are two types of sensor devices. The rst set of sensors called the coding devices are capable of performing network coding, routing, and replication. The second set of sensors simply perform routing or replication. The coding devices can be randomly deployed in the network. It is also possible to deploy coding devices in specic locations. The maximum lifetime coding subgraph problem for network with a xed number of coding devices can be formulated with some modications on problem (3.20). The objective of this new problem is to maximize the network lifetime, which is equivalent to minimizing the variable q. The maximum lifetime coding subgraph problem with limited number of coding devices can be formulated by setting = 0 in the objective function in problem (3.20) and by including the following constraint in problem (3.20): si (T ) = 0; 8 i 2 VnVc; s 2 S; T 2 T s; (3.22) where Vc V denotes the set of coding devices. The constraint in (3.22) guarantees 71 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs that only coding devices perform network coding. The maximum lifetime coding subgraph problem with a limited number of coding devices is also a linear programming problem. It can also be eciently solved by using various polynomial time algorithms. 3.2.4 Minimize the Number of Coding Devices Consider the case where the number of coding devices is not xed. However, the coding devices are more expensive compared to typical wireless sensor nodes. The objective is to jointly maximize network lifetime and minimize the number of coding devices. In other words, this formulation answers the following question: What is the minimum set of sensor devices that should perform network coding in order to achieve a certain level of the network lifetime? The dierence between this problem and the problem presented in the previous subsection is that the number of coding devices is not xed. The problem of nding the coding subgraph while the objective is to jointly maximize the lifetime and minimize the number of coding devices can be formulated with modication in problem (3.20). Let i be an indicator variable which denotes whether node i performs network coding or not. If i = 1, then node i performs network coding. This boolean variable can be mapped to si for node i as follows: i = 8><>: 1; if P s2S P T2T s s i (T ) > 0; 0; otherwise. This problem can be formulated by (a) replacing the objective function in problem (3.20) by minimizing q + P i2V i, where is a design factor, and (b) including the following constraints in problem (3.20): i P s2S P T2T s s i (T ) Hmax ; i 2 f0; 1g; (3.23) 72 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs where Hmax is an upper bound for the rate of performing network coding at all nodes. It is a constant and is used to guarantee that P s2S P T2T s s i (T )=Hmax is always less than 1. The formulated problem is a mixed integer linear programming problem with binary variables i. It can be solved by using branch-and-bound method [51]. 3.3 Performance Evaluation In this section, we evaluate the performance of our proposed MLMR algorithm and compare it with the minimal resource algorithm [23], the maximum lifetime Steiner tree (MLST) algorithm [95], and evolutionary minimum resource (EMR) algorithm [96]. For the MLST algorithm, a mixed integer linear programming model is used to construct the maximum lifetime multicast Steiner tree. We use the MOSEK [84] optimization toolbox to solve the problem. In the MATLAB simulations, we consider a square coverage area with each side equal to 70 m. There are 40 sensor nodes randomly deployed in the coverage area. One of them is the source node. There are four sinks located at the corners of the coverage area. The random topology has been used widely in WSNs in the literature [6, 70, 98]. Each source generates 10 kbps of information (i.e., rs = 10 kbps, 8 s 2 S). The size of each packet is 256 bits. The maximum transmission range is 10 m. The path loss exponent a is set to 4 [6]. We choose 1 = 100 pJ/sec/m and 2 = 1 nJ/sec [70]. The initial energy of each sensor node is 1 kJ. Each point is averaged over 100 simulation runs. 3.3.1 Varying the Tuning Parameter In the rst experiment, we determine the maximum network lifetime and the total rate of performing coding by varying the tuning parameter . There are four sinks deployed at the corners of the coverage area. One sensor node is randomly selected to operate as the source transmitting data towards all the sinks. A large value of (i.e., >> 1) implies 73 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 10âˆ’4 10âˆ’3 10âˆ’2 10âˆ’1 100 101 102 103 0.85 0.9 0.95 1 1.05 1.1 1.15 1.2 1.25 Î³ N et w or k life tim e (ye ars ) MLMR Minimal Resource Algorithm MLST 20% 25% No network coding Figure 3.3: Average network lifetime under dierent values of . that network lifetime is more important than the rate of performing network coding. On the other hand, a small value of (i.e., << 1) decreases the eect of network lifetime in nding the optimal coding subgraph. Figs. 3.3 and 3.4 show the network lifetime and the total rate of performing network coding under dierent values of , respectively. When the value of is small, the joint maximum lifetime minimum resource coding subgraph problem is reduced to the maximum lifetime coding subgraph problem. In this case, both the network lifetime and also the rate of performing coding achieve their maximum values. For small values of , the MLMR algorithm outperforms the minimal resource algorithm and the MLST algorithm by 20% and 25%, respectively. The total rate of performing network coding is 30% more in our proposed MLMR algorithm when compared with the minimal resource algorithm. When the value of increases, the rate of coding operation is decreased and eventually becomes zero when is greater than 10. In this case, the MLST algorithm performs better than the minimal resource algorithm since MLST makes use of the broadcast nature of the wireless 74 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 10âˆ’4 10âˆ’3 10âˆ’2 10âˆ’1 100 101 102 103 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Î³ N et w or k co di ng ra te (k bp s) MLMR Minimal Resource Algorithm 30% Figure 3.4: Total rate of performing network coding under dierent values of . links while the minimal resource algorithm does not. The MLMR algorithm performs better than MLST since it uses multipath routing as well as the broadcast nature of the wireless links. Multipath routing is known to outperform single path routing in terms of energy consumption and network throughput. Fig. 3.5 shows the lifetime of the network versus the network coding rates. Dierent points of this gure relate to dierent values of parameter and are derived from Figs. 3.3 and 3.4. When moving along this curve from left to right, the value of decreases from 10 to 104. A further decrease of the value of can neither improve the network lifetime nor increase the rate of coding operations. This gure shows that higher rates of coding operations in the network can lead to higher network lifetime. It is because network coding can reduce the total number of packets transmitted in the network and consequently can reduce the power consumption. 75 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.04 1.06 1.08 1.1 1.12 1.14 1.16 Network coding rate (kbps) N et w or k life tim e (ye ars ) Î³ = 10 Î³ = 1 Î³ =10âˆ’1 Î³=10âˆ’2 Î³=10âˆ’3 Î³=10âˆ’4 Figure 3.5: Network lifetime versus coding operation rate. 3.3.2 Varying the Number of Sinks jDsj In the second experiment, we compare the performance of our MLMR algorithm with the minimal resource and MLST algorithms in the presence of dierent number of sinks. One sensor node is randomly selected as the source node. The number of sinks increases in each step starting from one to four. In each step, the source node transmits data towards all the available sinks. Figs. 3.6 and 3.7 show the network lifetime and the rate of performing network coding under dierent number of sinks, respectively. When the network only has one sink, the problem is reduced to the unicast problem. Thus, our proposed MLMR algorithm and the minimal resource algorithm provide similar performance. These algorithms perform better than the MLST algorithm because they use multipath routing rather than single path routing as in the MLST algorithm. The MLST problem in the unicast case can be solved in polynomial time. In a unicast problem, the rate of performing network coding is zero. On the other hand, when the number of sinks increases, the amount of data ow in the network increases. The lifetime of the network decreases and the rate 76 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 1 2 3 4 0.8 1 1.2 1.4 1.6 1.8 2 2.2 Number of sinks N et w or k life tim e (ye ars ) MLMR Minimal Resource Algorithm MLST Figure 3.6: Network lifetime under dierent number of sinks ( = 104). of performing coding operation increases accordingly. 3.3.3 Varying the Number of Sources jSj The next experiment evaluates the performance of dierent algorithms when the number of sources varies in the network. There are four sinks located at the four corners of the coverage area. The number of sources is increased in each step of the simulation from 1 to 5. Each source node sends data towards the two sinks which are closer to itself. Figs. 3.8 and 3.9 show the network lifetime and the rate of performing network coding under dierent number of sources, respectively. When the number of sources increases, there are more packet transmissions and it causes a higher energy depletion in each sensor node. Thus, the network lifetime decreases. As the number of sources increases in the network, the rate of performing network coding is increased as well. The percentage of dierence between our proposed MLMR algorithm and the MLST algorithm increases from 25% for a network with one source to 35% for a network with ve source nodes. Compared with the minimal 77 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 1 2 3 4 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2 Number of sinks N et w or k co di ng ra te (k bp s) MLMR Minimal Resource Algorithm Figure 3.7: Total rate of coding operations under dierent number of sinks ( = 104). resource algorithm, our proposed MLMR algorithm has a higher network lifetime and a higher network coding rate. 3.3.4 Comparison between MLMR and EMR Algorithms In the last experiment, we compare the MLMR algorithm with the evolutionary minimum resource (EMR) algorithm proposed in [96]. We consider the network constructed by cas- cading multiple copies of the topology as shown in Fig. 3.10 (a). The network constructed by cascading three copies is shown in Fig. 3.10 (b). We consider the cascaded networks with 1, 3, 7, and 15 copies. The number of sinks in these networks are 2, 4, 8, and 16, respectively. The source node is placed at the root of each topology. Table 3.1 compares the number of links performing network coding between the MLMR and EMR algorithms for dierent copies of topology shown in Fig. 3.10 (a). Since the multicast rates are achiev- able without network coding, the minimum number of links performing network coding is zero. Our proposed MLMT algorithm achieves the optimal solution for values of greater 78 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 1 2 3 4 5 0.4 0.6 0.8 1 1.2 1.4 1.6 Number of sources N et w or k life tim e (ye ars ) MLMR Minimal Resource Algorithm MLST 25% 35% Figure 3.8: Network lifetime for dierent number of sources ( = 104). Table 3.1: Average number of links performing network coding. Number of copies 1 3 7 15 EMR algorithm 0.23 0.65 2.15 5.35 MLMR algorithm with = 102 1 3 7 15 MLMR algorithm with = 101 1 3 7 15 MLMR algorithm with = 1 0 0 0 0 MLMR algorithm with = 10 0 0 0 0 than 1. When is less than 101, the EMR algorithm performs better than the MLMR algorithm especially for larger networks. It is because our proposed MLMR algorithm maximizes the network lifetime as the main objective and minimizes the network resources as the secondary objective when is small. 79 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs 1 2 3 4 5 0.5 1 1.5 2 2.5 3 Number of sources N et w or k co di ng ra te (k bp s) MLMR Minimal Resource Algorithm Figure 3.9: Total rate of coding operations under dierent number of sources ( = 104). 3.4 Summary In this chapter, we studied the tradeo between network lifetime and system resources utilized to perform network coding in energy-constrained WSNs. We rst introduced the constraints of the system. We then proposed the coding ow variables which enable us to determine the type of operation performed in each sensor node. The rate of performing network coding and replication in each node can be determined by using our proposed variables. We formulated the joint problem of constructing maximum-lifetime minimum- resource coding subgraph as a linear programming problem. The complexity of our algo- rithm increases linearly with the number of nodes and number of sessions, and it increases exponentially with the number of sinks. Hence, the algorithm is suitable for networks with a large number of sessions while each session has a small number of sinks. We described two directions for the model extension of this problem. Simulation results showed that our proposed MLMR algorithm has a better performance when compared with the minimal resource algorithm [23], the MLST algorithm [95], and the EMR algorithm [96]. 80 Chapter 3. Lifetime-Resource Tradeo for Multicast Trac in WSNs s (b) d1 d2 d3 d4 s d1 d2 (a) Figure 3.10: Network topology: (a) one copy, (b) three copies. 81 Chapter 4 Feedback Mechanism for Random Linear Network Coding with Buer Sharing in Lossy Wireless Sensor Networks The wireless links are prone to failure due to fading and interference in WSNs. Therefore, improving the reliability can help to achieve power gain (i.e., lower power consumption). It is shown that random linear network coding (RLNC) can improve the reliability of end-to- end communication in the presence of lossy links [24, 25]. For a multihop communication session between a source and the sink, if the intermediate nodes use RLNC to store the received packets and transmit coded packets by linearly combining the buered packets, the packet-level (i.e., max ow min-cut) capacity of a unicast session can be achieved [24], [25]. To reduce the time for the sink to decode the packets, the source divides the generated packets into groups called generations. The source and intermediate nodes perform coding operations on the packets of one generation. The sink can decode the packets of one generation as soon as it has enough packets for the decoding. The performance of RLNC is comparable to link-by-link automatic repeat request (ARQ) in terms of power consumption. However, it is shown in [100] that RLNC can 82 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs achieve substantially higher power gain compared to end-to-end ARQ. The decoding delay of RLNC in multicast networks is investigated and compared to conventional scheduling techniques in [101]. The delay analysis of RLNC for unicast session on a line topology is presented in [102]. A comprehensive study of RLNC for time division duplexing with uni- cast session on a line network is performed in [103, 104, 105]. The source transmits packets consecutively and then waits for the sink to announce the number of additional packets it requires for decoding. In order to minimize the power consumption, there is an optimal number of packets to send before waiting for the feedback from the sink [103]. Energy ecient techniques based on opportunistic variants of RLNC are proposed in [106, 107]. RLNC can also be used in other areas such as network tomography [61], peer-to-peer content distribution [108], and code updates [109]. The use of feedback in routing packet networks and networks using RLNC is dierent. In routing packet networks with lossy links, feedback-based techniques such as ARQ are used to trigger the retransmission of lost packets. With delay and error free link-by-link feedback, the end-to-end packet transmission with ARQ can achieve the max- ow min-cut capacity [104]. However, perfect feedback may not be possible in real situations. On the other hand, the feedback packets in RLNC are used to acknowledge the receipts of enough coded packets for decoding. Similar to ARQ, both link-by-link and end-to-end feedback mechanisms can be used in RLNC. When link-by-link feedback is used, each intermediate node sends feedback to its upstream neighboring node when it has sucient packets with independent coding coecients. With end-to-end feedback, the sink informs the source and all the intermediate nodes to stop transmission of a generation by sending feedback packets to them. RLNC can achieve the max- ow min-cut capacity when the code size and the generation size are suciently large [24, 25]. In RLNC, when intermediate nodes keep dierent buers for various ows (i.e., RLNC 83 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs without buer sharing), each transmitted packet contains information of only one ow. For the case of link-by-link feedback, an intermediate node i will receive a feedback control packet for a particular ow when its immediate downstream node has enough coded packets to decode the packets of one generation of that ow. For the case of end-to-end feedback, an intermediate node i will receive a feedback control packet from the sink for a particular ow when the sink has enough coded packets for decoding. The work in [110] presented dierent ways that feedback can help for network coding, including the benet of feedback for quality of service, resource management, and improving the reliability. A feedback- based online network coding approach is presented in [111], where the destinations send individual feedback for each received packet. It has a lower decoding delay compared to the generation-based coding approaches. The idea of using shared buer for dierent ows passing an intermediate node has been employed in several network coding based techniques. COPE [112] presents a practical way to implement linear network coding in wireless networks while packets of various ows share the buer. It increases the throughput of the network by taking advantage of network coding and opportunistic listening. The performance of COPE is improved by jointly considering network coding and medium access control (MAC). COPE has also been extended in dierent directions [113, 114, 115]. In SenseCode [116], the intermediate nodes combine the overheard packets from dierent neighbors with its generated packets. It increases the amount of redundant information in the network, which can improve the reliability. We consider a WSN with a single sink and several sources, while data are gathered through a reverse multicast tree rooted at the sink. The feedback mechanism design for RLNC with buer sharing is dierent from RLNC without buer sharing. We notice that the feedback control packet is generated in order to inform a node to stop packet 84 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs transmission for a particular ow. In RLNC without buer sharing, an intermediate node can stop transmission of a ow f after successfully transmittingKf packets, whereKf is the generation size of ow f . On the other hand, for RLNC with buer sharing, the transmitted packets contain information of all the ows passing the intermediate node. Therefore, it is not possible to distinguish to which ow a transmitted packet belongs. Consequently, it is a challenge to determine when a node can stop transmission of a particular ow. In this chapter, we study the problem of feedback mechanism design for RLNC with buer sharing. Although the problem of feedback mechanism design for RLNC without buer sharing is studied in [25], [103], and [110], to the best of our knowledge, there is no feedback mechanism in the literature for RLNC with shared buers. The contributions of this chapter are as follows: For an intermediate node i in a reverse multicast tree topology, we determine when the node can stop transmission of a particular ow f . We analytically show that reducing the transmission rate at this time does not change the rate at which node i transmits the coded packets which carry new information for its downstream neighbor. We propose a novel link-by-link feedback mechanism. In this mechanism, every intermediate node generates feedback control packet for its upstream neighboring node. We propose three dierent types of end-to-end feedback mechanisms for RLNC with buer. In end-to-end feedback mechanisms, the sink is responsible for generating feedback control packet for all the nodes in the network. Simulation results show that the link-by-link feedback mechanism has better perfor- mance in terms of the power consumption than the end-to-end feedback mechanism. The results also show the performance gain of using buer sharing compared to RLNC 85 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs without buer sharing in terms of power consumption. They also show the tradeo between the power consumption and delay when using buer sharing is employed. The model and mechanisms we present in this chapter are unique when compared to the prior work done in the area of feedback mechanism design. In terms of buering, the work in [24, 25] require an individual buer for each ow at the intermediate nodes. Our proposed feedback mechanisms use buer sharing. In terms of overhead, COPE [112] requires an acknowledgement packet be transmitted for each received or overheard packet. In contrast, our proposed mechanisms require a downstream node (or sink) to transmit a feedback packet when it has received a generation of packets. For the work in Sensecode [116], all the ows stop transmission at the same time while in our proposed approaches, various ows stop transmissions based on the order the packets of one generation are successfully transmitted. The rest of this chapter is organized as follows: The system model along with a descrip- tion of RLNC with buer sharing is summarized in Section 4.1. In Section 4.2, we model and analyze the rate at which the intermediate nodes transmit and receive the packets with new information. In Section 4.3, we propose the link-by-link and end-to-end feed- back mechanisms. Performance evaluation and comparison are presented in Section 4.4. A summary is given in Section 4.5. 4.1 System Model We consider a WSN with a set of sources and one sink. Without loss of generality, we assume that the sources do not relay information of other ows. Let V denote the set of sensor nodes. Data from dierent sources are gathered at the sink via a reverse muticast tree. Therefore, there is a one-to-one mapping between each sensor node and its outgoing link. We use the same set V to denote the set of links. Thus, link i is the output link 86 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs of node i. We use i to denote the packet success probability of the output link of node i. Let F denote the set of all the ows in the network. A ow is the data ow from a source to the sink. The set of nodes relaying packets of ow f 2 F is denoted by Pf . The set of dierent ows passing through an intermediate node i 2 V is denoted by Fi. Each intermediate node keeps one buer for all the ows. Each source divides the generated packets into groups called generations. The down- stream intermediate nodes buer the received packets of one generation from the up- stream ows. The sources and the intermediate nodes create coded packets by combining the buered packets using random coecients taken from a Galois eld with size q (i.e., GF(2q)). They append the coding coecients in the packet header. The vector of coding coecients is called the encoding vector. The source and intermediate nodes transmit coded packets until they receive a feedback control packet from either the sink or a downstream node. The rate at which packets of ow f 2 F are being transmitted is rf . Since various sources may generate packets at dierent rates, we set the generation size of dierent ows such that all the ows have the same generation size to transmission rate ratio. This ratio is denoted by . Let Kf denote the generation size of ow f . We have Kf=rf = for all ow f 2 F . This condition ensures that if the links are lossless, then the sink can decode the packets seconds after receiving the rst packet. In RLNC with buer sharing, all the sources start transmission of a generation at the same time. The dierence between the time that the sources start transmission of the packets and the time that the sink can decode the packets is called the decoding delay. Let i(t) denote a matrix composed of the encoding vectors of the packets in the buer of node i at time t. Each column in matrix i(t) contains the encoding vector of a packet stored in the buer of node i. Each row in matrix i(t) corresponds to the coecients of a 87 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs packet from a generation of a particular ow. The rank of this matrix, denoted as ji(t)j, represents the number of packets with independent encoding vectors in the buer of node i. We dene ji(t)jF as the rank of matrix i(t) with respect to the set of ows in F Fi. It is computed by replacing the rows of matrix i(t) which do not belong to the ows in F by zero vectors and then computing the rank of the resulting matrix. A packetW transmitted by node i at time t is an innovative packet for downstream node j if it increases the rank of matrix j(t) by one upon reception. For large Galois eld size, ji(t)j > jj(t)jFi would result that W is an innovative packet with probability close to one [25]. The ux of innovative packets for ow f can be modeled as a queueing system [20, Chapter 4]. Each intermediate node is modeled as a server while innovative packets are customers traveling from the sources to the sink via intermediate nodes. Note that this queue is dierent from the actual buer of the node which stores all the received packets. To distinguish this queue from the buer of the node, it is called the virtual queue of the node. For an intermediate node i, the number of packets in the virtual queue of node i is increased by one when it receives an innovative packet from one of its upstream nodes. The virtual queue of intermediate node i may receive packets from multiple ows. The input rate to the virtual queue of node i is the aggregate rate at which node i receives innovative packets from its upstream neighboring nodes. The number of packets in the virtual queue of node i is decreased by one when node i successfully transmits an innovative packet. Therefore, the service rate of the virtual queue is the rate at which packets are successfully transmitted. We call the product of the packet success probability of the output link of node i and the transmission rate of node i as the eective transmission rate of node i. This is also the service rate of the virtual queue of node i. The rate at which the innovative 88 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs packets are transmitted from node i depends on the eective transmission rate of the node and the input rate of the innovative packets. The number of innovative packets in the buer of node j (i.e., the downstream node of node i) received from node i at time t is jj(t)jFi . 4.2 Transmission Rate Analysis The goal of the feedback mechanism is to generate feedback control packets which ac- knowledge the receipt of a generation of source packets. An intermediate node i reduces its transmission rate by rf upon receiving the feedback for ow f . Therefore, to design the feedback mechanism, we need to determine when an intermediate node can stop transmit- ting the packets of one generation for ow f . In this section, we determine the time that an intermediate node i can stop transmission of a particular ow f by analyzing the rate at which it transmits innovative packets. 4.2.1 When Can Node i Stop Transmission of Flow f? For RLNC without buer sharing, the intermediate node i stores the packets of dierent ows in various buers. It can stop transmitting the packets of ow f as soon as it successfully transmits the Kf -th innovative packet. After this time, the rate at which node i transmits the innovative packets is zero. Therefore, node i can reduce its transmission rate by rf [24, 103]. On the other hand, for the case that the intermediate node i stores the packets of various ows in a shared buer, it starts transmitting the packets from the shared buer at the aggregate rate of P f2Fi rf . The rate at which node i transmits the innovative packets depends on the rate at which it receives the innovative packets and its eective transmission rate. Node i can stop transmission of ow f (i.e., reduce its transmission rate 89 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs Figure 4.1: A network tree with two sources, one intermediate node i, and one sink. Packets of ows 1 and 2 are generated by source s1 and s2, respectively. by rf ) if the rate at which innovative packets are transmitted does not alter after reducing the rate. Every transmitted packet contains information of all the ows in Fi. Thus, one cannot distinguish to which ow a transmitted packet belongs to. Consequently, it is not feasible to determine the time that node i can stop transmission of ow f by counting the number of transmitted innovative packets of a particular ow. As an example, consider Fig. 4.1 with two ows (from sources 1 and 2 to the sink d) and an intermediate node i. The transmission rates of ows 1 and 2 are r1 = r2 = 1 packet per second. The packet success probability of the links in the network are as follows: 1 = 0:75, 2 = 0:9, and i = 1. Node i receives innovative packets of ows 1 and 2 at the average rate of 0:75 and 0:9 packets per second at the beginning, respectively. Therefore, the input rate of innovative packets to the virtual queue of node i is 1:65 packets per second. The transmission rate of node i is 2 packets per second, which is equal to the eective transmission rate of the node. If the generation size of ow 1 is K1, node i receives the last innovative packet of ow 1 on average after 1 = K1=0:9 seconds. After this time, the input rate of the innovative packets to the virtual queue of node i drops from 1:65 to 0:75. 90 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs As soon as node i can manage to transmit the packets of ow 1 after time 1, it can reduce its transmission rate from two packets per second to one packet per second. Since the rate at which this node receives the innovative packets is 0.75 packets per second, reducing the transmission rate from 2 to 1 does not change the rate at which this node transmits the innovative packets. Now, we determine when each node on path set Pf can stop transmission of ow f . We start from the source of ow f and move along path Pf to the sink. Among ows in F , we only study ow f in this section. For the sake of simplicity, we denote the set of nodes in the path set Pf by 1; 2; : : : ; jPf j , where node 1 is the source of ow f and node jPf j is the sink. Since the source of ow f does not relay the packets of other ows, it can stop transmission after successfully transmitting Kf packets with independent encoding vectors. Let f1 denote the time that the source of ow f successfully transmits the Kf -th innovative packet. At this time, the virtual queue of the source is empty. Since after time f1 , node 2 does not receive any innovative packet from the source of ow f , it can stop transmission of the ow as soon as it can transmit all the packets in its virtual queue after time f1 . Note that the packets transmitted by node 2 contain information of all the packets in its buer. Therefore, we cannot distinguish to which ow a transmitted packet belongs to if node 2 relays packets of more than one ow. The rst time that the virtual queue of node 2 is empty after f1 is the rst time that we can ensure all the information of ow f are transmitted. Let f2 denote the rst time after f 1 at which the virtual queue of node 2 is empty. For an intermediate node i, we use fi to denote the rst time after f i1 that the virtual queue of node i is empty. We dene this time in a recursive manner as fi = min n t j t > fi1; ji(t)j = ji+1(t)jFi o ; i = 1; : : : ; jPf j 1 (4.1) 91 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs where f0 = 0. First, we show how this time can be calculated in practice. Then, we show that reducing the rate by rf at time f i does not change the rate at which node i transmits the innovative packets, which means node i can reduce its transmission rate at fi . 4.2.2 Determine the Time fi Let gfi (t) denote the number of packets with exclusive information of ow f in the buer of node i at time t. This is the number of innovative packets in the buer of node i minus the number of innovative packets of all the ows except ow f at time t. gfi (t) is increased by one at time t if node i receives an innovative packet which is not innovative for ows in Finffg. For better understanding of the concept, consider the following example. Assume that node i receives packets of three ows, namely, f1, f2, and f3. Assume that the generation size is one (i.e., K1 = K2 = K3 = 1) and node i currently has two packets with encoding vectors (2, 4, 3) and (2, 3, 1). Both of these packets are innovative. They are also innovative packets for ows f1 and f2. Therefore, the number of packets with exclusive information of ow f3 is zero. At time t, node i receives a packet with encoding vector (1, 4, 1). Since this packet is innovative, the total number of innovative packets in the buer of node i would be 3. Moreover, this packet is not innovative for ows f1 and f2. Therefore, g 3 i (t) = 1. We notice that the newly received packet is not innovative for ow f3 while it has exclusive information of ow f3. From the denition of gfi (t), the value of g f i (t) at time t can be calculated as gfi (t) = ji(t)j ji(t)jnffg; (4.2) where ji(t)jnffg is the number of innovative packets of all the ows except ow f at time t. This can be calculated by setting the coding coecients corresponding to the ow f for 92 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs the packets in i(t) to zero and then calculating the rank of this resulting matrix. The following lemma shows how the function gfi (t) can be used to determine time f i . Lemma 4 The time fi is the rst time at which g f i+1(t) is equal to Kf fi = min n t j gfi+1(t) = Kf o ; i = 1; : : : ; jPf j 1; f 2 Fi (4.3) Proof The function gfi (t) is an increasing function since it is not possible that node i receives a packet which is innovative for all the ows except f while this packet is not innovative for node i. Nevertheless, the number of packets with exclusive information of ow f is less than or equal to the number of innovative packets of ow f . Therefore, function gfi (t) is upper bounded by Kf . Now, we proof the lemma by mathematical induction. At time f1 , node 2, which is the immediate downstream node of node 1 (i.e., the source node of ow f), has received the Kf -th innovative packet from the source. Since every packet in the buer of node 2 contains either information of f or other ows, we have 2 f1 = 2 f1 nffg + 2 f1 ffg. Therefore, we have gf2 ( f1 ) = Kf . This is the basis of our induction. Now as the hypothesis of the induction, assume that gfi+1( f i ) is equal to Kf while g f i+1(t) < Kf for t < f i . We need to prove that g f i+2( f i+1) = Kf , while gfi+2(t) < Kf for t < f i+1. Since f i+1 > f i and g f i (t) is an increasing function and is upper bounded by Kf , we have g f i+1( f i+1) = Kf . Since the virtual queue of node i + 1 is empty at time fi+1, node i + 2 has the same information that node i + 1 has about ows in set Fi+1, which implies gfi+2( fi+1) is equal to Kf . To complete the proof, we need to show that gfi+2(t) < Kf for t < f i+1. Since g f i+2(t) < g f i+1(t) and g f i+1(t) < Kf for t < f i , therefore, gfi+2(t) < Kf for t < f i . Now, assume that there exists a time such that fi < < f i+1 and g f i+2() = Kf . Thus, at time , node i + 2 has received a packet with exclusive information of ow f . It means there is no packet in the virtual queue of node i+1 with information of other ows except f . However, this is the last packet sent by node 93 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs i + 1 with exclusive information of ow f . Therefore, after time , the virtual queue of node i+1 is empty while this contradicts to the denition of fi+1. Therefore, g f i+2(t) < Kf for t < fi+1. 4.2.3 Transmission Rate of Innovative Packets After Time fi In this section, we show that reducing the transmission rate after time fi does not change the rate at which node i transmits innovative packets. Our model analyzes the system on a long term operation period and the transmission rates are expected values. Let zi (F ) denote the rate at which node i transmits the innovative packets of ows in set F . We focus on node i and one of the ows f 2 Fi. We assume that ow f has the lowest value of fi among all the ows in Fi (i.e., fi = min s2Fi si ). For the sake of simplicity, we assume that fi is not equal to s i for s 2 Finffg in the rest of the chapter. The following theorem shows that node i can reduce its transmission rate at time fi without changing the rate at which innovative packets are transmitted. Theorem 3 The value of zi(Finffg) does not change if node i reduces its transmission rate from P s2Fi ri to P s2Finffg ri (i.e., reduces by rf), where f i is equal to min s2Fi si . Proof Since fi = min s2Fi si , zi(Finffg) is constant in time period [0; fi ] as long as node i receives innovative packets from ows in Finffg. At time fi , the virtual queue of node i is empty. Hence, all the received innovative packets up to time fi have been transmitted by node i. The number of innovative packets transmitted by node i up to time time fi is i fi , which is equal to gfi fi + i fi nffg. Based on Lemma 4, we have gfi fi = Kf . Since the transmission rate of the innovative packets for all the ows except ow f is zi(Finffg), the average number of innovative packets transmitted by node i up to time fi is zi (Finffg) fi +Kf . The average number of successful transmissions of node i up to time fi is f i i P s2Fi rs. The average number of innovative packets that node i 94 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs has transmitted is less than or equal to the number of successful transmissions of node i. Therefore, we have zi (Finffg) fi +Kf fi i X s2Fi rs; (4.4) which can be re-arranged as zi (Finffg) i X s2Fi rs Kf fi : (4.5) IfKf= f i > irf , then we obtain zi (Finffg) < i P s2Finffg rs from (4.5). Now, we consider the case that Kf= f i irf , which is equal to = fi i. Since the ows in set Finffg are still active, the total number of innovative packets transmitted by node i from these ows up to time fi is strictly less than the total number of packets for one generation of these ows (i.e., zi (Finffg) fi < P s2FinffgKs). Therefore, we have zi (Finffg) < P s2FinffgKs fi = fi X s2Finffg rs i X s2Finffg rs: (4.6) This means the rate at which node i transmits innovative packets is less than its eective transmission rate after reducing the rate by rf . Hence, the rate at which this node transmits the innovative packets does not alter by reducing the rate. The following lemma shows that as soon as node i reduces its transmission rate once, the queuing delay of its virtual queue is upper bounded. Lemma 5 For time t greater than fi , where f i = min s2Fi si , the number of packets in the virtual queue of node i is upper bounded. Proof The virtual queue of node i is empty at time fi . Based on Theorem 3, at time t = fi , the input rate of the virtual queue is less than the service rate of the queue which 95 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs is i P s2Finffg rs. Since the input rate of the virtual queue is not increased over time, the input rate is always less than P s2Finffg rs for t > f i . We notice that, the transmission rate of node i is not reduced such that it falls below the input rate of the virtual queue after time fi . Therefore, since Ji( fi ) = 0 while the input rate of the queue is always less than the service rate during the operation of the queue, the number of packets in the virtual queue of node i is bounded and the probability that the virtual queue is empty is non-zero for t > fi . Another interpretation of Lemma 5 is that the rate at which node i transmits innovative packets is always less than the rate at which this node receives the innovative packets after time fi . Let '(t) Fi denote the set of ows that node i receives innovative packets from at time t. The following lemma characterizes the rate at which node i transmits innovative packets of ows '(t). Lemma 6 The rate at which node i transmits the innovative packets of ows '(t) from time 0 to t is the weighted sum of the rates of all these ows. That is, zi ('(t)) = X s2'(t) rs i s('(t)); (4.7) where is('(t)) is a non-negative coecient for node i and ow s corresponding to the set of ows '(t). Proof We use mathematical induction to prove this lemma. The rate at which the source of ow f (i.e., node sf ) transmits the innovative packets is zsf (ffg) = sf rsf . This is the basis of induction. Consider intermediate node i where Ni denotes the set of upstream nodes of node i. As inductive step, assume that upstream node j 2 Ni transmits packets of ows '(t) \ Fj with rate zj ('(t) \ Fj) = P s2'(t)\Fj rs j s('(t) \ Fj). Then, the rate at which node i receives innovative packets of ows '(t) is the sum of the rate at which nodes 96 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs in set Ni transmit innovative packets. The rate at which node i transmits the innovative packets is the minimum of the rate at which it receives innovative packets and its eective transmission rate. That is, zi ('(t)) = min 8<:X j2Nj zj ('(t) \ Fj) ; i X s2'(t) rs 9=; = min 8<:X j2Nj X s2'(t)\Fj rs j s('(t) \ Fj); i X s2'(t) rs 9=; (4.8) Both arguments of the minimum function on the right hand side of equation (4.8) are linear combination of rs for all s 2 '(t). Therefore, zi ('(t)) is a linear combination of rs for all s 2 '(t) which can be denoted by zi ('(t)) = P s2'(t) rs i s('(t)) where i s('(t)) is a constant coecient. Using Lemma 6, we are able to generalize Theorem 3 as Theorem 4 The value of zi('(t)) does not change if node i reduces its transmission rate by rf at time f i . Proof If all the ows being relayed by node i are active at time fi , based on Theorem 3, node i can reduce its transmission rate by rf . Now, assume that ow f is not the rst ow whose rate is reduced by node i. Since node i has reduced its transmission rate before time fi once, the rate at which it receives the innovative packets before time f i is less than its eective transmission rate. According to Lemma 6, the rate at which this node receives the packets of ows in set '(t) is zi('(t)). The average rate at which it received the packets of ow f before fi is Kf= f i . Therefore, we have zi ('(t)nffg) + Kf fi i X s2'(t) rs: (4.9) 97 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs Equation (4.9) is similar to (4.5). We can follow the rest of proof of Theorem 3 after equation (4.5) and show that zi('(t)nffg) < i P s2'(t)nffg rs. This shows that reducing the transmission rate of node i by rf does not change the rate at which this node transmits the innovative packets. Theorem 4 proves that fi is the time that node i can reduce the transmission rate by rf . 4.3 Feedback Mechanism Design The goal of the feedback mechanism is to generate feedback control packet for an inter- mediate node and a particular ow such that the node can stop transmission of that ow. As shown in Theorem 4, for any ow f 2 Fi, node i can reduce its transmission rate by rf at time f i . However, as Lemma 4 shows, node i cannot determine this time by itself. The feedback control packet generated by downstream nodes of node i is used to notify node i to reduce its transmission rate at certain times. We propose two feedback mechanisms, namely link-by-link and end-to-end feedback, which are useful under dierent circumstances. 4.3.1 Link-by-Link Feedback Mechanism In link-by-link feedback mechanism, each intermediate node is responsible to generate feed- back control packet for its upstream neighboring nodes. It is applicable if the intermediate nodes are capable of calculating the matrix ranks. In this mechanism, each intermediate node checks the stored packets and informs the upstream neighboring nodes to reduce the rate for a particular ow when it exclusively has full rank information of the ow. Based on Theorem 4, node i can stop transmission of ow f at time fi where gj fi = Kf 98 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs Algorithm 4.1 Link-by-Link Feedback Mechanism at Node i. 1: input: Fi;Kf ; 8f 2 Fi 2: for each generation 3: A := ; 4: while A 6= Fi and a new packet is arrived at time t 5: for ow f 2 FinA 6: if ji(t)j ji(t)jnffg is equal to Kf 7: Send feedback control packet for ow f to the upstream node that relays packets of ow f 8: A := A [ ffg 9: end if 10: end for 11: end while 12: end for and j is the downstream neighboring node of node i. Therefore, node j can generate the feedback control packet of ow f for node i as soon as gj fi = Kf . Algorithm 4.1 shows the link-by-link feedback mechanism at the intermediate node i. Upon receiving a packet from an upstream node, node i checks whether it has enough exclusive packets for any of the ow (Step 4). If there is any ow with enough exclusive packets (Step 6), node i will send the feedback control packet to the appropriate upstream neighboring node (Step 7). The algorithm continues until node i sends feedback control packet for all the ows in Fi. 4.3.2 End-to-End Feedback Mechanism As mentioned earlier, the link-by-link feedback mechanism is benecial if the intermediate sensor nodes are capable of calculating the rank of the matrix. However, sensor nodes are inexpensive devices with low computational capabilities. Sensor nodes may not able to calculate the matrix ranks online, especially when there are several ows. In this case, the sink, which has higher computational power, can generate the feedback control packet for the sources and all the intermediate nodes. 99 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs When the sink is responsible to generate the feedback, there are three dierent feedback mechanisms: Type 1. The sink transmits feedback control packets to all the nodes as soon as it can decode the packets of one generation of all the ows. In this case, the sink needs to monitor the total number of received innovative packets. Once the number of innovative packets is equal to P s2F Ks, the sink sends feedback control packets to all the nodes to stop transmission. Although this has a low computational load since the sink does not need to monitor various ows individually, this wastes power at the intermediate nodes via unnecessary transmissions. We call this mechanism the end-to-end feedback mechanism after decoding. Type 2. The sink generates a feedback control packet for ow f at time fd . This feedback packet acknowledges all the nodes on the path set Pf relaying packets of ow f . We call it per ow end-to-end feedback mechanism. The following proposition shows that the sink d can generate a feedback packet to acknowledge ow f at time fd . We notice that gfd (t) = jd(t)j jd(t)jnffg. Proposition 2 If gfd (t) is equal to Kf at time t, then all the nodes relaying packets of ow f can reduce their transmission rates by rf . Proof Based on Lemma 2, the immediate upstream node of the sink d, which relays packets of ow f , can stop transmission of ow f as soon as gfd (t) is equal to Kf . Since fi+1 is strictly less than f i for i = 1; : : : ; jPf j 1, all the nodes in path set Pf can stop their transmissions at this time as well. Type 3. The sink sends individual feedback packet for any intermediate node i 2 V and ow f 2 Fi. This type of feedback is unique to the network which uses shared buer. If the intermediate nodes keep separate buers for various ows, it is not possible to create 100 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs feedback per intermediate node. An intermediate node with multiple incoming links can receive individual feedback from the sink. We call this type of the feedback per ow per node end-to-end feedback mechanism. Proposition 2 provides a sucient condition for the generation of feedback for node i and ow f . The following lemma, however, provides a necessary condition for the feedback generation. Lemma 7 The sink d should send feedback control packet of ow f to intermediate node i 2 V at time t if jd(t)jFi jd(t)jFinffg = Kf : (4.10) Proof In the buer of node downstream node i+1 of node i, there are two independent sets of packets. The rst set is the packets which have information of ows in Fi. The second set of packets include those with information of the ows in Fi+1nFi. The packets of ows in Fi at the sink are linear combination of the packets in the buer of node i+1. Assume that there are n packets in the buer of the sink which contain information of ows Fi. We have jd(t)jFi = minfn; ji+1(t)jFig and jd(t)jFinffg = minfn; ji+1(t)jFinffgg. This shows that, jd(t)jFijd(t)jFinffg = 8>>>><>>>>: 0, if n ji+1(t)jFinffg n ji+1(t)jFinffg, if ji+1(t)jFinffg < n < ji+1(t)jFi ji+1(t)jFi ji+1(t)jFinffg, if n ji+1(t)jFi . (4.11) This equation shows that jd(t)jFi jd(t)jFinffg ji+1(t)jFi ji+1(t)jFinffg =ji+1(t)j ji+1(t)jnffg = gfi (t). To guarantee that gfi (t) = Kf , it is necessary that jd(t)jFi jd(t)jFinffg = Kf . Algorithm 4.2 shows type 3 end-to-end feedback mechanism performed at the sink d. Upon receiving a packet from an upstream node (Step 4), for any unacknowledged ow at 101 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs Algorithm 4.2 Type 3 End-to-End Feedback Mechanism at Sink d. 1: input: Fi; 8 i 2 V;Kf ; 8f 2 F 2: for each generation 3: Ai := ;; 8 i 2 V 4: while a new packet is arrived at time t 5: for i 2 V 6: for f 2 FinAi 7: if jd(t)jFi jd(t)jFinffg is equal to Kf 8: Send feedback control packet for the ow f to node i 9: Ai := Ai [ ffg 10: end if 11: end for 12: end for 13: end while 14: end for node i (i.e., set Ai), the sink checks whether it has enough exclusive packets for that ow (Step 7). If there exists a ow f 2 Fi with enough exclusive packets, the sink will send the feedback packet to the appropriate node (Step 8) and the node will reduce its transmission rate by rf . Then, the sink adds ow f to the set Ai (Step 9). 4.4 Performance Evaluation In this section, we present the performance analysis and comparison for the proposed feedback mechanisms as well as the power eciency of RLNC with buer sharing. We construct the reverse multicast tree from the sources to the sink which is the root of the tree. For the packet success probability, we follow the model used in [117]. For each outputs link of node i, the packet success probability i is randomly chosen with probability (1) i , where is a tunable design parameter. The mean of the packet success probability is =(+1). The higher the value of , the lower rate the packet loss in the network. The results are averaged over 1000 simulation runs. The power consumption of node i 2 V is the number of packets transmitted by node i times the power consumed to transmit one 102 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs 20 40 60 80 100 120 140 160 180 200 20 25 30 35 40 45 50 55 60 Generation size Kf N or m al iz ed a ve ra ge p ow er c on su m pt io n RLNC with Buffer Sharing âˆ’ Endâˆ’toâˆ’end feedback after decoding RLNC without Buffer Sharing âˆ’ Endâˆ’toâˆ’end feedback RLNC with Buffer Sharing âˆ’ Per flow endâˆ’toâˆ’end feedback RLNC with Buffer Sharing âˆ’ Per flow per node endâˆ’toâˆ’end feedback RLNC without Buffer Sharing âˆ’ Linkâˆ’byâˆ’link feedback RLNC with Buffer Sharing âˆ’ Linkâˆ’byâˆ’link feedback 15% 22% Figure 4.2: Normalized average power consumption versus generation size K for = 2. packet. To normalize the power consumption, we divide it by the number of ows, the generation size, and the power consumed to transmit one packet. We compare RLNC with buer sharing and RLNC without buer sharing for both link-by-link and end-to-end feedback mechanisms. The comparison is carried out in terms of the power consumption and the decoding delay. First, we consider a topology with 100 intermediate sensor nodes and 30 sources randomly deployed in a 100 m 100 m square area. The sink is placed at the upper-right corner. The generation size of dierent ows are equal. We set equals to 2. Fig. 4.2 compares the normalized power consumption of various feedback mechanisms for the generation size equal to 10, 50, 100, 150, and 200. The normalized power consumption decreases by increasing the number of packets in each generation. We notice that the results are normalized by the generation size. For values greater than 100, the improvement in the power consumption achieved by increasing the generation size is negligible. Therefore, for the rest of simulations, we set Kf = 100 for 103 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs 1 2 3 4 5 6 7 8 9 10 20 30 40 50 60 70 Î» N or m al iz ed A ve ra ge P ow er C on su m pt io n Endâˆ’toâˆ’end feedback mechanism after decoding Per flow endâˆ’toâˆ’end feedback mechanism Per flow per node endâˆ’toâˆ’end feedback mechanism Linkâˆ’byâˆ’link feedback mechanism (a) RLNC with buer sharing 1 2 3 4 5 6 7 8 9 5 10 15 20 25 30 35 Î» N or m al iz ed A ve ra ge P ow er C on su m pt io n Endâˆ’toâˆ’end feedback mechanism Linkâˆ’byâˆ’link feedback mechanism (b) RLNC without buer sharing Figure 4.3: Normalized average power consumption versus parameter . all the ows. For Kf = 100, by using buer sharing in RLNC, the power consumption can be reduced by 15% and 22% for link-by-link and end-to-end feedback mechanisms, respectively. Figs. 4.3 (a) and (b) compare the normalized power consumption of RLNC with/without buer sharing using link-by-link and end-to-end feedback mechanisms. We vary the design parameter and measure the power consumption. Results shows that the link-by-link feed- back mechanism performs better when compared to the end-to-end feedback mechanism 104 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs 1 2 3 4 5 6 7 8 9 1 1.5 2 2.5 3 3.5 4 4.5 5 Î» N or m al iz ed A ve ra ge D ec od in g De la y RLNC with Buffer Sharing RLNC without Buffer Sharing 30% Figure 4.4: The normalized decoding delay between RLNC with and without buer sharing. for RLNC with buer sharing and RLNC without buer sharing. For all the mechanisms, the power consumption decreases as increases since a higher packet success probability will lead to a lower number of packet losses in the network. For large values of (i.e., 7), since the loss rate of the links approach zero, the benet of using network coding is negligible. For RLNC with end-to-end feedback mechanism, we observe that the perfor- mance of RLNC with buer sharing and end-to-end feedback mechanism is close to that of RLNC without buer sharing and link-by-link feedback mechanism. This means, even if the intermediate sensor nodes are not capable of generating feedback, end-to-end feed- back mechanism can be used with buer sharing while the performance is close to RLNC without buer sharing and link-by-link feedback mechanism. Next, we we present the decoding delay performance. The decoding delay is the dier- ence between the rst time that the sink can decode all the packets of a generation and the time that the sources start transmission of that generation. The decoding delay is equal to min n t j gfd (t) = Kf ; 8f 2 F o . We divide the total delay by the generation size in order to obtain the normalized decoding delay. In RLNC without buer sharing, the sink decodes packets from dierent ows independently. Therefore, the decoding delay is dierent for 105 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs various ows. For RLNC without buer sharing, we consider the average delay of various ows in the network. Fig. 4.4 compares the normalized decoding delay for RLNC with and without buer sharing. Note that the type of feedback has no eect on the decoding delay since the rate at which the sink receives the innovative packets is independent of the feedback type. For = 1, the normalized decoding delay of RLNC with buer sharing is 30% higher than RLNC without buer sharing. As increases, the decoding delay of both techniques approaches since the number of lost packet diminishes and the eect of using network coding disappears. As Figs. 4.2 and 4.4 show, the power gain achieved by buer sharing is at the cost of a higher decoding delay. Next, we vary the number of sources from 10 to 30 with steps of 5. The number of intermediate nodes is 100 and the eld size is 100 m 100 m. The parameter is set to 2. Figs. 4.5 (a) and (b) show the power consumption of RLNC with and without buer sharing, respectively. These results are normalized to the number of sources. For RLNC with buer sharing, increasing the number of sources decreases the normalized power consumption for all both end-to-end and link-by-link feedback mechanisms. It is because the average number of ows passing each intermediate node increases. It provides more opportunities to combine the packets of dierent ows and save more power at the intermediate nodes. For RLNC without buer sharing, increasing the number of sources has a superposition eect and does not change the normalized power consumption. Finally, we vary the number of nodes from 60 to 140 with steps of 20 in the network while we keep the number of sources to be equal to 30. The eld size is increased from p 60 m p60 m to p140 m p140 m. The parameter is set to 2. Figs. 4.6 (a) and (b) compare dierent versions of the end-to-end and link-by-link feedback mechanisms. For both RLNC with and without buer sharing, the power consumption is increased by increasing the number of sources because the number of hops from the sources to the sink 106 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs 5 10 15 20 25 30 20 25 30 35 40 45 50 55 N or m al iz ed A ve ra ge P ow er C on su m pt io n Nnumber of Sources Endâˆ’toâˆ’end feedback mechanism after decoding Per flow endâˆ’toâˆ’end feedback mechanism Per flow per node endâˆ’toâˆ’end feedback mechanism Linkâˆ’byâˆ’link feedback mechanism (a) RLNC with buer sharing 5 10 15 20 25 30 20 21 22 23 24 25 26 27 N or m al iz ed A ve ra ge P ow er C on su m pt io n Number of Sources Endâˆ’toâˆ’end feedback mechanism Linkâˆ’byâˆ’link feedback mechanism (b) RLNC without buer sharing Figure 4.5: Normalized average power consumption versus the number of sources for = 2. is increased and more transmissions are required to deliver one packet to the sink. 4.5 Summary In this chapter, we studied the use of RLNC with buer sharing in wireless sensor networks. In RLNC with buer sharing, intermediate sensor nodes which relay information of multiple sources maintain one buer for ows towards the sink. Since the transmitted packets convey 107 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs 60 70 80 90 100 110 120 130 140 10 20 30 40 50 60 70 N or m al iz ed A ve ra ge P ow er C on su m pt io n Nnumber of Nodes Endâˆ’toâˆ’end feedback mechanism after decoding Per flow endâˆ’toâˆ’end feedback mechanism Per flow per node endâˆ’toâˆ’end feedback mechanism Linkâˆ’byâˆ’link feedback mechanism (a) RLNC with buer sharing 60 70 80 90 100 110 120 130 140 15 20 25 30 35 N or m al iz ed A ve ra ge P ow er C on su m pt io n Nnumber of Nodes Endâˆ’toâˆ’end feedback mechanism after decoding Linkâˆ’byâˆ’link feedback mechanism (b) RLNC without buer sharing Figure 4.6: Normalized average power consumption versus the number of nodes for = 2. information of multiple ows, it is not possible to distinguish which ow a packet belongs to after transmission. Through analytical modeling, we showed when an intermediate node can stop transmission of the packets for a particular ow without changing the average decoding delay of the sink. Then, we designed two feedback mechanisms, namely link-by- link and end-to-end, for RLNC with buer sharing. In link-by-link feedback mechanism, an intermediate node transmits feedback control packet to its upstream neighboring node and acknowledges each ow individually. The upstream node reduces its transmission 108 Chapter 4. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSNs rate when it receives a feedback packet. In end-to-end feedback mechanism, the sink is responsible of transmitting the feedback. We investigated the power eciency of both feedback mechanisms and compared the case with and without buer sharing, separately. Simulation results showed that for both feedback mechanisms, RLNC with buer sharing has a better power eciency compared to RLNC without buer sharing. The cost of achieving this gain is a longer delay in decoding the packets. 109 Chapter 5 Link Loss Inference in Wireless Sensor Networks with Random Linear Network Coding Due to the stochastic nature of the channels, communication links between sensors are also subject to fading and interference [1, 3]. Although techniques such as ARQ and forward error correction (FEC) can improve the reliability of packet transmission between the source nodes and the sink, energy and bandwidth constraints in WSNs impose barriers to deploying those techniques. Recent studies have shown that network coding can not only increase the network throughput in wired and wireless networks [7, 8, 11], but can also improve the robustness in systems with erasure channels [20, 25, 118]. Network coding outperforms ARQ and FEC techniques in terms of a lower delay and a higher network throughput [20]. Network coding also outperforms erasure codes since intermediate sensor nodes do not need to decode packets. It reduces the complexity of operation at intermediate sensor nodes and reduces the end-to-end delay. For both wireless and wired networks, it is of interest to monitor the behavior of the network, identify the link status, estimate the delay and loss rate of dierent links. Such a technique is called network tomography or network monitoring in the literature. Network tomography for wired and wireless networks has received much attention recently [26, 27, 28, 29, 30]. Network monitoring is especially important for WSNs as the information can 110 Chapter 5. Link Loss Inference in WSNs with RLNC allow sensor nodes to make decisions on routing and to bypass the links which are either congested or prone to failure. As mentioned in Chapter 1, network monitoring can be performed either in an active or passive manner [27]. Passive monitoring schemes are more attractive for WSNs because of the limited power supply and bandwidth constraints in these networks [31, 32]. The problem of supporting passive network monitoring by data aggregation techniques is stud- ied in [117, 119]. Identication of poorly performing links using end-to-end observations and maximum likelihood estimate in a WSN is studied in [120]. However, none of the above works use network coding for network monitoring. In [121], Gui et al. used a linear algebraic approach and proposed an active monitoring scheme for packet loss inference on mesh topologies. Active network monitoring using network coding is studied in [16]. The identiability challenge in active monitoring of coded packet networks is studied in [122]. Results in [123] show that for active monitoring techniques using network coding, appro- priate selection of the number and location of sources and destinations have a signicant impact on the accuracy of estimation. Network coding has also been used for topology inference. In [124], network coding and active network monitoring are used to study the topology inference problem. The passive monitoring of coded packet networks employing RLNC is studied in [125]. In this chapter, we focus on designing algorithms to infer the loss rate of dierent links in WSNs by passively monitoring the trac at the sink. All sensor nodes (including source nodes and intermediate nodes) are capable of performing RLNC. The link identication problem in coded packet networks is dierent from the traditional routed packet networks. In a coded packet network, the loss rate of a chosen path is the maximum loss rate of all the links of that path [20]. Therefore, it can be infeasible to infer the loss rate of the intermediate links by simply observing the path loss rate from the source node towards the 111 Chapter 5. Link Loss Inference in WSNs with RLNC sink. This behavior of the coded packet networks makes the link identication problem more challenging. However, we can benet from the coding operations performed at the intermediate nodes and extract information about the path loss rate from the intermediate nodes to the sink. The contributions of this chapter are as follows: By inspecting the contents of the received coded packets at the sink and adopting the subspace properties of network coding, we propose an estimation technique to estimate the path loss rates not only from the source nodes but also from several intermediate nodes to the sink. We characterize the conditions under which the link loss rate of a particular link can be estimated. We propose a passive loss inference with random linear network coding (PLI-RLC) algorithm using the proposed estimation technique to determine the loss rate of intermediate links in the network. Results show that our proposed algorithm has a lower percentage of false detection compared to a Bayesian inference algorithm [126]. The work in this chapter diers from the existing related work in the literature in several aspects. The problem of passive inference of the possible locations of link failures for multicast trac is studied in [127]. Our work diers from [127] in that (a) we consider unicast trac, and (b) sensor nodes are able to buer data packets and perform coding in order to improve the reliability of the system. In [126], the problem of passive loss inference in WSNs with network coding is studied. Our work diers from [126] in that we study the identiability problem and compute the loss rate of links precisely instead of merely categorizing the links as either good or bad. To the best of our knowledge, this work is the rst attempt to use the subspace properties in network coding for the link loss inference problem in WSNs. 112 Chapter 5. Link Loss Inference in WSNs with RLNC The rest of this chapter is organized as follows: In Section 5.1, the system model is introduced. In Section 5.2, we propose estimators to determine the path loss rate and an PLI-RLC algorithm to infer the link loss rate. In Section 5.3, we evaluate the performance of our proposed algorithm. A summary is given in Section 5.4. 5.1 System Model 5.1.1 Network Structure Consider aWSN. LetN = f1; 2; : : : ; Ng denote the set of sensor nodes and L = f1; 2; : : : ; Lg denote the set of directed wireless links. Let S denote the set of source nodes where S N . There is one sink node in the network. The data is gathered at the sink over a directed tree rooted at the sink. The leaves of the tree are source nodes. We notice that the intermediate nodes can be sources as well. With a tree structure, there is a unique path from every source node to the sink. We call the packets transmitted from source s to the sink as the ow of source s. Let P denote the set of paths in the network. Let Ps 2 P denote the path from source node s to the sink and Ls denote the set of links on path Ps. For any intermediate node i 2 N in the tree, the upstream ows are ows of those sources in S using node i as a relay. Fig. 5.1 shows a sample WSN with nodes 1, 2, 3, 4, and 7 as the source nodes. 5.1.2 Random Linear Network Coding (RLNC) Coded packet networks can provide reliable data gathering for WSNs. Each source has a stream of data packets to transmit towards the sink. Each packet is a sequence of symbols over a Galois eld GF (2q). For practical purposes, the source nodes group the packets into generations [118]. Each source transmits one generation at a time. When the sink 113 Chapter 5. Link Loss Inference in WSNs with RLNC 6 43 5 7 21 Sink P1 P4 P3 P7 P2 Figure 5.1: A sample WSN with ve sources, namely 1, 2, 3, 4, and 7. can decode the packets of one generation, the source moves to the next generation. Let K denote the size of each generation. Every source transmits packets periodically. Without loss of generality, sources transmit with a rate of one packet per second. Each sensor node can perform network coding by combining several incoming packets to create a coded packet. We assume the use of RLNC [128]. Each coded packet transmitted by node i 2 N is a weighted linear combination of the packets in the buer of node i using a set of random weights taken from GF (2q) called the coding coecients. Nodes append the coding coecients in the header of the coded packet to enable decoding at the sink. The vector of coecients is called the coding vector. Each sensor node has several buers to store the packets received from dierent upstream ows. Upon receiving a packet from ow s, the node checks whether the packet is linearly independent of the other packets currently stored in the buer of ow s. An incoming packet is placed in the buer if it is linearly independent of the currently buered packets. When a node transmits a packet of ow s, it linearly combines the stored packets in the buer of ow s using the random coding coecients. We slightly modify the randomized linear network coding for the monitoring purposes. In this modied version, an intermediate node with more than one incoming link randomly selects two ows from two dierent incoming links and combines the buers of those ows. 114 Chapter 5. Link Loss Inference in WSNs with RLNC These ows do not have common information about one source since they are from dierent incoming links. We notice that the intermediate node still relays two separate ows. In this case, some of the transmitted packets have information of more than one source. Since we assume that the maximum loss rate is 0.5 in the network, the input rate for innovative packets of both ows which are combined is at least 0.5. Therefore, for each of the transmitted ows, the intermediate node always has innovative packets to transmit and acts as a source. We show that merging the buers can help to derive information of the path from the intermediate node to the sink. The sink receives packets from jSj ows and stores the packets of every ow s at buer Bs. Since some of the intermediate nodes have combined dierent ows, buer of ow s may contain information of other sources as well. To decode the packets, the sink uses the buers of all ows. The sink can decode the data if it has KjSj linearly independent packets in dierent buers. We notice that the sink needs to keep dierent buers for monitoring purposes but not for decoding purposes. 5.2 Problem Formulation The objective is to study the link identication and loss inference problem for WSNs using the information obtained at the sink. We rst need to estimate the end-to-end path loss rates from the sources to the sink. Then the loss rate of links can be inferred using the information of path loss rates. In the next two subsections, we consider the path loss estimation and link identiability problems. 5.2.1 Path Loss Estimation In this subsection, the objective is to accurately estimate the loss rate of the paths in the WSNs by passively observing the data trac received at the sink. This is based on tracking the propagation of packets known as innovative packets from dierent source nodes. Such 115 Chapter 5. Link Loss Inference in WSNs with RLNC packets are innovative as they carry new, yet unknown, information generated by the source nodes. Let s(t) represent the subspace spanned by those coecients of the packets in Bs corresponding to the source s at time t. For example, if the rst K coecients of each coding vector belong to the source s 2 S, then s(t) is the subspace spanned by the rst K coecients of the packets in Bs at time t. The time at which the sink expects to receive the rst packet from a source depends on the distance (i.e., number of hops) between the source node and the sink. Let t1s denote the earliest time at which the sink can receive the rst packet of source s. Let ts denote the time at which the subspace s becomes full rank. The maximum rank of subspace s is equal to the number of packets generated by source s which is K. That is dim((ts)) = K. The rate at which buer Bs receives innovative packets from source s is the minimum rate at which the nodes on the path Ps receives packets [20]. This is equal to the minimum rate at which packets are transmitted on the links in Ls multiplied by the corresponding link success rates. Since the rate at which intermediate nodes relay the packets of ow s is one, the rate at which buer Bs receives innovative packets of source s is the minimum of the link success rate for the links in Ls. This is also considered as the the path loss rate of path Ps which can be written as 1: 1 s = min l2Ls f1 elg ; 8 s 2 S (5.1) where s is the loss rate of the path Ps and el denotes the link loss rate of link l. We assume the link loss rate is less than 0.5, since a link with loss rate greater than 0.5 should not be used in practice. At every second, buer Bs receives an innovative packet of source s with probability s. Therefore, the dimension of subspace (ts) has a negative binomial 1In the case of routing without network coding, we have (1 s) = Q l2Ls (1 el). 116 Chapter 5. Link Loss Inference in WSNs with RLNC distribution and it can be used to estimate the path success rate as: ~s(t) = 1 dim(s(t)) t t1s + 1 ; 8 s 2 S: (5.2) where ~s(t) is the estimation of s at time t. We notice that for values of t > ts, since the dimension of the subspace is not incremented, the estimator uses the last time slot which contains useful information for estimation which is ts. Therefore, we have ~s(t) = ~s(ts) for t > ts. The estimation error in ~(t) asymptotically follows a normal distribution with zero mean and variance 2s(t) as [129]: 2s(t) s(1 s) t t1s + 1 ; 8 t 2 [t1s; ts]; s 2 S: (5.3) We notice that t in fact cannot go to innity. The maximum value of t which can be used to estimate s is ts. At time ts, the network experiences the minimum achievable variance of estimation error. The minimum value for ts which can be achieved when there is no loss is equal to the size of the generation K, which is a design parameter. Thus, higher values of K can increase the accuracy of the estimation. However, it can impose additional delay to the decoding. Also, the intermediate nodes need additional memory capacity and the sink needs more computational capability for the decoding process. Hence, there is an inherent tradeo between the accuracy and the complexity. Given the path loss rates observed at the sink, it is challenging to infer the link loss rates as the number of variables (i.e., link loss rates) is more than the number of equations (i.e., path loss rates). From (5.1), the path loss rate s of a path Ps is an upper bound on the link loss rate el for all link l 2 Ls. We now show that more information can be obtained for the link loss rates in the network by taking into account the properties of the coded packet networks. We call an 117 Chapter 5. Link Loss Inference in WSNs with RLNC intermediate node with more than one incoming link as a virtual source. We note that an intermediate node can be a source node as well. In this case, we do not consider it as a virtual source since this assignment cannot provide more information. Let V denote the set of virtual sources in the network. For virtual source v, let Pv denote the path from the virtual source to the sink and Lv denote the set of links constructing path Pv. From the RLNC, every virtual source v 2 V combines the packets of two upstream ows. Therefore, among jSj ows received at the sink, there exists at least one ow which carries information of more than one upstream ows of the virtual source v. Let Bv denote the buer for that ow at the sink and let Sv denote the set of ows whose buers have been combined by the node v. We notice that this ow may contain information of other sources as well. For a virtual source v 2 V , let v(t) denote the subspace spanned by those coecients of the packets in Bv corresponding to the sources in Sv at time t. Let t1v denote the earliest time at which the sink can receive the rst packet in Bv. Let tv denote the time at which the subspace v becomes full rank. The rate at which the node v receives the innovative packets of the sources in Sv is greater than or equal to one since the packets received are from two dierent ows each with rate at least equal to 0.5 (this is from the assumption that we made on the minimum loss rate of the links). Therefore, the packets transmitted from node v are always innovative packets with respect to the generated packets of sources in Sv. Therefore, the node v can be considered as a source generating packets which contribute to the dimension of v. Thus, the behavior of the actual and virtual sources are similar if we monitor the dimension of v instead of s. We can use the following estimator to estimate the path loss rate for a path from virtual source v to the sink ~v(t) = 1 dim(v(t)) t t1v + 1 8 v 2 V ; (5.4) 118 Chapter 5. Link Loss Inference in WSNs with RLNC where ~v(t) is the estimate of v at time t. We notice that similar to s(t), for values of t > ts, we have v(t) = v(tv). Similar to the approximation proposed for the variance of the error obtained for ~s(t), the variance of error in the estimation of v can be obtained as follows: 2v(t) v(1 v) t t1s + 1 ; 8 t 2 [t1v; tv]; v 2 V : (5.5) 5.2.2 Identiability Problem The main objective of this chapter is infer the loss rate of the network links. However, it is not always possible to infer loss rates for all the links using end-to-end measurements. Given the topology of the network, we can classify the links in three sets: links which are not identiable, links which are possibly identiable, and links which are identiable. A link l is not identiable if for any assignment for the loss rates of the links in the network, we are not able to infer the link loss rate of link l using end-to-end measurement. The possible identication is a new notion of identiability introduced in this chapter. A link is possibly identiable if the identiability of the link depends on the loss rate of other links. That is, the link loss rate can be inferred for some assignments, but not for other assignments. For an identiable link, the loss rate can always be inferred independent of the loss rate of other links. For each directed link l 2 L, let head(l) and tail(l) denote the nodes attached to the head and tail of link l, respectively. That is, head(l) 2 N denotes the transmitter node of link l and tail(l) 2 N denotes the receiver node of link l. The following lemma helps to distinguish between these three groups of links. Lemma 8 For the directed link l 2 L: (a) It is identiable if head(l) 2 S [ V and tail(l) is the sink. (b) It is possibly identiable if head(l) and tail(l) 2 S [ V. 119 Chapter 5. Link Loss Inference in WSNs with RLNC (c) Otherwise, it not identiable. The proof of Lemma 8 is given in Section 5.5.1. Using the estimators presented in Section 5.2.1 and Lemma 8, we propose the passive loss inference with random linear network coding (PLI-RLC). Algorithm 5.1 shows the PLI-RLC algorithm. The algorithm monitors the incoming packets to the sink and estimates the loss rate of the links. The algorithm is composed of two parts. In the rst part (lines 318), the algorithm calculates the dimension of all subspaces at every time slot according to the buered packets and the packets which are received in that time slot. Then, it estimates the packet loss rate based on the dimension of the subspaces. We notice that the PLI-RLC algorithm is a passive monitoring algorithm and time t is the system time instead of the algorithm time. If at a time instance t, the variance of estimation error of all the path loss rates obtained using equation (5.3) is less than a certain threshold Eth, then the algorithm stops monitoring the received packets. In the second part of the algorithm (lines 1923), the algorithm determines the loss rates. 5.3 Performance Evaluation In this section, we evaluate the performance of the proposed estimators and our proposed PLI-RLC algorithm. Moreover, we compare our proposed PLI-RLC algorithm with the Bayesian inference algorithm [126]. We developed a discrete-event packet level simulator for the WSNs using MATLAB. For RLNC, the size of the generation K is set to 100. The Galois eld size q is equal to 8. We set the threshold value Eth to be equal to 5 104. 120 Chapter 5. Link Loss Inference in WSNs with RLNC Algorithm 5.1 - Passive Loss Inference with Random Linear Network Coding (PLI-RLC) Algorithm 1: input: network topology, sets S and V; output: link loss rates 2: for every generation 3: While at time slot t 4: for each source node s 2 S 5: if t t1s, 6: Calculate dim(s(t)). 7: Calculate ~s(t) using (5.2). 8: Calculate 2s(t) using (5.3) and s(t) ~s(t). 9: end for 10: for each virtual source v 2 V 11: if t t1v, 12: Calculate dim(v(t)). 13: calculate ~v(t) using (5.4). 14: Calculate 2v(t) using (5.5) and v(t) ~v(t). 15: end for 16: if t maxi2S[V t1i and 2i (t) < Eth; 8 i 2 S [ V 17: Break while. 18: end while 19: for each link l 2 L, 20: if (head(l), tail(l) 2 S [ V) 21: if ~head(l) > ~tail(l), 22: Set el := ~head(l). 23: end for 24: end for 5.3.1 Number of Identiable Links We investigate the performance of PLI-RLC algorithm on inferring the link loss rates. We consider the network in Fig. 5.1. For the link loss rate model, we follow the model proposed in [117]. For each link l 2 L, the probability distribution function that the loss rate of the link becomes el is f(el) = (1 el)(1); el 2 (0; 1]; (5.6) where is a tunable parameter. The mean of the link loss error rate is 1=(+1). The link loss rate on each link is randomly chosen from the distribution in (5.6). If the chosen link loss rate is greater than 0.5, we set it to 0.5. We vary the value of from 5 to 10. The 121 Chapter 5. Link Loss Inference in WSNs with RLNC 5 6 7 8 9 10 4.03 4.04 4.05 4.06 4.07 4.08 4.09 4.1 4.11 4.12 Î» Av er ag e nu m be r o f l in ks id en tif ie d Figure 5.2: Average number of links whose rates determined using PLI-RLC algorithm. PLI-RLC algorithm is run 100 times for each value of . Fig. 5.2 shows the average number of links whose loss rates can be inferred using our proposed PLI-RLC algorithm. Higher values of decreases the average of link loss rate in the network. When is increased from 5 to 10, the average number of link with determined loss rate is slightly decreased from 4.12 to 4.04. We notice that there are 2 identiable links and 5 possibly identiable links in this network. That is, from 5 possibly identiable links, on average the link loss rate of 2 can be determined by PLI-RLC algorithm. 5.3.2 Performance Comparison In this section, we compare our proposed PLI-RLC algorithm with the Bayesian inference algorithm proposed in [126]. In [126], the posterior probability of the link loss rate is derived given the observed path loss rates from sources to the sink. Then, a link is categorized as a good link if with probability greater than 0.5 the link loss rate is greater than a threshold . To compare our scheme with the one proposed in [126], we classify each link to be either a good or a bad link using the observations obtained from the PLI-RLC algorithm. 122 Chapter 5. Link Loss Inference in WSNs with RLNC 5 6 7 8 9 10 15 20 25 30 35 Î» Pe rc en ta ge o f f al se d et ec tio n Bayesian Inference PLIâˆ’RLC 14% 11% Figure 5.3: Comparison of false detection for PLI-RLC algorithm and Bayesian inference algorithm [126]. For link l 2 L whose loss rate is determined by the algorithm, we classify the link as a good link if the loss rate of the link is higher than . For a link l 2 L whose link loss rate cannot be determined using PLI-RLC algorithm, we derive the posterior probability of loss rate el using the observed path loss rates. Let f(el j fi; 8 i 2 S [ Vg) denote the probability distribution of link loss rate el for link l whose rate cannot be determined using the PLI-RLC algorithm. Assuming no a priori information on el, the posterior probability distribution function of el can be written as f(el j fi; 8 i 2 S [ Vg) = 8><>: 1 min fi2S[V j l2Lig fig ; if el minfi2S[V j l2Lig fig ; 0; otherwise: Link l is classied as a bad link if: Z 0 f(el j fi; 8 i 2 S [ Vg)del 1=2: (5.7) 123 Chapter 5. Link Loss Inference in WSNs with RLNC We use the PLI-RLC algorithm along with equation (5.7) to classify all the links as either good or bad links. We compare the performance of LPI-RLC and Bayesian inference algorithms using the ratio of false detection. A detection is false if we declare a good link as a bad link, or vice versa. We consider a WSN with 50 sensor nodes randomly deployed in a 100 m 100 m eld. 25 sensor nodes are randomly selected as the sources. Each source node selects the path with minimum power consumption among all the paths it has towards the sink. The link loss rates are selected randomly based on the distribution function in equation (5.6). The value of is varied from 5 to 10 and we measure the fraction of links whose status are detected incorrectly. The threshold value is set to 0.7. The results are averaged over 100 simulation runs. We notice that the number of links which participate in data communication in each simulation run depends on the topology of the network and the routing tree. Fig. 5.3 shows the false detection ratio when is varied from 5 to 10. Fig. 5.3 compares LPI-RLC and Bayesian inference algorithms for varying . Higher values of reduce the number of bad links in the network. As Fig. 5.3 shows, the false detection ratio is decreased when is increased. When is equal to 5, 32% of the links are bad links and 68% of them are good links. In this case, the percentage of the false detection in our algorithm is 14 percent less that of Bayesian inference algorithm. When is equal to 10, 11% of the links are bad links and 89% of them are good links and the percentage of the false detection in our algorithm is 11 percent better than that of the Bayesian inference algorithm. 5.4 Summary In this chapter, we studied the loss inference problem in WSNs while nodes perform ran- domized linear network coding. By using the subspace property of network coding, we 124 Chapter 5. Link Loss Inference in WSNs with RLNC proposed estimators to determine the path loss rate between a sink and a source. We showed that the intermediate nodes with multiple incoming links can be considered as vir- tual sources and we are able to determine the path loss rates from the virtual sources to the sink as well. We considered the assumption that there is no link with loss rate higher than 0.5 in the network in deriving the estimators. We characterized the conditions for a link to be either identiable, possibly identiable, or not identiable. We proposed a passive loss inference with random linear network coding (PLI-RLC) algorithm to determine the link loss rates. Simulation results showed that our proposed algorithm is accurate. It also has a lower percentage of false detection compared to the Bayesian inference algorithm. 5.5 Analytical Proof 5.5.1 Proof of Lemma 8 Consider a link l 2 L with two actual/virtual sources at the head and tail. Let head(l) and tail(l) denote the path loss rate from the nodes located at the head and tail of l to the sink, respectively. The relationship between the path and link loss rates can be expressed as head(l) = maxfel; tail(l)g; (5.8) where head(l) and tail(l) are observed values and el is an unknown variable. The loss rate of link l can be determined as head(l) if head(l) > tail(l). However, if head(l) tail(l), then the loss rate can have any value less than or equal to head(l). It means that for link l, we have el 8><>: = head(l) if head(l) > tail(l); head(l) if head(l) tail(l): (5.9) Therefore, such a link is possibly identiable. A link l is identiable if for any assignment 125 Chapter 5. Link Loss Inference in WSNs with RLNC of link loss rates, we have head(l) > tail(l). This only happens when tail(l) = 0 which means tail(l) is the sink. Now, consider link l while either head(l) or tail(l) is not actual/virtual source. Consider the case that tail(l) is not an actual/virtual source. tail(l) has one incoming link which is l. Let l0 denote the outgoing link of node tail(l). Any path including l should contain l0 as well. Therefore, from the point of view of sink, l and l0 are not distinguishable. Therefore, link l is not identiable for any pattern of link loss rates. The case that head(l) is not an actual/virtual source is similar. 126 Chapter 6 Cardinality Estimation in RFID Systems with Multiple Readers Tag estimation is widely used as a preliminary phase in ALOHA-based interrogation tech- niques [46, 47, 48]. Readers can adjust the frame size based on the estimation of tag population. Another application of tag estimation techniques, which has recently received attention, is the anonymous tracking of objects [49, 50]. In order to preserve the privacy and anonymity of the tag users, it may not be necessary to identify each individual user in some RFID applications. Instead, the goal is to estimate the total number of tags (or users) in the system. This is called the cardinality estimation (or tag population estima- tion) problem in RFID systems. In [49], Kodialam et al. proposed the zero-based and collision-based tag estimation techniques using a framed-slotted ALOHA model with a single reader. In [50], they ex- tended their work by introducing the enhanced-zero based (EZB) estimator, which is an asymptotically unbiased estimator. Using this technique, the mean and variance of the estimation error approach zero when the estimation process is repeated multiple times. Although the EZB algorithm can also be used for RFID systems with multiple readers, the variance of estimation error increases exponentially with the number of readers. In [47], Qian et al. proposed the lottery frame (LoF) scheme, which is a replicate-insensitive estimation protocol. LoF applies the hash functions with geometric distribution to tag IDs to select the time slots for transmission. 127 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers For large scale RFID systems, it is necessary to deploy multiple readers with overlapped interrogation zones to fully cover the area and achieve a high accuracy in the estimation. Consequently, a tag can be within the interrogation zone of several readers simultaneously. For tracking applications, which require privacy and anonymity of the users, each tag only transmits a portion of its ID to the reader when it is being queried. Thus, readers cannot identify uniquely the individual tags. Thus, those tags which are within the range of multiple readers may be counted multiple times. We call this problem the multiple counting problem. This motivates us to propose estimation algorithms which are capable of estimating the number of tags in such systems. In this chapter, we study the problem in two dierent conditions. First, we assume that readers cannot perform interrogation synchronously. We develop an asynchronous multiple-reader cardinality estimation (A- MRCE) algorithm under this condition. Then, we study the problem where the readers can be synchronized for interrogations, and we develop a synchronous multiple-reader cardinality estimation (S-MRCE) algorithm. The contributions of this chapter are as follows: We propose two maximum likelihood (ML) estimators, namely asynchronous and synchronous exclusive estimators to estimate the number of tags, which are exclu- sively within the interrogation zone of a reader. We show that the error for these estimators is asymptotically normal and the esti- mators are asymptotically unbiased. We derive upper bounds on the variance of the estimation error. The accuracy of these bounds is validated via simulations. We develop two estimation algorithms namely, A-MRCE and S-MRCE algorithms using asynchronous and synchronous exclusive estimators, respectively. We validate the analytical models, investigate the performance of our proposed es- 128 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers timators, and compare our proposed A-MRCE and S-MRCE algorithms with the EZB [50] and LoF [47] algorithms. Although all these algorithms are asymptotically unbiased, the variance of the estimation error for A-MRCE and S-MRCE algorithms increases linearly with the number of readers, while it increases exponentially for EZB and LoF algorithms. To the best of our knowledge, there is no prior work specically considering the problem of tag population estimation for RFID systems with multiple readers. Although EZB and LoF algorithms can be used in RFID systems with multiple readers, since they are not designed for such systems, they can have poor performance under some scenarios as shown in Section 6.4. On the contrary, both A-MRCE and S-MRCE algorithms can be used in large scale RFID systems. Since S-MRCE algorithm needs synchronous operation of readers, this algorithm is suitable for systems where readers can operate synchronously. The rest of this chapter is organized as follows: The system model is presented in Section 6.1. In Section 6.2, we rst propose an asynchronous exclusive estimator. Then, we propose an A-MRCE algorithm to estimate the total number of tags in the RFID system. In Section 6.3, we propose a synchronous exclusive estimator and an S-MRCE algorithm. Performance evaluation and comparison are presented in Section 6.4. A summary is given in Section 6.5. 6.1 System Model and Problem Statement 6.1.1 Notations and Model Consider an RFID system with multiple readers. Readers use framed-slotted ALOHA protocol for interrogations. This is the model proposed in EPCglobal Gen2 standard [45]. We consider a xed frame size for an interrogation process. Each reader broadcasts a query 129 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers message, which includes information such as the frame size f , persistence probability p, and a random seed q at the beginning of the interrogation process. Each tag decides whether or not to transmit in the current frame based on the persistence probability p. If a tag decides to transmit, it selects a time slot based on a uniform distribution related to its ID, the persistence probability p, and the random seed q. Note that given the specic values of the frame size f , the random seed q, and persistence probability p, the tag selects exactly the same slot in a frame of size f , regardless of how many times it has received the query message. To perform dierent interrogations, readers can alter the seed q. The interrogation results are independent whenever a dierent seed q is being used. Multiple interrogations are used to improve the accuracy of the estimation process. To preserve the anonymity and privacy of the users, each tag only transmits part of its ID to the reader in the reply message. Therefore, the reader cannot individually identify the tags. Throughout this chapter, we assume that the interrogation time is fast enough such that the tags do not leave or enter the interrogation zone of a reader. According to EPCglobal Gen2 standard [45], the average duration of a time slot is less than 1 ms which is much smaller than the average time that the tags move around the system. We now introduce some of the notations. Let N and R denote the number of tags and the set of readers in the system, respectively. Let Tr denote the set of tags within the zone of reader r 2 R. Let nr denote the number of tags in the interrogation zone of reader r 2 R (i.e., nr = jTrj). We use nW to denote the number of tags within the range of a set of readersW (i.e., nW = j \w2W Twj). Two readers are called neighboring readers if there is a tag which is in the interrogation range of both of the readers. LetHr denote the set of other readers which are neighbors of reader r. For reader r, let vr = (v 1 r ; : : : ; v f r ) denote the vector created after performing an interrogation process, where vlr (with l = 1; : : : ; f) indicates whether the lth time slot is empty (i.e., vlr = 0) or has at least one transmission (i.e., 130 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 0 1 v1 Interrogation zones v2 r1 r2 Tag Reader Figure 6.1: An RFID system with two readers r1 and r2. nr1 = 6, nr2 = 7, N = 11, f = 10, and p = 1. vlr = 1). The number of elements of vector vr is equal to the frame size f . We call vector vr as the interrogation vector of reader r. Assume reader r performs M interrogations using M dierent seed values. We use vectors v1r ; : : : ;v M r to denote these interrogation vectors. Fig. 6.1 shows a two-reader RFID system with overlapped interrogation zones and the interrogation vectors. 6.1.2 Multiple Counting Problem For an RFID system with multiple readers, by adding up the number of tags within the zone of all readers, one can obtain an estimator for the number of tags. Since some tags may appear in the zone of several readers, they are counted multiple times by dierent readers. Therefore, the estimation may not be accurate especially for dense RFID systems. To obtain an accurate estimate for the number of tags, the number of tags in the overlapped areas of neighboring readers is required in addition to the number of tags within the zone of each reader. In the estimation process, once a tag is counted by a reader, other readers should exclude that tag from their estimations. The total number of tags is the summation of the number of tags estimated by all the readers, while each reader excludes the tags that have already been counted by other readers. In general, for jRj readers r1; : : : ; rjRj 2 R 131 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers with overlapping interrogation zones, the total number of tags N in the system is N = jTr1 j+ jTr2nTr1 j+ + jTrjRjnfTr1 [ [ TrjRj1gj: (6.1) Note that the order chosen to calculate N has no eect on the nal result. Moreover, if reader rj 2 R shares no tags with readers r1; : : : ; rj1, then TrjnfTr1 [ [ Trj1g = Trj . As (6.1) suggests, in order to estimate N , the number of tags within the zone of a reader needs to be estimated. We call such an estimator single reader estimator. Moreover, we need to estimate the number of tags which are only within the zone of a reader but are not in the zone of some other readers (e.g., jTr2nTr1 j). To estimate the number of tags which are exclusively located within the zone of a reader, we propose two estimators in the next sections, namely asynchronous exclusive and synchronous exclusive estimators. For the single reader estimator, we use the estimator proposed in [50]. Assume that reader r has performed M interrogations using M dierent seed values, the we have v1r ; : : : ;v M r . Let tm denote the number of empty slots in vmr ; m = 1; : : : ;M . Using the EZB algorithm, the number of tags within the zone of reader r can be estimated as [50]: ~nr = f=p ln MX m=1 tm=Mf ! : (6.2) It is shown in [50] and [130] that the estimation error is asymptotically normal and unbi- ased. The variance of the estimation error is 2nr = f (exp(pnr=f) (1 + p2nr=f)) =(Mp2). We will use this estimator in both A-MRCE and S-MRCE algorithms. 132 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 6.2 Asynchronous Multiple Reader Cardinality Estimation In some practical cases, it may not be possible for the readers to perform interrogations in a synchronous manner. This models the case when the readers are not equipped with accurate clocks or synchronization imposes a high overhead. Under such condition, we develop an asynchronous multiple reader cardinality estimation (A-MRCE) algorithm. The A-MRCE algorithm is used to estimate the total number of tags while readers perform interrogations independently and forward the information to a central controller. The A- MRCE algorithm implements (6.1) using asynchronous exclusive estimator described in the following subsection. 6.2.1 Asynchronous Exclusive Estimator The asynchronous exclusive estimator is used to estimate the number of tags within the zone of a particular reader excluding the tags shared with some other readers, while read- ers perform interrogations independently. It facilitates implementation of equation (6.1). Consider reader r and a set of readersW Hr. Let nrnW denote the number of tags within the zone of reader r that do not belong to any of the readers in setW (i.e., jTrn[w2W Twj). Given the number of tags within the zone of readers inW , nW , we propose an asynchronous exclusive estimator to estimate nrnW . Consider a time slot which is non-empty in vector vr. This indicates that one or more tags within the range of reader r has chosen that time slot. If this time slot is empty in vw for any w 2 W , it ensures that none of the tags within the range of readers in W has chosen that slot. Let variable Z denote the number of time slots which are nonempty in vr and empty in vw; 8 w 2 W . That is, given reader r 2 R and set W , we have 133 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers Z = Pf l=1 v l r Q w2W(1 vlw). The time slots, which are non-empty in vr and empty in vw, are chosen by a subset of tags in the set fTrnf[w2WTwgg. This suggests that the variable Z can be used to estimate nrnW . The following theorem characterizes the distribution of variable Z. Theorem 5 The random variable Z has a normal distribution with mean z and variance 2z for large values of f , nrnW and nW : z = f 1 exp pnrnW f exp pnW f : (6.3) 2z = z 1 z=f 1 + p2nW f p2nrnW exp 2p f (nrnW + nW) : (6.4) The proof of Theorem 5 is given in Section 6.6.1. By using the interrogation vectors v1r ; : : : ;v M r , and v 1 w; : : : ;v M w , 8 w 2 W , one can obtain M samples of the random vari- able Z, namely z1; : : : ; zM . Let z denote a vector composed of all the samples (i.e., z = z1; : : : ; zM ). From Theorem 5, the likelihood function of z given nrnW and nW is L z;nrnW ; nW = MY m=1 1p 22z exp (z m z)2 22z ! : (6.5) The maximum likelihood (ML) estimate of nrnW is the value that maximizes the log- likelihood function as follows: ~nMrnW = arg max nrnW lnL z;nrnW ; nW = arg max nrnW ( M 2 ln 2z MX m=1 (zm z)2 22z ) : (6.6) In practice, nW is not given and an estimation should be used instead. Let ~nMW denote the estimation of nW using M interrogation vectors. Since lnL z;nrnW ; nW is convex, by taking its derivative and equating to zero, we can nd the closed form expression for the 134 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers ML estimator. For large values of M (e.g., M > 10) and f (e.g., f > 100), the exclusive estimator in (6.6) can be approximated as ~nMrnW ( nrnW z 1M MX m=1 zm = 0 ) = f p ln 1 PM m=1 z m Mf exp p~nMW f ! : (6.7) Eq. (6.7) is the asynchronous exclusive estimator. In the next subsection, we explain how nW can be estimated. The inaccuracy in estimation of nrnW comes from the random nature of samples taken from the system and also the error in estimation of nW . The following theorem characterizes the error of the estimator in (6.7). Theorem 6 Given the error in estimation of nW follows a normal distribution, for large values of M and f , the error in estimation of nrnW using (6.7) has a normal distribution. Moreover, this estimator is asymptotically unbiased if the mean of error in estimation of nW approaches zero for large values of M . The variance of error is bounded by 2nrnW (M) 1 p2 exp 2p nrnW + nW f ! 2z M exp pnrnW f 1 2 2nW (M); (6.8) where 2nrnW (M) and 2 nW (M) are the variance of errors in estimation of nrnW and nW using M independent set of interrogation vectors, respectively. The proof of Theorem 6 is given in Section 6.6.2. We will compare 2nrnW (M) and its upper bound in Section 6.4. 6.2.2 A-MRCE Algorithm We now present the A-MRCE algorithm to estimate the total number of tags in an RFID system with multiple readers. The A-MRCE algorithm is a centralized algorithm. The controller is a centralized unit which is responsible to estimate the total number 135 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers Algorithm 6.1 A-MRCE Algorithm executed at reader r 2 R. 1: Upon receiving parameters p;q, and f from the controller, reader r performsM interrogation processes using seed values q. 2: Reader r sends its location info and the interrogation vectors v1r ; : : : ;v M r to the controller. Algorithm 6.2 A-MRCE Algorithm executed at the controller. 1: Input: Set of readers R, neighboring set Hr of reader r, and the interrogation vectors of reader r; 8r 2 R. 2: Initialization: Set ~N := 0, and := fg 3: while 6= R 4: Select a reader r randomly from the set Rn. 5: Set W := \Hr. 6: if W = fg 7: Calculate ~nr using (6.2). 8: Set ~N := ~N + ~nr. 9: else 10: Calculate ~nW using (6.2) if jWj = 1 or using A-MRCE algorithm if jWj > 1. 11: Calculate ~nrnW using asynchronous exclusive estimator (6.7). 12: Set ~N := ~N + ~nrnW . 13: end if 14: Set := [ frg. 15: end while of tags in the system. Each reader performs interrogations individually and transmits its interrogation vectors to the controller. The controller uses these vectors to estimate the number of tags. The A-MRCE algorithm, which is shown in Algorithms 6.1 and 6.2, implements equation (6.1) using the single reader and the asynchronous exclusive estimators. Algorithm 6.1 shows part of the A-MRCE algorithm performed by a reader r 2 R. Algorithm 6.2 shows part of the A-MRCE algorithm performed by the controller. When the algorithm is invoked, the controller informs the persistence probability p, frame size f , and a set ofM random seeds q (i.e., jqj =M) to all the readers. Each reader r 2 R then performs M interrogation processes and sends the interrogation vectors (v1r ; : : : ;v M r ) to the controller. The readers also inform the controller about their location by sending the location information to the controller. Hr is the set of readers whose interrogation 136 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers vectors overlap with the interrogation zone of reader r. Based on the interrogation range of each reader and its location, the set Hr of neighboring readers of reader r can also be determined. The readers may encounter reader-to-tag and reader-to-reader collision during their interrogations. To avoid the collision, several techniques have been proposed in the literature [131, 132, 133, 134, 135] for RFID systems with multiple readers. However, it is not the focus of this chapter and we assume that the readers employ one of these techniques to perform interrogations. After receiving the required information (interrogation vectors and location informa- tion) from all the readers, the controller estimates the total number of tags using asyn- chronous exclusive estimator by invoking Algorithm 6.2. Algorithm 6.2 is equivalent to applying equation (6.1) iteratively to estimate the total number of tags. Steps 4 14 denote one iteration of the algorithm. At each iteration, the algorithm selects a reader r randomly from the readers which have not been selected yet (i.e., Rn). Then, the con- troller calculates the number of tags within the range of the selected reader which have not already been counted and adds it to ~N . The set W denotes the set of neighbors of reader r which have been selected by the algorithm in the previous iterations (i.e., the tags within the range of the readers in the set W have been counted till now). If this set is empty, the algorithm uses the single reader estimator in (6.2) to calculate ~nr and adds this number to the current estimation of the total number of tags ~N (Steps 69). If the set W is non-empty, then the algorithm uses the asynchronous exclusive estimator to calculate ~nrnW . To do so, the asynchronous exclusive estimator requires the value of ~nW . If the set W has only one member, then ~nW can be calculated using single reader estimator in (6.2). Otherwise, the controller invokes the A-MRCE algorithm (Algorithm 6.2) recursively to estimate the number of tags within the range of readers in the set W . The recursion ends at maximum after jWj iteration. This shows a recursive operation of 137 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers the A-MRCE algorithm. We notice that since the controller already has the interrogation vectors of all the readers including those in set W , it does not need to ask the readers to perform interrogations again. 6.2.3 Estimation Error and Discussion To estimate ~nrnW , the asynchronous exclusive estimator uses the estimation of nW . There- fore, the A-MRCE algorithm needs to calculate ~nW . If the set W has one element, then the single reader estimator can be used and the estimation error in estimating nW has a normal distribution with zero mean. If the setW has more than one reader, the algorithm is invoked again to estimate nW . This gives a recursive operation of the A-MRCE algo- rithm. In the recursive procedure, the rst level of the estimation is obtained by using the asynchronous exclusive estimator which has an error with normal distribution and zero mean. Based on Theorem 6, the next levels have also an estimation error with normal distribution and zero mean. Consequently, the estimation of nW has a normal distribution with zero mean. We now describe how to determine the estimation error for the A-MRCE algorithm. The value of ~N obtained by the A-MRCE algorithm is composed of several estimations from the single reader and the asynchronous exclusive estimators. All the readers con- tribute to the estimation of ~N . Since dierent terms for ~N are from either single reader or asynchronous exclusive estimators, they have asymptotically normal distributions with zero mean. Therefore, ~N has asymptotically normal distribution with zero mean. In gen- eral, dierent terms of ~N are not independent. However, the summation of the variance of error of these terms can give an upper bound for the variance of the error for A-MRCE algorithm. The summation of the variances depends on the order that readers are selected in the algorithm (Step 4 of Algorithm 6.2). 138 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers For pure random selection of the readers (Step 4 of Algorithm 6.2), we calculate the expected value of the summation of variances over dierent runs of the algorithm. For reader r 2 R with jHrj neighbors, let Qr denote the power set of Hr. The power set of a set is the set of all subsets of that set. In dierent runs of the A-MRCE algorithm, the number of tags within the zone of reader r may appear in various forms in ~N . For example, it can be either ~N := ~N + ~nr or ~N := ~N + ~nrnW for any W 2 Qr. For set W 2 Qr, the probability that ~N contains ~nrnW is equal to the probability that only readers in set W from the neighbors of r are selected before reader r within the algorithm run. Assuming that the reader selection is purely random, this probability is equal to the probability that among reader r and its neighbors (i.e., Hr), readers in set W are selected before reader r. The probability that any subset of neighbors of r with cardinality jWj is selected by the algorithm before reader r is 1=(jHrj+ 1) and the number of such subsets is jHrj jWj . Let PnrnW denote the probability that nrnW appears in ~N . This probability can be written as PnrnW = 1 (jHrj+ 1) jHrj jWj : (6.9) Therefore, when the reader r is selected within the algorithm run, with probability PnrnW we have W = \ Hr; 8 W 2 Qr. The expected value for the summation of variances of errors in ~N gives an upper bound on the variance of estimation error 2asyn: 2asyn X r2R X W2Qr PnrnW 2 nrnW : (6.10) 139 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 6.3 Synchronous Multiple Reader Cardinality Estimation (S-MRCE) We proposed the A-MRCE algorithm in the previous section based on the assumption that readers cannot be synchronized for interrogations. In this section, we consider the case that readers have the ability to be synchronized for interrogations (e.g., they are equipped with accurate clocks). We develop a synchronous multiple reader cardinality estimation (S- MRCE) algorithm, which is suitable for RFID systems with multiple synchronized readers. The readers operate synchronously in a sense that they start interrogation at certain times and perform interrogations periodically one after another. We rst propose a synchronous exclusive estimator, which is a building block of the S-MRCE algorithm. 6.3.1 Synchronous Exclusive Estimator The synchronous exclusive estimator is developed to estimate nrnW for W Hr using interrogation vectors obtained from synchronous operation of the readers. The main idea behind the operation of the synchronous exclusive estimator is the use of dierent seed values for dierent tags in one interrogation. In fact, the reader performs interrogation while the shared tags (i.e., the tags in Tr \ f[w2WTwg) and the tags which are exclusively located within the range of the reader have dierent seed values. Consider reader r, the set of readers W Hr, and the vector vr obtained from the interrogation of tags within the range of r using seed value q. Also, consider vector ur obtained from the interrogation of tags in Tr while the tags in Trnf[w2WTwg) use seed value q and the tags in Tr \f[w2WTwg use seed value q0. Since the tags select the same slot whenever they are interrogated with the same seed value, vectors vr and ur have common information about nrnW . The dierence between these two vectors comes from the shared tags, which have been interrogated with 140 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers dierent seed values. The number of slots with at least one transmission in either vr or ur represents the existence of a tag in set Tr while the tags in Tr \ f[w2WTwg are counted twice. Let Y denote the number of time slots which are nonempty either in vr or ur. That is, given reader r 2 R and set W , we have Y =Pfl=1 vlr + ulr vlrulr. The samples of random variable Y can be used to estimate the value of nrnW . The following theorem characterizes the distribution of variable Y . Theorem 7 The random variable Y has a normal distribution with mean y and variance 2y for large values of f , nr, and nrnW as y = f (1 exp (p=f)) ; (6.11) 2y = f exp (p=f) 1 (1 + p2) exp (p=f) ; (6.12) where = (2nr nrnW). The proof is similar to the proof given in [136] for the occupancy problem. Using M dierent pairs of seed values for the tags in Trnf[w2WTwg and Tr\f[w2WTwg, M dierent samples of random variable Y can be obtained, namely y1; : : : ; yM . Let y denote the vector of all samples (i.e., y = y1; : : : ; yM ). The likelihood function of nrnW using y is similar to that obtained in (6.5) if the mean and variance of variable Z is replaced by variable Y . The ML estimate of nrnW with M dierent samples can be obtained by taking derivative from the likelihood function and equating it to zero similar to the approach used for (6.6). For large values of M (e.g., M > 10) and f (e.g., f > 100), the synchronous exclusive 141 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers estimator can be approximated as nÌ‚MrnW ( nrnW y 1M MX m=1 ym = 0 ) = 2nr + f p ln 1 PM m=1 y m Mf ! ; (6.13) where nÌ‚MrnW denotes the estimation of nrnW using the synchronous exclusive estimator with M samples. When using the synchronous exclusive estimator, we use an estimation of nr. This estimation is obtained using the single reader estimator which is asymptotically unbiased. For large values of M , P m y m=M converges to y and ln (1 P m y m=(Mf)) converges to p=f. Since the error in the estimation of nr approaches zero, the syn- chronous exclusive estimator is asymptotically unbiased. Since it is an ML estimator, the error distribution is asymptotically normal [137]. The error in the estimation of nr is also asymptotically normal and is added to the error generated from the random samples taken from the system. Assume that there is no error in estimation of nr. In this case, the error in nÌ‚MrnW originates from the second term in (6.13). Since the synchronous exclusive estima- tor is an ML estimator, the variance of error can be approximated using the Cramer-Rao bound [137]. The Fisher information for this exclusive estimator can be written as Isyn(nrnW) = EyjnrnW ( @ @nrnW lnL(y;nrnW) 2) = EyjnrnW 8<: @ @nrnW ln MY m=1 1p 22y exp (y m y)2 22y !!29=; : (6.14) Equation (6.14) can be approximated as Isyn(nrnW) 0y 2 2z = p2 f (1 (1 + p2) exp (p=f)) ; (6.15) 142 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers where 0y denotes the derivative of y with respect to nrnW . Now, we calculate the vari- ance of estimation error. The variance of estimation error for nrnW is E[ ~nrnW nrnW 2 ]. Replacing ~nrnW from (6.13), we have 2nrnW (M) = E h ~nrnW nrnW 2i = E 24 2 (~nr nr) + f p ln 1 PM m=1 y m Mf ! !!235 : (6.16) If we replace ~nr from (6.2), we obtain 2nrnW (M) = E 24 2 f=p ln MX m=1 tm=Mf ! nr ! + f p ln 1 PM m=1 y m Mf ! + !!235 : Let 1 = f=p ln PM m=1 t m=Mf nr and 2 = f=p ln 1PMm=1 ym=Mf+ . Then, we have 2nrnW (M) = 4E[ 2 1 ] + E[ 2 2 ] + 2E[ 1 2]. t m denotes the number of empty slots in the interrogation vector using mth seed value while ym denotes the number of non- empty slots. If the average of tm for various seed values is less than nr , then the average of ym is above . Therefore, E[ 1 2] is always non-positive and we have 2 nrnW (M) 4E[ 21 ] + E[ 2 2 ]. Replacing E[ 2 1 ] by 2 nr and E[ 2 1 ] by MIsyn(nrnW) 1 , we obtain 2nrnW (M) MIsyn(nrnW) 1 + 42nr : (6.17) 6.3.2 S-MRCE Algorithm We now present the S-MRCE algorithm to estimate the total number of tags in a system covered by multiple readers. On contrary to the A-MRCE algorithm, the S-MRCE algorithm is a distributed approach where readers perform interrogation and estimate the number of tags individually. Then, they transmit their estimation to the controller. The 143 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers Algorithm 6.3 S-MRCE Algorithm to calculate the total number of tags in the system. 1: The controller sends the parameters p, f , vector q, and random slot numbers fs1; : : : ; sjRjg to all readers. 2: for k = 0; : : : ; jRj 1 3: if sr = k, 4: Reader r starts periodic interrogation process using seed vector q. 5: end if 6: end for 7: for r 2 R 8: Reader r calculates ~nr using (6.2) and calculates ~nrnW using synchronous exclusive estimator (6.13). 9: Reader r sends the estimated value ~nrnW to the controller. 10: end for 11: The controller sums up the received value from all readers to nd the estimation of N . controller just sums up those numbers to obtain the estimation of the total number of tags. The computation load of estimation is at the reader's side. The S-MRCE algorithm implements (6.1) using the synchronous exclusive estimator. Algorithm 6.3 shows the S- MRCE algorithm. In this algorithm, all the readers are assumed to be synchronized with a central clock. We divide the system time into several time periods and each reader is assigned a period number. Each reader performs an interrogation within the assigned period. To prevent collision between neighboring readers, we use a scheduling algorithm based on graph coloring [138]. We assign dierent colors to various readers such that two neighboring readers are not assigned the same color. The chromatic number of the system is the minimum number of colors needed to color all the readers. Let C denote the chromatic number of our system. The colors are interpreted as dierent time periods of the system. This provides a time division multiple access method for interrogation of all the readers. There are C interrogation periods assigned to the readers. Let sr denote the period number which is assigned to the reader r. Each period is long enough for an interrogation process. At the beginning, the controller informs the persistence probability p, frame size f , the 144 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers random seed vector q = (q1; : : : ; qM), where qi 6= qj; 8 i; j, and the slot number to all the readers (Step 1). We call the C slots together an interrogation round. Within an interrogation round, all the readers perform the interrogation once. To estimate the number of tags, all the readers perform interrogation twice in two consecutive rounds. In the rst round, all the readers announce their seed value and then perform interrogation. In the second round, however, the readers just perform the interrogation and do not announce the seed value. For the reader r, the rst interrogation results in measuring interrogation vector vr while all the tags within range of reader r are interrogated with the same seed value. In the second interrogation, the reader r measures vector ur while the tags in the range of reader r which are in the range of other readers have dierent seed value compared to those exclusively in the range of reader r. To make sure that neighboring readers are not using the same seed value, reader with slot number sr used the sr-th seed value. We assume that the chromatic number C is less that the number of samples M . To obtain M samples, the interrogation rounds are repeated M times with dierent seed values. We call this synchronous process performed by every reader the periodic interrogation process (Step 4). After performing the interrogations by all the readers, each reader r uses the vectors obtained by announcing the seed value to estimate nr. Reader r calculates the estimated value of nrnW using the estimation of nr and also two sets of interrogation vectors vr and ur (Step 8). Reader r sends the estimation of nrnW to the controller (Step 9). The controller can calculate the estimation of the total number of tags by adding up all values received from the readers (Step 11). Since the error of synchronous exclusive estimator has normal distribution with zero mean, the estimation of N obtained by using the S-MRCE algorithm has normal error dis- tribution and is asymptotically unbiased. The upper bound for the variance of estimation 145 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers r3 r7 r4 r6 r8 r9 r1 r5 r10 (b) r2 Figure 6.2: Network topologies: (a) Three readers, and (b) Ten readers. error for the S-MRCE algorithm can be calculated using a similar approach employed to calculate the variance of the A-MRCE algorithm. The upper bound can be written as 2syn X r2R X W2Qr PnrnW 2 nrnW ; (6.18) where 2nrnW is derived in (6.17). Compared to the A-MRCE algorithm, the S-MRCE algorithm provides better performance in terms of the estimation of error. The probability of error of asynchronous exclusive estimator increases exponentially with nW . When the number of neighboring readers increases, the probability of error for asynchronous exclusive estimator increases rapidly. However, the error of synchronous exclusive estimator depends on the number of tags within the zone of the reader, but not the neighboring readers. The cost which is paid to achieve this better performance is the need of the synchronous operation of readers. The estimation error of A-MRCE and S-MRCE algorithms depends on the choice of design parameters f and p. To choose these parameters appropriately, the controller re- quires to know the number of tags in the system. In case that the controller does not have a priori information about the number of tags in the system, the controller can choose 146 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 5 10 15 20 25 30 35 40 45 50 0 10 20 30 40 50 60 70 80 90 100 Number of interrogations M M ea n of E st im at io n Er ro r n r = 1000 n r = 750 n r = 500 5 10 15 20 25 30 35 40 45 50 1 2 3 4 5 6 7 8 9 10 Number of interrogations M M ea n of E st im at io n Er ro r n r = 1000 n r = 750 n r = 500 (a) (b) Figure 6.3: Mean of estimation error for dierent number of interrogations M , (a) asyn- chronous exclusive estimator, and (b) synchronous exclusive estimator. predetermined values for f and p and perform a round of interrogations. Then, based on the estimation of the number of tags, the controller chooses f and p for the next round of interrogation. 6.4 Performance Evaluation We used MATLAB and developed a discrete-event RFID simulator to validate the analyt- ical models and to evaluate the performance of the exclusive estimators and the MRCE algorithms. 6.4.1 Performance Evaluation for Exclusive Estimators In this section, we investigate the performance of the exclusive estimators, validate the models, and compare them in terms of the mean and variance of the estimation error. We rst consider the topology given in Fig. 6.2 (a). The interrogation zone of each reader is 15 m. The tags are randomly deployed within the zone of readers. The number of tags within 147 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 5 10 15 20 25 30 35 40 45 50 0 20 40 60 80 100 120 140 160 180 Number of Interrogations, M St an da rd D ev ia tio n of E rro r Upper Bound âˆ’ n r =750 Simulation âˆ’ n r =750 Upper Bound âˆ’ n r =500 Simulation âˆ’ n r =500 Upper Bound âˆ’ n r =250 Simulation âˆ’ n r =250 Figure 6.4: Standard deviation of estimation error for dierent number of interrogations M when using an asynchronous exclusive estimator. the zone of all readers is equal. The number of tags shared between any two of readers is 15% of nr. Also, 5% of the tags are shared among three of them. We use asynchronous and synchronous exclusive estimators to estimate nr3nW where W = fr1; r2g. The estimation of nW , is obtained as ~nW = ~nr1 + ~nr2nr1 , where ~nr1 and ~nr2nr1 are obtained by using (6.2) and (6.5), respectively. We notice that nrnW = 0:75nr. First, we investigate the performance of the models by varying the number of interro- gationsM from 1 to 50. We set the frame size f to 500 and the persistence probability p to 1. We measure the mean and variance of the estimation error for both asynchronous and synchronous exclusive estimators. These errors contain the errors in estimation of ~nW and ~n3 as well. Figs. 6.3 (a) and (b) show that both estimators are asymptotically unbiased and the mean of the error approaches zero rapidly when M increases in the system. Figs. 6.4 and 6.5 show the standard deviation of error obtained from simulations and compare these values with analytical upper bounds obtained in equations (6.8) and (6.17). For both estimators, the variance of error approaches zero for large values of M . As shown in Figs. 148 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 5 10 15 20 25 30 35 40 45 50 0 50 100 150 200 250 300 350 400 Number of Interrogations, M St an da rd D ev ia tio n of E rro r Upper Bound âˆ’ n r =2000 Simulation âˆ’ n r =2000 Upper Bound âˆ’ n r =1000 Simulation âˆ’ n r =1000 Upper Bound âˆ’ n r =500 Simulation âˆ’ n r =500 Figure 6.5: Standard deviation of estimation error for dierent number of interrogations M when using the synchronous exclusive estimator. 6.4 and 6.5, the upper bounds are tight when the number of tags within the zone of readers is small. Next, we investigate the behavior of these estimators for dierent number of tags within the range of readers. We use the notion of operational range for comparison. The oper- ational range of the estimators is dened as the the range of nr such that the mean of estimation error is within a certain threshold of the actual value. We use 1% as the threshold. The lower bound of the range is always zero and the upper bound depends on frame size f and persistence probability p. Lowering the persistence probability p can decrease the eective number of tags transmitting in an interrogation process and it can increase the operational range. The analytical models for the estimators are valid as long as nr is within the operational range. We vary the number of tags within the zone of each reader from 100 to 10,000 by steps of 50. Fig. 6.6 shows the mean of estimated value for asynchronous and synchronous exclusive estimators for two values of persistence probability, p = 1 and p = 0:5. The mean of estimation for the asynchronous exclusive 149 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 Number of Tags, n r M e a n o f e s t im a t io n o f n r \ W Actual number of tags Syn. Exclusive Estimator âˆ’ p = 0.5 Syn. Exclusive Estimator âˆ’ p = 1 Asyn. Exclusive Estimator âˆ’ p = 0.5 Asyn. Exclusive Estimator âˆ’ p = 1 Figure 6.6: The mean of estimation error for varying number of tags, asynchronous and synchronous exclusive estimators. estimator is within the 1% of the actual value of n3nW for values of n3 less than 1,100 and 2,200 for p = 1 and p = 0:5, respectively. These indicated the operational range of the estimators. The values beyond these thresholds are out of the operational range of the estimator. These values for synchronous exclusive estimator are 2,600 and 5,500 for p = 1 and p = 0:5, respectively. The operational range of the exclusive estimators is a function of the persistence proba- bility. Fig. 6.7 shows the operational range of the asynchronous and synchronous exclusive estimators for various values of p. The operational range is extended when the probability is decreased. Although decreasing p can increase the operational range, it may increase the estimation error under some circumstances, especially for the systems with a low number of tags. Figs. 6.8 (a) and (b) show the behavior of the standard deviation of the error versus the persistence probability for the asynchronous and synchronous exclusive estima- tors, respectively. We notice that the values of nr equal to 1000 and 2000 are not in the operational range of the asynchronous exclusive estimator. Therefore, Fig. 6.8 (a) does not include the curves for 1000 and 2000 nodes. Both estimators have similar behavior 150 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 10 20 30 40 50 60 70 Persistence Probability, p O pe ra tio na l R an ge (L oa d F ac tor ) Syn. Exclusive Estimator Asyn. Exclusive Estimator Figure 6.7: Operational range of asynchronous and synchronous exclusive estimators for varying persistence probabilities. in terms of variance of error. For the systems with a small number of tags compared to the frame size, the variance of the estimation error increases when p decreases. Therefore, p = 1 is a suitable choice in terms estimation error. On the other hand, for large values of nr compared to the frame size, decreasing the persistence probability can improve the error to some extent. However, for very small persistence probabilities, the error start increasing again. There is a trade o between the operational range and the variance of error in choosing the design parameter p. 6.4.2 Performance Evaluation for A-MRCE and S-MRCE Algorithms In this section, we rst investigate the performance of the A-MRCE and S-MRCE algo- rithms for a system with ten readers shown in Fig. 6.2 (b). The interrogation zone of each reader has a range equal to 15 m. The tags are randomly deployed within the interrogation 151 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 10 15 20 25 30 35 40 Persistence Probability p St an da rd D ev ia tio n of E rro r n r = 750 n r = 500 n r = 250 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 5 10 15 20 25 30 35 40 Persistence Probability p St an da rd D ev ia tio n of E rro r n r = 2000 n r = 1000 n r = 750 n r = 500 n r = 250 (a) (b) Figure 6.8: Standard deviation of error for varying persistence probabilities: (a) asyn- chronous exclusive estimator, (b) synchronous exclusive estimator. zone of the readers. We set the frame size f to be 500 time slots, the persistence probability p to 1, and M to 50. Then, we increase the total number of tags in the system from 500 to 5000 with steps of 500. These numbers are chosen such that the single reader and exclusive estimators work in their operational range (i.e., the mean of estimation error is zero). Fig. 6.9 shows the standard deviation of error for the A-MRCE and S-MRCE algorithms and compares the analytical results obtained in (6.10) and (6.18) with the simulation results. The simulation results are averaged over 1000 iterations. As we expect, the analytical values provide upper bounds on the simulation results for both algorithms. In the worst case, the analytical results are 40% and 30% higher than the simulation results. As Fig. 6.9 shows, the standard deviation of error is small compared to the actual number of tags in the system, which proves the accuracy of the algorithms. Moreover, it can be seen that the S-MRCE algorithm outperforms the A-MRCE algorithm substantially in terms of estimation error. However, we notice that S-MRCE is not suitable for cases when readers cannot perform synchronously in the system. Next, we compare the A-MRCE and S-MRCE algorithms with two other algorithms: 152 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 0 20 40 60 80 100 120 Total Number of Tags N St an da rd D ev ia tio n of E rro r Aâˆ’MRCE âˆ’ Upper Bound Aâˆ’MRCE âˆ’ Simulation Sâˆ’MRCE âˆ’ Upper Bound Sâˆ’MRCE âˆ’ Simulation Figure 6.9: Comparison of A-MRCE and S-MRCE in terms of standard deviation of error. the lottery frame (LoF) [47] and EZB [50] algorithms. Both EZB and LoF algorithms can also be extended to estimate the number of tags for systems with multiple readers. To achieve that, the interrogation vectors of all the readers in the system are merged using slot-wise and operator. The resulting vector is similar to a vector obtained by a single reader interrogating all the tags in the system. Therefore, this vector can be used as an input for the EZB or LoF algorithm to estimate the total number of tags in the system. We compare these algorithms for a system with three readers and ten readers separately. First, we compare the mean and variance of estimation error of A-MRCE, S-MRCE, LoF, and EZB algorithms for various interrogation times for an RFID system with three readers shown in Fig 6.2 (a). The number of tags within the range of each reader is 750. Figs. 6.10 (a) and (b) show the mean and standard deviation of error in estimating the total number of tags versus the interrogation time, respectively. The interrogation time is dened as the number of time slots that each reader requires to perform interrogation. The frame size for A-MRCE, S-MRCE, and EZB algorithms is set to 500 while it is set to 153 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 500 1000 1500 2000 2500 3000 3500 4000 0 5 10 15 20 25 30 35 40 Number of Time Slots M ea n of E st im at io n Er ro r EZB Aâˆ’MRCE Sâˆ’MRCE LoF 500 1000 1500 2000 2500 3000 3500 4000 0 50 100 150 200 250 Number of Time Slots St an da rd D ev ia tio n of E st im at io n Er ro r LoF EZB Aâˆ’MRCE Sâˆ’MRCE (a) (b) Figure 6.10: Comparing dierent algorithms in terms of interrogation time (number of time slots), (a) mean of estimation error, and (b) standard deviation of estimation error. 16 for LoF. We vary the number of interrogations for various algorithms (change M and the number of hash functions) and determine the mean and variance of estimation error. Fig. 6.10 (a) shows that LoF algorithm has a lower mean of estimation error compared to other algorithms for the same interrogation times. Then, LoF has a wider operational range compared to other schemes. However, as Fig. 6.10 (b) shows, the variance of estimation error is higher in LoF compared to other algorithms. Next, we consider the system in Fig. 6.2 (b). The number of tags within the zone of dierent readers is nr = 500. The frame size f is set to 500 time slots for A-MRCE, S-MRCE, and EZB algorithms while the frame size of the LoF is set to 16. The number of interrogations M is set to 20 for A-MRCE and EZB algorithms and it is set to 10 for S- MRCE algorithm. We use 600 various hash functions for the LoF algorithm. We notice that under this setting, the readers in all the algorithms have the same interrogation time. We also mention that the mean of estimation error is close to zero for all the estimators under this setting. At the beginning, we only consider reader 1 for the simulations. Then, we add the readers one by one to the system and investigate the performance of the algorithms 154 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 1 2 3 4 5 6 7 8 9 10 0 20 40 60 80 100 120 140 160 180 200 Number of Readers St an da rd D ev ia tio n of E rro r EZB LoF Aâˆ’MRCE Sâˆ’MRCE Figure 6.11: Comparing the standard deviation of estimation error for A-MRCE, S-MRCE, EZB [50], and LoF [47] algorithms. in the presence of dierent number of readers. Fig. 6.11 shows the standard deviation of the estimation error for the total number of tags for various number of readers. It can be seen that the standard deviation of error in the A-MRCE and S-MRCE algorithms seems to grow linearly with the number of readers while it seems to increase exponentially in LoF and EZB algorithms. In the presence of multiple readers, EZB and LoF algorithms merge the interrogation vectors of several readers to obtain one interrogation vector. For a xed number of tags within the range of the readers, increasing the number of readers would linearly increase the total number of tags in the system. Since both algorithms use the merged interrogation vector for estimation and the variance of the estimation error for either EZB and LoF algorithms increases exponentially with the number of tags, the variance of EZB and LoF algorithms increases exponentially as the number of readers linearly increases. However, for the A-MRCE and S-MRCE algorithms, whenever a reader is added to the system, only the error of the exclusive estimator which is used to estimate the tags within range of that reader is added to the total error. Therefore, the increase in 155 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers the error is linear as the number of readers increases linearly. 6.5 Summary In this chapter, we studied the problem of anonymous cardinality estimation in RFID systems with multiple readers. We proposed two ML estimators, namely an asynchronous exclusive estimator and a synchronous exclusive estimator, to estimate the number of tags which are exclusively located within the zone of a reader. We showed that these estimators are asymptotically unbiased and we derived upper bounds on the variance of estimation error. We proposed the A-MRCE and S-MRCE algorithms which can accurately estimate the tag population anonymously using the query replies of dierent readers and exclusive estimators. We derived the probability density function of the estimation error and showed that it can be approximated as a normal distribution with zero mean. The accuracy of the model and the approximations are validated via simulations. For performance comparisons, results showed that the variance of estimation error for A-MRCE and S-MRCE algorithms increase linearly with the number of readers while it increases exponentially for EZB [50] and LoF[47] algorithms. 6.6 Analytical Proofs 6.6.1 Proof of Theorem 5 Let z and z denote the event that z predetermined slots are nonempty in vr and empty in vw; 8 w 2 W , respectively. Let z denote the event that both events z and z occur. 156 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers We have P(z) = P (z \ z) = P(z j z)P( z), where P(z j z) = nrnWX t=0 P(z j t tags pick these z slots) P(t tags pick these z slots j z): The condition on observed z aects the upper bound of the summation. The probability that z time slots are non-empty if t tags choose them is as follows [139, p. 92]: P(z j t tags pick these z slots) = zX k=0 (1)k z k 1 z f t : We also have P ( t tags pick these z slots j z) = nrnW t pz f t 1 pz f (nrnWt) : Hence, we have P(z) = nrnWX t=0 zX k=0 (1)k z k 1 k f t nrnW t pz f t 1 pz f (nrnWt) = zX k=0 (1)k z k 1 pk f nrnW : Therefore, we can write P(z) as P(z) = 1 pz f nw zX k=0 (1)k z k 1 pk f nrnW : Let Sz denote the summation of probability of all possible occurrences of z events in a frame. This is equal to Sz = f z P (z). Let Pz denote the probability of having exactly z slots nonempty in vr and empty in vw;8 w 2 W . This probability can be calculated using 157 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers [139, p. 96] as follows: Pz = fX m=z (1)mz m z Sm = fX m=z (1)mz m z f m P (m): (6.19) Equation (6.19) shows that this problem is similar to the occupancy problem investi- gated in [130]. It is shown in [130, 136] that the distribution for the occupancy problem is asymptotically normal. Using a similar approach, we can show that Z has a normal distribution for large values of f and nr. To calculate the mean and variance of Z, we use the approach presented in [136]. We dene an auxiliary random variable Xi which takes values from f0; 1g. Xi is equal to one if the ith time slot is non-empty in vr and empty in vw; 8w 2 W . Therefore, we have Z = Pf i=1Xi. The mean and variance of variable Z can be obtained using this auxiliary variable as follows: z = E[Z] = E " fX i=1 Xi # = fP1 f 1 exp pnrnW f exp pnW f : 2z = E 24 fX i=1 Xi !235 2z = fX i=1 E X2i + 2E " fX i=1 fX j=i+1 XiXj # = fP1 + f(f 1)P2 2z z 1 z f 1 + p2nW f p2nrnW exp 2p f (nrnW + nW) : 158 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers 6.6.2 Proof of Theorem 6 We replace P m z m M and ~nW by z + eMz and nW + e M n , respectively while e M z and e M n are random variables. Since variable Z has a normal distribution, variable eMz is a normal random variable with zero mean and variance 2z=M . Moreover, it is assumed that ~nW is a normal random variable and the estimation is asymptotically unbiased. Therefore, eMn is a normal random variable with zero mean. For large values of f and M , the variance of eMz and e M n approaches zero and we have ~nrnW = f p ln 1 P m z m Mf exp p~nW f = f p ln 1 z + e M z f exp p nW + eMn f !! f p ln 1 z + e M z f 1 + p=feMn exp pnW f ! f p ln 1 z f exp pnW f e M z + zp=fe M n f exp pnW f f p ln 1 z f exp pnW f e M z =p+ z=fe M n 1 z=f exp pnW f exppnW f nrnW e M z p exp p nW + nrnW f ! eMn exp pnrnW f 1 : Since both variables eMz and e M n are normal random variables, variable ~nW is a normal random variable for large values of M . Moreover, the mean of error approaches zero for large values ofM . Variables eMz and e M n are dependent in general since they are both derived from the same vectors vr and vw. e M n is the error in estimation of nW . If e M n is positive, it means that the average number of empty slots in vectors vw in dierent interrogations is greater than the expected value of the empty slots. Since z is the number of slots which are non-empty in vr and empty in vw, the average of z m for various interrogations is less 159 Chapter 6. Cardinality Estimation in RFID Systems with Multiple Readers than z which means e M z is negative. Therefore, the errors e M w and e M r always cancel out each other. Consequently, the summation of variances for these two terms gives an upper bound for the variance of error as follows: 2nrnW = 1 p2 exp 2p nrnW + nW f ! 2z M + exp pnrnW f 1 2 2nW : 160 Chapter 7 Conclusions and Future Work In this chapter, we conclude the thesis by summarizing our results and highlighting the contributions of this dissertation. We also suggest several topics for further research. 7.1 Research Contributions In this thesis, we proposed several power-ecient algorithms for WSNs using optimization theory and network coding in Chapters 2, 3, 4, and 5. We have also considered the problem of anonymous cardinality estimation in RFID systems with multiple readers in Chapter 6. In Chapter 2, we studied the problem of WSNs with multiple sinks and we formulated two algorithms to fairly share the network resources among various commodities and nodes in the system using the concept of lexicographical fairness. We rst proposed the centralized LOCL algorithm to obtain the exact lexicographically optimal solu- tion. LOCL is a stepwise algorithm. In each step, a linear mixed-integer program- ming problem is being solved. Our second algorithm, called the LONL algorithm, is a distributed algorithm. It can obtain the optimal solution under certain assump- tions, and the sub-optimal solutions in general. The LONL algorithm is easier for implementation and more practical for deployments. In Chapter 3, we studied the tradeo between network lifetime and system resources utilized to perform network coding for multicast trac in WSNs. We proposed a 161 Chapter 7. Conclusions and Future Work set of new variables called the coding ow variables. Using coding ow variables, we can determine the type of the operation and the rate at which the operation is per- formed in each sensor node. Then, we formulated the joint problem of constructing maximum-lifetime minimum-resource coding subgraph as a linear programming prob- lem. The complexity of our algorithm increases linearly by the number of nodes and number of sessions, and it increases exponentially by the number of sinks. Hence, the algorithm is suitable for networks with a large number of sessions while each session has a small number of sinks. In Chapter 4, we studied the use of RLNC with buer sharing in WSNs. Through analytical models, we showed when an intermediate node can stop transmission of the packets for a particular ow. Based on this model, we designed a link-by-link and an end-to-end feedback mechanism for RLNC with buer sharing. In link-by-link feedback mechanism, an intermediate node transmits feedback control packet to its upstream neighboring node and acknowledges each ow individually. The upstream node reduces its transmission rate when it receives a feedback packet. In end-to- end feedback mechanism, the sink is responsible of transmitting the feedback. We investigated the power eciency of both feedback mechanisms and compared the case with and without buer sharing, separately. In Chapter 5, we studied the loss inference problem in wireless sensor networks while nodes performs randomized linear network coding. By using the subspace property of network coding, we proposed estimators to determine the path loss rate between a sink and a source. We showed that the intermediate nodes with multiple incoming links can be considered as virtual sources and we are able to determine the path loss rates from the virtual sources to the sink as well. We considered the assumption that there is no link with poor condition in the network in deriving the estimators. We 162 Chapter 7. Conclusions and Future Work characterized the conditions for a link to be either identiable, possibly identiable, or not identiable. We proposed a passive loss inference with random linear network coding (PLI-RLC) algorithm to determine the link loss rates. In Chapter 6, we studied the problem of anonymous cardinality estimation in RFID systems with multiple readers. The goal was to estimate the number of tags within range of multiple readers while tags do not reveal their IDs. We proposed an asyn- chronous exclusive estimator and a synchronous exclusive estimator, to estimate the number of tags which are exclusively located within the zone of a reader. We derived upper bounds on the variance of estimation error for these estimators. Using these estimators, we proposed the A-MRCE and S-MRCE algorithms which can accurately estimate the tag population anonymously. We showed that these algorithms result in asymptotically unbiased estimations. We derived the probability density function of the estimation error and showed that it can be approximated as a normal distribution with zero mean. The accuracy of the model and the approximations are validated via simulations. 7.2 Suggestions for Future Work In the following, we consider several interesting possibilities for extension of the current work. 1. Lexicographically Optimal Routing for WSNs with Multiple Sinks. Both LOCL and LONL algorithms can be extended to enable the source nodes to select the appropriate sink. Alternatively, the problem can be formulated such that the optimal location for the sinks is determined while the network lifetime is being maximized. 2. Lifetime-Resource Tradeo for Multicast Trac in WSNs. One can extend 163 Chapter 7. Conclusions and Future Work the model by considering the problem of determining the optimal location of coding devices while the objective is to maximize the network lifetime. The lifetime-resource tradeo can also be studied for networks such that the multicast rate cannot be achieved without using network coding. 3. Feedback Mechanism for RLNC with Buer Sharing in Lossy WSN. One can study the eect of limited buers on operation of RLNC with buer sharing. Another direction is to consider the eect of lossy feedback on the performance of RLNC with buer sharing. 4. Link Loss Inference in WSNs with RLNC. For PLI-RLNC algorithm, the inter- mediate network nodes keep separate buers for dierent ows. The algorithm can be extended if the intermediate nodes can keep shared buers for separate ows. The accuracy of the algorithm can be improved in this case since more information can be revealed from the network. Another direction of problem extension is to consider a carrier sense multiple access MAC protocol for the purpose of link loss inference. 5. Cardinality Estimation in RFID Systems with Multiple Readers. One can study the problem of choosing the design parameters (e.g., frame size f , persistence probability p) based on the initial estimation of the number of tags and study the tradeo between the variance of estimation error and interrogation time. 164 Bibliography [1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, \Wireless sensor networks: A survey," Elsevier Computer Networks Journal, vol. 38, pp. 393{422, Mar. 2002. [2] I. F. Akyildiz and M. C. Vuran, Wireless Sensor Networks. John Wiley & Sons, 2010. [3] A. Goldsmith and S. Wicker, \Design challenges for energy-constrained ad hoc wire- less networks," IEEE Trans. on Wireless Communications, vol. 9, pp. 8{27, Aug. 2002. [4] K. Romer and F. Mattern, \The design space of wireless sensor networks," IEEE Wireless Communications, vol. 6, pp. 54{61, Dec. 2004. [5] J. Chang and L. Tassiulas, \Energy conserving routing in wireless ad-hoc networks," in Proc. of IEEE INFOCOM, Tel-Aviv, Israel, March 2000. [6] ||, \Maximum lifetime routing in wireless sensor networks," IEEE/ACM Trans. on Networking, vol. 12, pp. 609{619, Aug. 2004. [7] R. Ahlswede, N. Cai, S. R. Li, and R. W. Yeung, \Network information ow," IEEE Trans. on Information Theory, vol. 46, pp. 1204{1216, July 2000. [8] R. Koetter and M. Medard, \An algebraic approach to network coding," IEEE/ACM Trans. on Networking, vol. 11, pp. 782 {795, Oct. 2003. [9] T. Cui, L. Chen, and T. Ho, \Distributed optimization in wireless networks using broadcast advantage," in Proc. of IEEE Conference on Decision and Control, New Orleans, LA, Dec. 2007. [10] S. Yang, J. Wu, and M. Cardei, \Ecient broadcast in MANETs using network coding and directional antennas," in Proc. of IEEE INFOCOM, Phoenix, AZ, Apr. 2008. [11] J. Zhang, P. Fan, and K. B. Letaief, \Network coding for ecient multicast routing in wireless ad-hoc networks," IEEE Trans. on Communications, vol. 56, no. 4, pp. 598{607, Apr. 2008. 165 Bibliography [12] C. Fragouli, J. Widmer, and J. Y. Le Boudec, \Ecient broadcasting using network coding," IEEE/ACM Trans. on Networking, vol. 16, no. 2, pp. 450{463, Apr. 2008. [13] S.-Y. R. Li, R. W. Yeung, and N. Cai, \Linear network coding," IEEE Trans. on Information Theory, vol. 49, pp. 371{381, Feb. 2003. [14] T. Ho, M. Medard, J. Shi, M. Eros, and D. R. Karger, \On randomized network coding," in Proc. of Allerton Conference on Communication, Control, and Comput- ing, Monticello, IL, Oct. 2003. [15] T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Eros, J. Shi, and B. Leong, \A random linear network coding approach to multicast," IEEE Trans. on Information Theory, vol. 52, pp. 4413{4430, Oct. 2006. [16] C. Fragouli, J. Widmer, and J. Y. Le Boudec, \Energy ecient broadcasting in wire- less ad-hoc networks using network coding," in Proc. of First Workshop on Network Coding (NetCod), Riva del Garda, Italy, Apr. 2005. [17] ||, \A network coding approach to energy ecient broadcasting: from theory to practice," in Proc. of IEEE INFOCOM, Barcelona, Spain, Apr. 2006. [18] J. Liu, D. Goeckel, and D. Towsley, \Bounds on the gain of network coding and broadcasting in wireless networks," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. [19] A. Keshavarz-Haddad and R. Riedi, \Bounds on the benet of network coding: Throughput and energy saving in wireless networks," in Proc. of IEEE INFOCOM, Phoenix, AZ, Apr. 2008. [20] T. Ho and D. S. Lun, Network Coding: An Introduction. Cambridge University Press, 2008. [21] D. S. Lun, N. Ratnakar, M. Medard, R. Koetter, D. R. Karger, T. Ho, E. Ahmed, and F. Zhao, \Minimum-cost multicast over coded packet networks," IEEE Trans. on Information Theory, vol. 52, pp. 2608{2623, June 2006. [22] J. Park and S. Sahni, \An online heuristic for maximum lifetime routing in wireless sensor networks," IEEE Trans. on Computers, vol. 55, pp. 1048{1056, 2006. [23] K. Bhattad, N. Ratnakar, R. Koetter, and K. R. Narayanam, \Minimal network coding for multicast," in Proc. of IEEE International Symposium on Information Theory (ISIT), Adelaide, Australia, Sept. 2005. [24] D. S. Lun, M. Medard, and M. Eros, \On coding for reliable communication over packet networks," in Proc. of 42nd Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct. 2004. 166 Bibliography [25] D. S. Lun, M. Medard, R. Koetter, and M. Eros, \On coding for reliable communi- cation over packet networks," Physical Communication, vol. 1, no. 1, pp. 3{20, Mar. 2008. [26] Y. Tsang, M. Coates, and R. Nowak, \Passive unicast network tomography using EM algorithm," in Proc. of IEEE Int'l Conf. on Acoustics, Speech, and Signal Processing, Salt Lake City, Utah, May 2001. [27] M. Coates, A. Hero III, R. Nowak, and B. Yu, \Internet tomography," IEEE Signal Processing Mag., vol. 19, no. 3, pp. 47{65, May 2002. [28] Y. Chen, D. Bindel, H. Song, and R. Katz, \An algebraic approach to practical and scalable overlay network monitoring," in Proc. of ACM SIGCOMM, Portland, OR, Sept. 2004. [29] N. G. Dueld, J. Horowitz, F. Lo Presti, and D. Towsley, \Multicast topology infer- ence from measured end-to-end loss," IEEE Trans. on Information Theory, vol. 48, no. 1, pp. 26{45, Jan. 2002. [30] N. Dueld, \Network tomography for binary network perfromance characteristics," IEEE Trans. on Information Theory, vol. 52, no. 12, pp. 5373{5388, Dec. 2006. [31] C. Hsin and M. Liu, \A distributed monitoring mechanism for wireless sensor net- works," in Proc. of ACM Workshop on Wireless Security, Atlanta, GA, Apr. 2002. [32] J. Zhao, R. Govindan, and D. Estrin, \Computing aggregates for monitoring wireless sensor networks," in Proc. of IEEE Int'l Workshop on Sensor Network Protocols and Applications, Anchorage, AK, May 2003. [33] R. Want, \An introduction to RFID technology," IEEE Pervasive Computing, vol. 5, pp. 25 { 33, Jan./Mar. 2006. [34] S. Ahson and M. Ilyas, RFID Handbook: Applications, Technology, Security, and Privacy. CRC Press, 2008. [35] P.-Y. Chen, W.-T. Chen, Y.-C. Tseng, and C.-F. Huang, \Providing group tour guide by RFIDs and wireless sensor networks," IEEE Trans. on Wireless Commun., vol. 8, pp. 3059{3067, June 2009. [36] A. Bletsas, S. Siachalou, and J. N. Sahalos, \Anti-collision backscatter sensor net- works," IEEE Trans. on Wireless Commun., vol. 8, pp. 5018{5029, Oct. 2009. [37] D. Shih, R. Sun, D. Yen, and S. Huang, \Taxonomy and survey of RFID anti-collision protocols," Computer Communications, vol. 29, pp. 2150{2166, July 2006. [38] J. Myung and W. Lee, \Adaptive splitting protocols for RFID tag collision arbitra- tion," in Proc. of ACM MobiHoc, Florence, Italy, May 2006. 167 Bibliography [39] C. Floerkemeier, \Bayesian transmission strategy for framed Aloha based RFID pro- tocols," in Proc. of IEEE Int'l Conf. on RFID, Grapevine, TX, Mar. 2007. [40] Y.-C. Ko, S. Roy, J. R. Smith, H.-W. Lee, and C.-H. Cho, \An enhanced dynamic RFID multiple access protocol for fast inventory," in Proc. of IEEE Globecom, Wash- ington, DC, Nov. 2007. [41] J. S. Choi, H. Lee, D. W. Engels, and R. Elmasri, \Robust and dynamic bin slotted anti-collision algorithms in RFID systems," in Proc. of IEEE Int'l Conf. on RFID, Las Vegas, NV, Apr. 2008. [42] H. Koh, S. Yun, and H. Kim, \Sidewalk: A RFID tag anti-collision algorithm ex- ploiting sequential arrangements of tags," in Proc. of IEEE ICC, Beijing, China, May 2008. [43] J.-B. Eom, T.-J. Lee, R. Rietman, and A. Yener, \Ecient framed-slotted Aloha algorithm with pilot frame and binary selection for anti-collision of RFID tags," IEEE Commun. Letters, vol. 12, pp. 861{863, Nov. 2008. [44] C.-H. Quan, J.-C. Choi, G.-Y. Choi, and C.-W. Lee, \The Slotted-LBT: A RFID reader medium access scheme in dense reader environments," in Proc. of IEEE Int'l Conf. on RFID, Las Vegas, NV, Apr. 2008. [45] EPCglobal, \EPC Radio-Frequency Identity Protocols Class-1 Generation-2 UHF RFID Protocol for Communications at 860 MHz-960 MHz Version 1.2," May 2008. [Online]. Available: http://www.epcglobalinc.org/standards/uhfc1g2 [46] G. Maselli, C. Petrioli, and C. Vicari, \Dynamic tag estimation for optimizing tree slotted Aloha in RFID networks," in Proc. of ACM MSWiM, Vancouver, Canada, Oct. 2008. [47] C. Qian, H. Ngan, and Y. Liu, \Cardinality estimation for large-scale RFID systems," in Proc. of IEEE Percom, Galveston, TX, Mar. 2008. [48] S.-R. Lee, S.-D. Joo, and C.-W. Lee, \An enhanced dynamic framed slotted Aloha algorithm for RFID tag identication," in Proc. of Int'l Conf. on Mobile and Ubiq- uitous Systems: Networking and Services, San Diego, CA, July 2005. [49] M. Kodialam and T. Nandagopal, \Fast and reliable estimation schemes in RFID systems," in Proc. of ACM Mobicom, LA, CA, Sept. 2006. [50] M. Kodialam, T. Nandagopal, and W. C. Lau, \Anonymous tracking using RFID tags," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. [51] D. P. Bertsekas, Network Optimization: Continuous and Discrete Models. Athena Scientic, 1998. 168 Bibliography [52] F. Glover, \Improved linear integer programming formulations of nonlinear integer problems," Management Science, vol. 22, pp. 455{460, Dec. 1975. [53] O. Mangasarian and R. Meyer, \Nonlinear perturbation of linear programs," SIAM Journal on Control and Optimization, vol. 17, pp. 745{752, 1977. [54] M. Friedlander and P. Tseng, \Exact regularization of convex programs," SIAM Journal on Optimization, vol. 18, pp. 1326{1350, Nov. 2007. [55] V. Shah-Mansouri and V. W. S. Wong, \Distributed maximum lifetime routing in wireless sensor networks based on regularization," in Proc. of IEEE Globecom, Wash- ington, DC, Nov. 2007. [56] ||, \Bounds for lifetime maximization with multiple sinks in wireless sensor net- works," in Proc. of IEEE Pacic Rim Conference on Communications, Computers and Signal Processing, Victoria, Canada, Aug. 2007. [57] V. Shah-Mansouri, A. H. Mohsenian-Rad, and V. W. S. Wong, \Multicommodity lifetime routing for wireless sensor networks with multiple sinks," in Proc. of IEEE ICC, Beijing, China, May 2008. [58] ||, \Lexicographically optimal routing for wireless sensor networks with multiple sinks," IEEE Trans. on Vehicular Technology, vol. 58, pp. 1490{1500, Mar. 2009. [59] V. Shah-Mansouri and V. W. S. Wong, \Maximum-lifetime coding subgraph for multicast trac in wireless sensor networks," in Proc. of IEEE GLOBECOM, New Orleans, LA, Dec. 2008. [60] ||, \Lifetime-resource tradeo for multicast trac in wireless sensor networks," IEEE Trans. on Wireless Commun., vol. 9, pp. 1924{1934, June 2010. [61] ||, \Link loss inference in wireless sensor networks with randomized network cod- ing," in Proc. of IEEE Globecom, Miami, FL, Dec. 2010. [62] ||, \Anonymous cardinality estimation in RFID systems with multiple readers," in Proc. of IEEE Globecom, Honolulu, HI, Dec. 2009. [63] ||, \Cardinality estimation in RFID systems with multiple readers," IEEE Trans. on Wireless Communications, vol. 10, no. 5, pp. 1458{1469, May 2011. [64] A. Ephremides, \Energy concerns in wireless networks," IEEE Wireless Commun., vol. 9, pp. 48{59, Aug. 2002. [65] J. Chang and L. Tassiulas, \Routing for maximum system lifetime in wireless ad-hoc networks," in Proc. of Allerton Conference Communication, Control, and Computing, Urbana, Illinois, Sept. 1999. 169 Bibliography [66] T. Brown, H. Gabow, and Q. Zhang, \Maximum ow-life curve for a wireless ad hoc network," in Proc. of ACM MobiCom, Long Beach, CA, Oct. 2001. [67] A. Giridhar and P. R. Kumar, \Maximizing the functional lifetime of sensor net- works," in Proc. of the Fourth International Conference on Information Processing in Sensor Networks (IPSN), Los Angeles, CA, April 2005. [68] H. Zhang and J. C. Hou, \On deriving the upper bound of -lifetime for large sensor networks," in Proc. of ACM MobiHoc, Roppongi Hills, Japan, May 2004. [69] M. Bhardwaj, T. Garnett, and A. Chandrakasan, \Upper bounds on the lifetime of sensor networks," in Proc. of IEEE ICC, Helsinki, Finland, July 2001, pp. 785{790. [70] R. Madan and S. Lall, \Distributed algorithms for maximum lifetime routing in wireless sensor networks," IEEE Trans. on Wireless Communications, vol. 5, pp. 2185{2193, Aug. 2006. [71] R. Madan, S. Cui, S. Lall, and A. Goldsmith, \Cross-layer design for lifetime maxi- mization in interference-limited wireless sensor networks," IEEE Trans. on Wireless Communications, vol. 5, pp. 3142{3152, Nov. 2006. [72] H. Nama, M. Chiang, and N. Mandayam, \Optimal utility-lifetime trade-o in self- regulating wireless sensor networks a distributed approach," in Proc. of 40th An- nual Conference on Information Sciences and Systems (CISS), Princeton, NJ, March 2006. [73] J. Zhu, S. Chen, B. Bensaou, and K. Hung, \Tradeo between lifetime and rate allocation in wireless sensor networks: A cross layer approach," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. [74] Y. Xue, Y. Cui, and K. Nahrstedt, \Maximizing lifetime for data aggregation in wire- less sensor networks," ACM/Kluwer Mobile Networks and Applications (MONET), vol. 10, pp. 853{864, Dec. 2005. [75] Y. Hou, Y. Shi, and H. D. Sherali, \On node lifetime problem for energy- constrained wireless sensor networks," ACM/Kluwer Mobile Networks and Appli- cations (MONET), vol. 10, pp. 875{878, Dec. 2005. [76] J. C. Dagher, M. W. Marcellin, and M. A. Neifeld, \A theory for maximizing the lifetime of sensor networks," IEEE Trans. on Communications, vol. 55, pp. 323{332, Feb. 2007. [77] E. I. Oyman and C. Ersoy, \Multiple sink network design problem in large scale wireless sensor networks," in Proc. of IEEE ICC, Paris, France, June 2004. 170 Bibliography [78] P. Thulasiraman, S. Ramasubramanian, and M. Krunz, \Disjoint multipath routing to two distinct drains in a multi-drain sensor network," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. [79] H. Kim, Y. Seok, N. Choi, Y. Choi, and T. Kwon, \Optimal multi-sink positioning and energy ecient routing in wireless sensor networks," Information Networking, Lecture Notes in Computer Science, vol. 3391, Springer, pp. 264{274, Dec. 2005. [80] F. Lin and Y. Wen, \Multi-sink data aggregation routing and scheduling with dy- namic radii in WSNs," IEEE Communications Letters, vol. 10, pp. 692{ 694, Oct. 2006. [81] K. Yuen, B. Li, and B. Liang, \Distributed data gathering in multi-sink sensor net- works with correlated sources," in Proc. of IFIP Networking, Coimbra, Portugal, May 2006. [82] S. Sarkar and L. Tassiulas, \Fair bandwidth allocation of multicasting in networks with discrete feasible set," IEEE Trans. on Computers, vol. 53, pp. 785{797, July 2004. [83] \ILOG CPLEX." http://www.ilog.com/products/cplex/. [84] \MOSEK." http://www.mosek.com. [85] A. H. Land and A. G. Doig, \An automatic method for solving discrete programming problems," Econometrica, vol. 28, pp. 497{520, 1960. [86] H. Taha, Operations Research: An Introduction, 7th ed. Prentice Hall, 2003. [87] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004. [88] L. Chen, S. H. Low, M. Chiang, and J. C. Doyle, \Optimal cross-layer congestion control, routing and scheduling design in ad hoc wireless networks," in Proc. of IEEE INFOCOM, Barcelona, Spain, April 2006. [89] J. Mo and J. Walrand, \Fair end-to-end window-based congestion control," IEEE/ACM Trans. on Networking, vol. 8, pp. 556{567, Oct. 2000. [90] M. Kim, M. Medard, V. Aggrawal, U. O'Reilly, W. Kim, C. Wook, and M. Eros, \Evolutionary approaches to minimize network coding resources," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. [91] L. Chen, T. Ho, S. H. Low, M. Chiang, and J. C. Doyle, \Optimization based rate control for multi-cast with network coding," in Proc. of IEEE INFOCOM, Anchorage, AK, May 2007. 171 Bibliography [92] T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Eros, J. Shi, and B. Leong, \A random linear network coding approach to multicast," IEEE Trans. on Information Theory, vol. 52, pp. 4413{4430, Oct. 2006. [93] C. Fragouli and E. Soljanian, \Information ow decomposition for network coding," IEEE Trans. on Information Theory, vol. 52, pp. 829{848, Mar. 2006. [94] J. E. Wieselthier, G. D. Nguyen, and A. Ephremides, \Energy-ecient broadcast and multicast trees in wireless networks," Mobile Network and Applications, vol. 7, pp. 481{492, Dec. 2002. [95] A. K. Das, M. El-Sharkawi, R. Marks, P. Arabshahi, and A. Gray, \Maximization of time-to-rst failure for multicasting in wireless networks: Optimal solution," in Proc. of Military Communications Conference, Monterey, CA, Oct. 2004. [96] M. Kim, C. W. Ahn, M. Medard, and M. Eros, \On minimizng network coding resources: An evolutionary approach," in Proc. of the Second Workshop on Network Coding, Theory, and Applications (NetCod), Riva del Garda, Italy, Apr. 2006. [97] K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu, \Impact of interference on multi-hop wireless network performance," in Proc. of ACM MobiCom, San Diego, CA, Sept. 2003. [98] Y. T. Hou, Y. Shi, and H. D. Sherali, \Rate allocation and network lifetime problems for wireless sensor networks," IEEE/ACM Trans. on Networking, vol. 16, pp. 321{ 334, Apr. 2008. [99] P. A. Chou, Y. Wu, and K. Jain, \Practical network coding," in Proc. of Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct. 2003. [100] M. Ghaderi, D. Towsley, and J. Kurose, \Reliability gain of network coding in lossy wireless networks," in Proc. of IEEE INFOCOM, Phoenix, AZ, Apr. 2008. [101] A. Eryilmaz, A. Ozdaglar, and M. Medard, \On delay performance gains from net- work coding," in Proc. of Conference on Information Sciences and Systems, Prince- ton, NJ, Mar. 2006. [102] T. K. Dikaliotis, A. G. Dimakis, T. Ho, and M. Eros, \On the delay of network coding over line networks," in Proc. of IEEE Int'l Symposium on Information Theory (ISIT), Seoul, Korea, June 2009. [103] D. Lucai, M. Stojanovic, and M. Medard, \Random linear network coding for time division duplexing: When to stop talking and start listening," in Proc. of IEEE INFOCOM, Rio de Janeiro, Brazil, Apr. 2009. 172 Bibliography [104] ||, \Random linear network coding for time-division duplexing: Field size consid- erations," in Proc. of IEEE Globecom, Honolulu, HI, Nov. 2009. [105] ||, \Sharing information in time-division duplexing channels: A network coding approach," in Proc. of 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct. 2009. [106] S. Chachulski, M. Jennings, S. Katti, and D. Katabi, \Trading structure for random- ness in wireless opportunistic routing," in Proc. of ACM SIGCOMM, Kyoto, Japan, Aug. 2007. [107] T. Cui, L. Chen, and T. Ho, \Energy ecient opportunistic network coding for wireless networks," in Proc. of IEEE INFOCOM, Phoenix, AZ, Mar. 2008. [108] E. Kehdi and B. Li, \Incorporating random linear network coding for peer-to-peer network diagnosis," in Proc. of IEEE INFOCOM, San Diego, CA, Mar. 2010. [109] I.-H. Hou, Y.-E. Tsai, T. Abdelzaher, and I. Gupta, \Adapcode: Adaptive network coding for code updates in wireless sensor networks," in Proc. of IEEE INFOCOM, Phoenix, AZ, Apr. 2008. [110] C. Fragouli, D. Lun, M. Medard, and P. Pakzad, \On feedback for network coding," in Proc. of Annual Conference on Information Sciences and Systems, Baltimore, MD, Mar. 2007. [111] J. K. Sundararajan, D. Shah, and M. Medard, \ARQ for network coding," in Proc. of IEEE Int'l Symposium on Information Theory (ISIT), Toronto, CA, July 2008. [112] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, \XORs in the air: Practical wireless network coding," in Proc. of ACM SIGCOMM, Pisa, Italy, Aug. 2006. [113] J. Le, J. Lui, and D. M. Chiu, \How many packets can we encode? An analysis of practical wireless network coding," in Proc. of IEEE INFOCOM, Phoenix, AZ, Apr. 2008. [114] F. Zhao and M. Medard, \On analyzing and improving COPE performance," in Proc. of International Conference on Information Theory and Application, San Diego, CA, Feb. 2010. [115] H. Seferoglu, A. Markopoulou, and K. K. Ramakrishnan, \I2NC: Intra- and inter- session network coding for unicast ows in wireless networks," in Proc. of IEEE INFOCOM, Shanghai, China, Apr. 2011. [116] L. Keller, E. Atsan, K. Argyraki, and C. Fragouli, \Sensecode: Network coding for reliable sensor networks," in EPFL Technical Report, 2009. 173 Bibliography [117] Y. Mao, F. R. Kschischang, B. Li, and S. Pasupathy, \A factor graph approach to link loss monitoring in wireless sensor networks," IEEE J. on Selected Areas in Commun., vol. 23, no. 4, pp. 820{829, Apr. 2005. [118] C. Fragouli, J.-Y. Le Boudec, and J. Widmer, \Network coding: An instant primer," ACM SIGCOMM Computer Communication Review, vol. 36, no. 1, pp. 63{68, Jan. 2006. [119] G. Hartl and B. Li, \Loss inference in wireless sensor networks based on data ag- gregation," in Proc. of Int'l Conf. on Information Processing in Sensor Networks (IPSN), Berkeley, CA, Apr. 2004. [120] H. X. Nguyen and P. Thiran, \Using end-to-end data to infer lossy links in sensor networks," in Proc. of IEEE INFOCOM, Barcelona, Spain, Apr. 2006. [121] J. Gui, V. Shah-Mansouri, and V. W. S. Wong, \An algebraic approach to loss tomography on mesh topologies," in Proc. of IEEE ICC, Cape Town, South Africa, May 2010. [122] M. Gjoka, C. Fragouli, P. Sattari, and A. Markopoulou, \Loss tomography in general topologies with network coding," in Proc. of IEEE Globecom, Washington, DC, Nov. 2007. [123] C. Fragouli, A. Markopoulou, R. Srinivasan, and S. Diggavi, \Network monitoring: It depends on your points of view," in Proc. of Information Theory and Applications (ITA) Workshop, San Diego, CA, Jan. 2007. [124] C. Fragouli, A. Markopoulou, and S. Diggavi, \Topology inference using network cod- ing," in Proc. of 44th Annual Allerton Conf. on Commun., Control, and Computing, Monticello, IL, Oct. 2006. [125] G. Sharma, S. Jaggi, and B. Dey, \Network tomography via network coding," in Proc. of Information Theory and Applications (ITA), San Diego, CA, Jan. 2008. [126] Y. Lin, B. Liang, and B. Li, \Passive loss inference in wireless sensor networks based on network coding," in Proc. of IEEE INFOCOM, Rio de Janeiro, Brazil, Apr. 2009. [127] T. Ho and H. Viswanathan, \Dynamic algorithms for multicast with intra-session network coding," in Proc. of Allerton Conference on Communication, Control, and Computing, Monticello, IL, Oct. 2005. [128] T. Ho, R. Koetter, M. Medard, D. R. Karger, and M. Eros, \The benets of cod- ing over routing in a randomized setting," in Proc. of IEEE Int'l Symposium on Information Theory, Yokohama, Japan, July 2003. [129] I. Blake, An Introduction to Applied Probability. John Wiley and Sons, 1987. 174 Bibliography [130] N. Johnson and S. Kotz, Urn Models and Their Applications. John Wiley and Sons, 1977. [131] A. H. Mohsenian-Rad, V. Shah-Mansouri, V. W. S. Wong, and R. Schober, \Dis- tributed channel selection and randomized interrogation algorithms for RFID sys- tems," IEEE Trans. on Wireless Communications, vol. 9, pp. 1402 { 1413, Apr. 2010. [132] J. Waldrop, D. W. Engels, and S. E. Sarma, \Colorwave: An anticollision algorithm for the reader collision problem," in Proc. of IEEE ICC, Anchorage, AK, May 2003. [133] Z. Zhou, H. Gupta, S. R. Das, and X. Zhu, \Slotted scheduled tag access in multi- reader RFID systems," in Proc. of IEEE Int'l Conf. on Networks Protocols (ICNP), Beijing, China, Sept. 2007. [134] J. Ho, D. W. Engels, and S. E. Sarma, \HiQ: A hierarchical Q-learning algorithm to solve the reader collision problem," in Proc. Int'l Symp. on Applications and Internet Workshops, Phoenix, AZ, Jan. 2006. [135] Y. Tanaka and I. Sasase, \Interference avoidance algorithms for passive RFID systems using contention-based transmit abortion," IEICE Trans. on Commun., vol. E90-B, pp. 3170{3180, Nov. 2007. [136] K. Whang, B. Vander-Zanden, and H. Taylor, \A linear time probabilistic counting algorithm for database applications," ACM Trans. on Database Systems, vol. 15, pp. 208{229, June 1990. [137] S. M. Kay, Fundamentals of Statistical Signal Processing, Volume I: Estimation The- ory. Prentice Hall, 1993. [138] D. Marx, \Graph colouring problems and their applications in scheduling," Periodica Polytechnica Series, Electrical Engineering, vol. 48, no. 1, pp. 11{16, Jan. 2004. [139] W. Feller, An Introduction to Probability Theory and Its Application. John Wiley and Sons, 1968. 175
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Energy-efficient algorithm design for wireless sensor...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Energy-efficient algorithm design for wireless sensor networks Shah-Mansouri, Vahid 2011
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Energy-efficient algorithm design for wireless sensor networks |
Creator |
Shah-Mansouri, Vahid |
Publisher | University of British Columbia |
Date Issued | 2011 |
Description | Wireless sensor networks (WSNs) are composed of inexpensive sensor devices called sensor nodes. Sensors have limited power supply, computational capabilities, and memory. Different types of sensors can measure either temperature, light, sound, or pressure from the environment. Because the sensors have short transmission range, the generated data are gathered via multihop transmissions at a central processor called a sink. In this thesis, we propose several power efficient algorithms for WSNs. First, we formulate the lexicographically optimal commodity lifetime routing problem. We propose the lexicographically optimal node lifetime algorithm, which is suitable for practical implementation. Simulation results show that our proposed algorithm can increase the network lifetime compared to other schemes in the literature. Second, we study the problem of supporting multicast traffic in WSNs with network coding. We formulate the maximum-lifetime minimum-resource coding subgraph problem to study the lifetime-resource tradeoff. Results show that the network lifetime can be substantially increased using our algorithm. Next, we consider the problem of designing feedback mechanisms for WSNs using random linear network coding (RLNC). For an intermediate node, we determine the time at which the node can stop transmission of a particular flow. We propose novel link-by-link and end-to-end feedback mechanisms for RLNC with buffer sharing. Simulation results show that link-by-link feedback is more power-efficient compared to end-to-end feedback. Then, we study the passive loss inference problem in WSNs using RLNC. By inspecting the contents of packets at the sink, the sink can estimate the path loss rates from the sources and intermediate nodes. We propose a passive loss inference with RLNC algorithm. Simulation results show that our algorithm can identify the status of a higher number of links compared to a Bayesian inference algorithm. Finally, we study the problem of cardinality estimation in radio frequency identification systems with several readers. We introduce exclusive estimators to estimate the number of tags located exclusively in the zone of a reader. Then, we propose cardinality estimation algorithms. Our simulation results show that the variance of our proposed estimation algorithms increases linearly with the number of readers while it increases exponentially for existing algorithms. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-08-24 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0072095 |
URI | http://hdl.handle.net/2429/36870 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2011-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2011_fall_shah-mansouri_vahid.pdf [ 1.11MB ]
- Metadata
- JSON: 24-1.0072095.json
- JSON-LD: 24-1.0072095-ld.json
- RDF/XML (Pretty): 24-1.0072095-rdf.xml
- RDF/JSON: 24-1.0072095-rdf.json
- Turtle: 24-1.0072095-turtle.txt
- N-Triples: 24-1.0072095-rdf-ntriples.txt
- Original Record: 24-1.0072095-source.json
- Full Text
- 24-1.0072095-fulltext.txt
- Citation
- 24-1.0072095.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0072095/manifest