1:114. .. v 2.3...“ 1L ‘1 8... . . 1 ... n. I. . Eyes! I. it. zwfiohfiycflhn... ... .61} .153...“ I‘ll _ .fiu. :.,.f.).~. LII .u. 3.1. , LIBRARY 3 Michigan State Ul liVBfSity U0) H This is to certify that the dissertation entitled NETWORK—INTEGRATED SENSING AND ENERGY-AWARE PROTOCOLS IN WIRELESS BODY AREA NETWORKS presented by Muhannad Quwaider has been accepted towards fulfillment of the requirements for the Doctoral degree in Electrical Engineering 9.211% ax. WW Major Professor’s Si nature 05/06 20/0 Date MSU is an Affirmative Action/Equal Opportunity Employer A q.--.-I“-'-.-.-.-.-.---.-.-' PLACE IN RETURN BOX to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE 5/08 KzlProleocaPresIClRClDateDueJndd NETWORK-INTEGRATED SENSING AND ENERGY-AWARE PROTOCOLS IN WIRELESS BODY AREA NETWORKS by Muhannad Quwaider A DISSERTATION Submitted to Michigan State University In partial fulfillment of the requirements For the degree of DOCTOR OF PHILOSOPHY Electrical Engineering 2010 - ABSTRACT NETWORK-INTEGRATED SENSING AND ENERGY-AWARE PROTOCOLS IN WIRELESS BODY AREA NETWORKS By Muhannad Quwaider The objective of this thesis is to develop an end-to-end framework for network integrated sensing and energy-aware protocols for supporting applications in resource-constrained Wireless Body Area Networks (W BAN). A large number of existing WBAN applications involving physical activity monitoring and body posture detection use multi-axis accelerometry as the primary sensing modality. While the accelerometer-based approaches work well for identifying high-activity postures such as walking and running, they do not work well when it is necessary to differentiate between low-activity postures such as standing, sitting, lying down, and sometimes with finer granularity such as sitting upright or reclining. The key contribution of the first part of this thesis is to develop a novel network-integrated sensing modality, inter-sensor relative proximity, which is inferred from the measured Received Signal Strength Indicator (RSSI) of the Radio Frequency (RF) signal between each pair of WBAN sensors. The concept of RSSI-based proximity is experimentally developed and then integrated within a Hidden Markov Model (HMM)-based stochastic processing framework for accurately identifying human body postures in a subj ect-independent manner. In the second part of the thesis, the issue of energy-aware on-body communication is addressed by developing a human body posture-aware transmission power control framework. A closed loop link power assignment framework has been developed in which the RF power on an on-body network link is dynamically adjusted depending on the instantaneous postural orientation of a subject individual. It was demonstrated that such posture-aware mechanisms can outperform the traditional power control algorithms by leveraging on-body RF attenuation information which heavily depends on postural configurations. In the third part of this thesis, an on-body Delay Tolerant Network (DTN) routing framework has been developed. Ultra-short transmission range is a common constraint for low-power RF transceivers used for embedded applications with limited energy and small form-factors. For such ultra-short transmission range, postural body movements can make the WBANs to be highly prone to topological partitioning, resulting in a body area Delay Tolerant Network (DTN). Such topological partitioning can often get aggravated by the unpredictable on-body RF attenuation. The objective of this part of the thesis was to develop on-body store-and—forward packet routing algorithms, along with an analytical framework for modeling routing delay in the presence of network partitioning. The goal is to minimize end-to-end packet delay while minimizing the end-to-end hop-count, so that the transmission energy drainage is minimized. Ckmynghtby Muhannad Quwaider 2010 To My Family ForAll Their Love and Support Acknowledgements I owe my deepest gratitude to my advisor Dr. Subir Biswas for guiding and supporting me throughout the course of my doctoral study. His ideas, expertise and sound advice have been a major influence on this thesis. I have learned a great deal under his able mentorship during this research work. I would also like to thank the other members of my committee namely Dr. Michael Shanblatt, Dr. Erik Goodman and Dr. Guoliang Xing for their helpful suggestions, support and advice. I am greatly indebted to the ECE department and the graduate school for their support and encouragement in my endeavor. Also, this research study required long and extensive experiments and simulations and would not have been possible without the availability of the resources in the NeEWs laboratory and HPCC. Very special thanks go to my colleagues and fi'iends in the NeEWS laboratory — Jayanthi Rao, Anthony Plummer, Mahmoud Taghizade, Tao Wu, Fan Yu, Debasmit Banerjee, Ali Aqel and Qiong Huo with whom I have worked closely during the last few years and enjoyed sharing research ideas and accomplishments. Lastly, and most importantly, I thank my mother, my father, my brothers, my wife, Abeer, and my kids, Bishr, Taqwa and Abdullah, for their understanding, motivation and support throughout this research work. TABLE OF CONTENTS LIST OF TABLES XI LIST OF FIGURES XII LIST OF ABBREVIATIONS XVII CHAPTER 1. BACKGROUND AND THESIS CONTRIBUTION 1 1.1 WIRELESS BODY AREA NETWORKS WBANS ......................................................... I 1.2 APPLICATIONS OF BODY Area NETWORKS .............................................................. 1 1.2.1 Healthcare Applications ................................................................................. 2 1.2.2 Activity Monitoring Applications .................................................................... 4 1.2.3 Military Applications ...................................................................................... 4 1.3 CHALLENGES, ISSUES AND THESIS CONTRIBUTION ................................................. 6 1.3.1 Limited Sensing Modalities ............................................................................ 7 1.3.1.1 Proposed Inter-sensor Relative Proximity .................................................. 7 1.3.2 Energy Management ....................................................................................... 8 1.3.2.1 Transmission Power Control ....................................................................... 8 1.3.2.2 Data Routing with Ultra-low Radio Transmission Range ........................ 10 CHAPTER 2. WBAN LABORATORY PROTOTYPE SYSTEM 12 2.1 WEARABLE SENSOR NODES ................................................................................. 12 2.2 SENSOR NODE HARDWARE ................................................................................... 14 2.3 MICA2DOT RADIO ............................................................................................. 15 2.4 SOFTWARE PLATFORM .......................................................................................... 16 2.5 TRANSMISSION POWER ASSIGNMENT ................................................................... 17 2.6 PROTOTYPE SYSTEM COMPONENTS ...................................................................... 18 CHAPTER 3. NETWORK-INTEGRATED PROXIMITY SENSING FOR PHYSICAL POSTURE DETECTION 19 3.1 INTRODUCTION AND RELATED WORK ................................................................... 19 3.2 UNI-MODAL ACCELEROMETRY ............................................................................. 19 3.3 INTER-SENSOR RELATIVE PROXIMITY ................................................................... 22 3 .4 TARGET SENSOR MODALITIES .............................................................................. 23 3 .5 COMPUTATION MODES .......................................................................................... 24 3 .6 SENSOR PLACEMENT AND MODALITY USAGE ....................................................... 25 3.7 POSTURE MODELING AND GENERATION ............................................................... 26 3 .8 THRESHOLD BASED IDENTIFICATION ..................................................................... 29 3 .9 CAPTURING STATIONARY BEHAVIOR USING HIDDEN MARKOV MODEL ................ 35 3.9.1 HMM Mapping ............................................................................................. 35 3. 9.2 Posture Detection using HMM ..................................................................... 40 3.10 EXPERIMENTAL RESULTS ...................................................................................... 41 3.10.1 Manual Calibration ...................................................................................... 41 vii 3.10.2 Automatic Observation Calibration ............................................................. 44 3.11 SUMMARY CONCLUSIONS ..................................................................................... 46 3.12 APPENDIX: ITERATIVE HMM WITH AUTOMATIC OBSERVATION CALIBRATION ...... 47 CHAPTER 4. TRANSMISSION POWER ASSIGNMENT WITH POSTURAL POSITION INFERENCE 50 4.1 RELATED WORK ................................................................................................... 50 4.2 DYNAMIC TRANSMISSION POWER ASSIGNMENTS ................................................. 53 4.3 CHARACTERIZATION OF ON-BODY RF LINKS ....................................................... 53 4.3. 1 Experimental Settings ................................................................................... 53 4.3.2 Target link and Posture Sequence ................................................................. 54 4.3.3 Transmission Power Levels .......................................................................... 55 4.3.4 Multi-scale Variations of Link Quality ......................................................... 56 4.3.5 Impacts of On-body Parameters on Link Quality ......................................... 60 4.3.6 Validating Linearity of RSSI for Other Pastures ................................. ' ......... 62 4.4 FIXED POWER ASSIGNMENTS ................................................................................ 63 4.4.1 Relevant Performance Metrics ..................................................................... 63 4.4.2 Fixed Power Assignment Results .................................................................. 64 4.5 DYNAMIC ON-BODY POWER ASSIGNMENTS ......................................................... 67 4.5.1 Closed Loop Control ..................................................................................... 67 4.5.2 Choice of RSSI Thresholds ........................................................................... 69 4.5.3 Target Power Computation by Linear Search .............................................. 70 4.5.4 Computation by Binary Search ..................................................................... 71 4.5.5 Control with Dynamic Postural Position Inference ...................................... 72 4.6 EXPERIMENTAL PERFORMANCE ............................................................................ 75 4.6.1 Medium Access Control ................................................................................ 75 4.6.2 Results and Interpretation ................................... _ ......................................... 7 7 4.6.2.1 Transmit Power and RSSI Dynamics ........................................................ 79 4.6.2.2 Packet Delivery Ratio (PDR) .................................................................... 80 4.6.2.3 Energy Per Packet (EPP) ........................................................................... 82 4.6.2.4 Energy Overhead of Closed Loop Control ................................................ 83 4.6.2.5 Results for Different Subject Individuals .................................................. 84 4.6.2.6 Impacts of RSSI Thresholds ...................................................................... 86 4.6.2.7 Results for Different Postures ................................................................... 86 4.7 SUMMARYAND CONCLUSIONS .............................................................................. 91 CHAPTER 5. POSTURE-PREDICTIVE POWER CONTROL USING LINEAR-QUADRATIC GAUSSIAN CONTROL 93 5.1 LQGI FRAMEWORK .............................................................................................. 94 5.1.1 Problem Formulation ................................................................................... 94 5.1.2 Quantized LQGI ........................................................................................... 97 5.2 PERFORMANCE RESULTS ....................................................................................... 98 5.3 RELEVANT PERFORMANCE METRICS .................................................................... 99 5.4 RESULTS AND INTERPRETATION .......................................................................... 100 5. 4. I Transmit Power and RSSI Dynamics .......................................................... 100 5.4.2 RSSI Target Error (RTE) ............................................................................. 103 viii 5.4.3 Energy Per Packet (EPP) ............................................. I ............................. 104 5.4.4 Energy Overhead of Closed-Loop Control ................................................. 105 5.5 SUMMARY AND CONCLUSIONS ............................................................................ 1 06 CHAPTER 6. DTN ROUTING IN BODY SENSOR NETWORKS WITH DYNAMIC POSTURAL PARTITIONING 108 6.1 INTRODUCTION ................................................................................................... 108 6.1.1 Short RF Transmission Range .................................................................... 108 6.1.2 Routing with Network Partitioning ............................................................. 109 6.1.3 Objective and Contributions ....................................................................... 109 6.2 RELATED WORK ................................................................................................. 110 6.3 CHARACTERIZATION OF ON-BODY NETWORK TOPOLOGY .................................. 1 14 6.3.1 Experimental Settings ................................................................................. 114 6.3.2 Variations of Topology and Network Partitions ......................................... 115 6.4 STORE-AND-FORWARD ROUTING WITH MULTI-SCALE MOVEMENT LOCALITY 119 6. 4. 1 Postural Link Cost with Multi-Scale Locality ............................................ 119 6.4.2 Probabilistic Routing with Postural Link Costs (PRPLC) ......................... 124 6.4.3 Single-Copy Probabilistic Routing (PROPHET) ........................................ 128 6.4.4 Distance Vector Routing with Postural Link Costs (D VRPLC) .................. 129 6.4.5 On-body Store and Flood Routing (OBSFR) .............................................. 132 6.5 EXPERIMENTAL PERFORMANCE .......................................................................... 136 6.5.1 Polling Based Channel Access for Collision Control ................................. 136 6.5.2 Performance Metrics .................................................................................. 1 3 8 6.5.3 T raflic Generation and Data Collection ..................................................... 138 6. 5. 4 Packet Delay (PD) ...................................................................................... 1 3 9 6.5.5 Packet Hop Count (PHC) ........................................................................... 142 6.5. 6 Packet Delivery Ratio ................................................................................. 143 6. 5. 7 Routing Packets from and to Dilfkrent Body Segments .............................. 145 6. 5. 8 Impacts of Postural Stability ...................................................................... I 4 6 6. 5. 9 Impacts of Intra-posture Movements .......................................................... I48 6.5.10 Impacts of Sensor Placements .................................................................... 149 6.6 OFFLINE SIMULATION WITH EXPERIMENTALLY OBTAINED TOPOLOGY ............... 150 6. 6. 1 Delay Benchmark ....................................................................................... 151 6.6.2 Simulated Performance Results .................................................................. 153 6.7 PRPLC WITHOUT 2-HOP ASSUMPTION ............................................................... 158 6. 7.1 Transitive Update of Link Likelihood Factor ............................................. 158 6. 7.2 Performance with Transitive LLF Update .................................................. 159 6.8 SUMMARY AND CONCLUSIONS ............................................................................ 160 CHAPTER 7. MODELING ON-BODY DTN PACKET ROUTING DELAY ...... 162 7.1 INTRODUCTION ................................................................................................... 162 7.2 TOPOLOGY TRACE COLLECTION FOR OFF-BODY ROUTING SIMULATION ............ 164 7.3 MODELING DTN ROUTING PROTOCOLS ............................................................. 165 7. 3. 1 Opportunistic Routing ................................................................................ I 66 7.3.2 Randomized Routing ................................................................................... 168 7.3.3 Utility-based Routing using Link Locality .................................................. 1 73 ix 7.3.4 Probabilistic Routing with Postural Link Cost (PRPLC) ........................... 1 76 7.3.5 Distance Vector Routing with Postural Link Costs (D VRPLC) .................. 182 7.4 ROUTING DELAY BENCHMARK ........................................................................... 185 7.5 PERFORMANCE EVALUATION .............................................................................. 187 7.5.1 Performance Metrics .................................................................................. 188 7.5.2 T rafi'ic Generation and Data Collection ..................................................... 188 7. 5. 3 Packet Delay (PD) ...................................................................................... 189 7.5.4 Packet Hop Count (PH C) ........................................................................... 190 7.5.5 Packet Delivery Ratio ................................................................................. 191 7. 5. 6 Routing Packets from and to Dzflerent Body Segments .............................. I93 7. 5. 7 Impacts of Postural Stability ...................................................................... 194 7. 5. 8 Impacts of Sensor Placements .................................................................... 196 7.6 EVALUATION OF NODE CRITTCALTTY ................................................................... 197 7.7 SUMMARY AND CONCLUSIONS ............................................................................ 201 CHAPTER 8. SUMMARY AND FUTURE WORK 202 8.1 CONTRIBUTIONS ................................................................................................. 202 8.2 FUTURE WORK ................................................................................................... 205 REFERENCES 207 List of Tables Table 2.1: Chipcon CClOOO Output Power Settings and Typical Current [75] ................ 15 Table 3.1: Computation Mode and Their Applications ..................................................... 24 Table 3.2: On-Body Sensor Modality and Placement Summary ....................................... 25 Table 3.3: Threshold group values for context identification ........................................... 29 Table 3.4: Observation sub-vectors and Window boundaries for different observation granularities ....................................................................................................................... 42 Table 4.1: Performance summary of different power assignments ................................... 79 Table 4.2: Power assignment performance for multiple subjects ...................................... 85 Table 4.3: Indoor and outdoor performance summary of different power assignments 89 Table 6.1: Low power and short range RF transceivers .................................................. 109 xi Figure 1.1: Figure 1.2: Figure 1.3: Figure 2.1: Figure 2.2: Figure 2.3: Figure 2.4: Figure 3.1: Figure 3.2: Figure 3.3: Figure 3.4: Figure 3.5: Figure 3.6: Figure 3.7: Figure 3.8: Figure 3.9: Figure 4.1: Figure 4.2: Figure 4.3: Figure 4.4: Figure 4.5: Figure 4.6: List of Figures Body Area Networks Applications ................................................................... 2 Body Area Sensor Network .............................................................................. 3 Pictorial summary of the investigated issues in this thesis ............................... 6 Wearable sensor network and health monitoring prototype ........................... 12 MICA2DOT sensor node [78] ........................................................................ 13 MICA2DOT mote specifications [78] ............................................................ 14 WBAN System Architecture ........................................................................... 17 Accelerometer data during a controlled posture sequence .............................. 20 Frequency domain view of the acceleration reading ...................................... 21 Posture state transition machine ...................................................................... 27 Posture identification using multi-modal thresholds ...................................... 28 Sensor outputs and actual postures ................................................................. 30 Detection accuracy for multiple human subjects ............................................ 33 Posture identification performance ................................................................. 43 Automatic self-calibration of the B matrix ..................................................... 45 Performance of Baum-Welch iterative algorithm ........................................... 48 On-body sensor positions and the used posture sequence .............................. 55 Link quality variations with varying postural positions .................................. 57 Impacts of transmission power at different postures ...................................... 58 Impacts of transmission power on packet loss ................................................ 59 Variation of sensor orientations and on-body obstructions ............................ 6O Impacts of sensor orientation and on-body obstructions ................................ 61 xii Figure 4.7: Orientations of a lower-body link with different postures .............................. 62 Figure 4.8: RSSI characteristics power for a lower-body link .......................................... 62 Figure 4.9: PDR performance with fixed power assignment ............................................ 65 Figure 4.10: EPP performance with fixed power assignment ........................................... 66 Figure 4.11: Closed loop power assignment model .......................................................... 67 Figure 4.12: RSSI threshold range for acceptable packet delivery rate ............................ 69 Figure 4.13: Posture-driven DPPI for dynamic power assignments ................................. 72 Figure 4.14: Multiple control schemes with synchronized postures ................................. 76 Figure 4.15: Power level and RSSI dynamics with posture changes ................................ 77 Figure 4.16: PDRs for DPPI and binary search assignments 81 Figure 4.17: Packet drops during posture transitions ........................................................ 82 Figure 4.18: EPP for DPPI and binary search assignments ............................................... 83 Figure 4.19: Cumulative control energy expenditure over time ........................................ 84 Figure 4.20: Energy expenditure with varying RSSI thresholds ....................................... 85 Figure 4.21: Power levels and RSSI dynamics with posture changes, for different power assignment strategies ......................................................................................................... 87 Figure 4.22: PDR for DPPI and binary search assignments .............................................. 90 Figure 4.23: EPP for DPPI and binary search assignments ............................................... 91 Figure 5 .1: Block diagram of the augmented system ........................................................ 94 Figure 5.2: Block diagram of quantized LQGI Control .................................................... 98 Figure 5.3: On-body sensor positions and the used posture sequence .............................. 99 Figure 5.4: Power level and RSSI dynamics with posture changes ................................ 101 Figure 5.5: RSSI average error and standard deviation ................................................... 103 Figure 5.6: Average EPP for different dynamic search assignments .............................. 105 xiii Figure 5.7: Cumulative control energy expenditure ........................................................ 106 Figure 6.1: On-body Mounted Sensors ............................................................................ 114 Figure 6.2: Variation of link connectivity with postural mobility ................................... 116 Figure 6.3: Topology and partition properties with posture changes .............................. 117 Figure 6.4: Distributed of number of neighbors .............................................................. 1 18 Figure 6.5: Evolution of multi-scale locality in terms of LLF and HCQ ........................ 123 Figure 6.6: PRPLC routing with LLF capturing multi-scale connection localities ......... 127 Figure 6.7: DVRPLC routing with link cost capturing multi-scale connection localilti3els Figure 6.8: OBSFR routing logic for packet delay lower bound ..................................... 134 Figure 6.9: Collision-free MAC access Via polling ......................................................... 137 Figure 6.10: Packet delivery delays with static and adaptivew scenarios ....................... 140 Figure 6.1 1: On-body packet delivery delay for different DTN routing protocols ......... 141 Figure 6.12: Distribution of Packet Hop Count (PHC) ................................................... 142 Figure 6.13: Number of transmissions per delivered packet ........................................... 143 Figure 6.14: Packet delivery performance ....................................................................... 144 Figure 6.15: Delivery delay for packets from thigh, waist and arm to right ankle (i.e. node 6) ...................................................................................................................................... 145 Figure 6.16: Delivery delay for packets to arm, thigh and ankle from the upper left arm (i.e. node 3 in Figure 6.1) ........................................................................................................ 146 Figure 6.17: Impacts of posture duration on packet delay .............................................. 146 Figure 6.18: Impacts of posture duration on packet delivery ratio .................................. 147 Figure 6.19: Packet delivery delay with intra-posture movement ................................... 148 Figure 6.20: Experiments with different sensor placements ........................................... 149 xiv Figure 6.21: On-body packet delay for: (a) sensor placement P1, and (b) sensor placement P2 ..................................................................................................................................... 150 Figure 6.22: Experimental topology export for offline simulation ................................. 151 Figure 6.23: Delivery delay from experiments and simulation ....................................... 154 Figure 6.24: Packet hop counts from experiment and simulation ................................... 155 Figure 6.25: Simulated average packet delivery delay .................................................... 156 Figure 6.26: Simulated average of Packet Hop Count .................................................... 157 Figure 6.27: The impacts of transitive updates on delivery delay ................................... 159 Figure 6.28: The impacts of transitive updates on Packet Hop Counts (PHC) ............... 160 Figure 7 .1: On-body Mounted Sensor ............................................................................. 163 Figure 7.2: Topology export for offline and model performance .................................... 164 Figure 7.3: Example connectivity of an on—body link ..................................................... 165 Figure 7.4: Evolution of multi-scale locality in terms of PLC and HCQ ....... . ................. 179 Figure 7.5: Capturing link connectivity locality in PRPLC and UTILITY age-based routing .............................................................................................................................. 181 Figure 7.6: On-body packet delivery delay for different DTN routing protocols ........... 189 Figure 7.7: Average Packet Hop Count ........................................................................... 191 Figure 7.8: Packet drops observed for different protocols .............................................. 192 Figure 7.9: Delivery delay for packets from thigh, waist and arm to right ankle ............ 193 Figure 7.10: Delivery delay for packets to arm, thigh and ankle from the upper lefi arm (i.e. node 3 in Figure 7.1) ........................................................................................................ 194 Figure 7.11: Impacts of posture duration on packet delay .............................................. 194 Figure 7.12: Experiments with different sensor placements ........................................... 195 Figure 7.13: On-body packet delay for: (a) sensor placement P1, and (b) sensor placement P2. .................................................................................................................................... 196 XV Figure 7.14: Node criticality in terms of: (a) Packet delay, and (b) Packet delay difference ......................................................................................................................................... 198 Figure 7.15: Two node criticality in terms of: (a) Packet delay, and (b) Packet delay difference ......................................................................................................................... 200 xvi WBAN RSSI DPPI DTN FSK FT HMM TPC TDOA CDMA PDR EPP LQGI LQGIQ RTE ST WASP PLCF LLF HCQ List of Abbreviations Wireless Body Area Networks Received Signal Strength Indicator Radio Frequency Dynamic Postural Position Inference Delay Tolerant Network Frequency Shift Keying Fourier Transform Hidden Markov Model Window Boundary Transmission Power Control Time Delay Of Arrival Code-Division Multiple-Access Packet Delivery Ratio Energy Per Packet Linear Quadratic Gaussian control with an Integrator Quantized Linear Quadratic Gaussian control with an Integrator Target Error Standard Deviation Autonomous Spanning tree Protocol Postural Link Cost Formulation Link Likelihood Factor Historical Connectivity Quality xvii PROPHET PRPLC DVRPLC LCF OBSFR BSDBR ER PD PHC UTILITY OPPT RAND DD SIT STD Probabilistic Routing Protocol using History of Encounters and Transitivity Probabilistic Routing with Postural Link Costs Distance Vector Routing with Postural Link Costs Link Cost Factor On-body Store and Flood Routing Backward Search for Delay Benchmark Routing Epidemic Routing Packet Delay Packet Hop Count Utility-age based protocol Opportunistic protocol Randomized protocol Directed Diffusion Sit straight Stand Sit Reclining Lying Down Walk Run xviii Chapter 1. Background and Thesis Contribution 1.1 Wireless Body Area Networks WBANS Wireless Body Area Networks (WBAN) consists of a set of intercommunicating sensors, either wearable or implanted, which can monitor vital body movement parameters and collect different body information [1-5]. These devices, communicating through wireless technologies, can transmit data from the body to a home base station fi'om where the data can be forwarded to a hospital, clinic, or a service provider in real-time. The WBAN technology is still in its primitive stage and is being widely researched. The technology, once accepted and adopted, is expected to be a breakthrough invention in many healthcare applications, leading to concepts like telemedicine and mobile health monitoring. 1.2 Applications of Body Area Networks Initial applications of WBANS are expected to appear primarily in the healthcare domain, especially for continuous monitoring and logging of vital parameters of patients suffering from chronic diseases such as diabetes, asthma and heart attacks, as well as in elder care monitoring. Other emerging applications of this technology include military, sports and security. Extending the technology to new areas could also assist communication by seamless exchanges of information between individuals, or between individual and machines. Figure 1.1 demonstrates a few examples of WBAN applications. Service Provider Data Collection Figure 1.1: Body Area Networks Applications 1.2.1 Healthcare Applications Wearable systems for continuous health monitoring are a key technology in helping the transition to more proactive and affordable healthcare. They allow individuals to closely monitor changes in their vital signs and provide feedback to help maintain an optimal health status. If integrated into a telemedical system, these systems can alert medical personnel when life-threatening changes occur. In addition, the wearable systems can be used for health monitoring of patients in ambulatory settings [6]. For example, they can be used as a part of a diagnostic procedure, optimal maintenance of a chronic condition, a supervised recovery from an acute event or surgical procedure, to monitor adherence to treatment guidelines (e.g., regular cardiovascular exercise), or to monitor effects of drug therapy. The multiple WBAN sensor nodes shown in Figure 1.2 are capable of sampling, processing, and communicating one or more vital signs like heart rate, blood pressure, oxygen saturation, breathing rate, diabetes, body temperature, ECG and activity, or environmental parameters like location, temperature, humidity, light, movement, proximity and direction. Typically, these sensors are implanted or placed strategically on the human body as tiny patches or hidden in users’ clothes allowing ubiquitous health monitoring in their native environment for extended periods of time. Modalities: - Blood pressure - Heart rate - Breathing rate -. _ Diabetes ' ‘ ' - Temperatures“ - Humidity ' ' - ECG - Movement - Proximity - Direction Out-of-Body Server Figure 1.2: Body Area Sensor Network The Institute of Electrical and Electronics Engineers (IEEE) approved five ISO/IEEE 11073 standards for automatic acquisition of vital signs by clinical information systems [7-11]. Those five standards are in the domain of information model, the common nomenclature, the basic communications profiles, and two defining underlying transport arrangements. All major manufacturers have prototype devices using these five standards as point-of-care device communication standards, but most of them are reluctant to make further investment until user demand recovers. Both USA and UK governments have specified that ISO/IEEE11073 Shall be used for device communication [7],[8]. While the major parts of these standards deal with information representation and data formatting, they do not propose any specific routing and power control models. The role of this thesis is to carry out an early analysis of such broad networkng issues in order to support the standardized data formats as proposed by the IEEE standards. 1.2.2 Activity Monitoring Applications Human activity has been studied [12-17] for the purposes of understanding the basic characteristics of human movement and the relationship of physical activity to chronic diseases such as cardiovascular disease and cancer, as well as for monitoring elderly patients. The accurate and detailed measurement of physical activity is therefore a crucial prerequisite to exploring its association with health and disease. Numerous methods have been used to measure physical activity in the short and long terms [2],[18-23]. They vary greatly in their applicability in epidemiological research, intervention studies, clinical practice, and personal assessment. Human activity monitoring has also been used for studying obesity among children of all ages [18],[21]. The purpose of these studies was to record the physical activity levels of children while they attend preschools, to identify the demographic factors that might be associated with physical activity among those children, and to determine the extent to which children’s physical activity varies among preschools. 1.2.3 Military Applications The physical safety and well being of the soldiers in a battlefield is the highest priority [24-26] of Incident Commanders. Currently, the ability to track and monitor soldiers relies on visual and verbal communication which can be somewhat limited in scenarios where the soldiers are deployed inside buildings and enclosed areas that are out of visual range of the commanders. Also, the need for stealth can often prevent a battling soldier from sending verbal clues to a commander about his or her physical well being. Sensor technologies can remotely provide various data about the soldiers including physiological monitoring and personal alert safety system functionality. A body area wireless network with multi-modal sensors can monitor the body movement and other physiological parameters for statistical identification of a soldier’s body posture, which can then be indicative of the physical conditions and safety alerts of the soldier in question. Soldier tele-monitoring using WBAN system would include: 1) The wounded soldier’s on-body sensor network to identify the soldier’s body posture (e. g. lying down on back would indicate a worrisome situation). 2) Assess the soldier’s context with respect to his or her surroundings by sensing other fellow soldiers and the athletic [24] assets such as tanks, aircrafis and medical facilities. 3) Delivering information from items (1) and (2) to remotely situated commanders and to local fellow military personnel. 4) To take an appropriate rescue, medical or evacuation decision. Since the majority of information gathering and situational assessment processes are automated, the rescue, evacuation and medical actions can be taken in a swift and safe manner due to the stealth nature of the outlined process. CEnergy'iwaie Wireless Body Area ( Appl‘cam’ns \ mumcanon Networks (WBAN) [Limited Sensor ] Characterization of - gs? Modalities On-Body RF Links] i it ’ . RSSI Readingl " - \ taming / Body ;. Transmission Power Movement-{I Network-integrated] Control . WBAN: Applications, I, Proximity Sensing (Chapter 4) . Challenges and Archrtecture ' .4 Overview (Chapter 1 & 2) Fixed 7' l ' \t I [ Linear, Binary, DPPI]/ \ (Chapter 3) Ultra-Low Postural Power Sensor Disconnection Store and Forwarding Modeling .WBAN Power Control Routin_ Routing k (Chapter 5) j K (Chapter 6) (Chapter 7) J Figure 1.3: Pictorial summary of the investigated issues in this thesis [ Gaussian Control DTN Routing i [[Linear-Quadratic ]\ Single Copy J Posture-Predictive (LQGI) 1.3 Challenges, Issues and Thesis Contribution Deployment of WBAN systems will need to address a number of technical challenges that lie ahead [27-32]. These include the need for innovative sensor design, efficient data processing, energy management, and secure data transfer. The goal of this thesis is to design and investigate a framework for network-integrated sensing and energy-aware protocols to address the resource constraints inherent in WBANS. Available energy, processing, and form factor constraints of a body-mounted or implanted sensor can severely limit its abilities for sensing, and the power and range of radio transmission for communication purposes. We investigate sensing, processing, and protocol solutions to address these system constraints. Figure 1.3 shows a Visual illustration of the scope of the work presented in this thesis. The following sections elaborate the topics in Figure 1.3 in more details. 1.3.1 Limited Sensing Modalities A large number of WBAN applications deal with physical activity monitoring and body posture detection, especially for continuous monitoring of patients suffering from chronic disease. The number and the accuracy of the detected postures depend on the number of available sensing modalities and the processing capability. In a number of papers in the literature [19],[33],[34], multi-axis accelerometers are the only modality used for the identification of body postures by analyzing the level of accelerations in different body segments, which are a direct indication of physical activity. These mechanisms are shown to work [35-3 7] very well for identifying postures such as walking, jogging, and sprinting. However, for those applications that require context identification at finer granularities, it is often necessary to differentiate between low-activity postures such as sitting, lying-down and standing; sometimes with even finer granularity such as sitting-upright or sitting-reclined. For these non activity-intensive postures, the traditional accelerometer-based solutions do not work. 1.3.1.1 Proposed Inter-sensor Relative Proximity To address the above limitation, new sensing modalities are needed in addition to the standard accelerometry. But adding more modalities in a WBAN sensor can be difficult due to the ultra-small form factor, energy and processing constraints, especially for implanted sensors. In this thesis, we have developed a novel network-integrated sensing modality, inter-sensor relative proximity, which is inferred from the measured Received Signal Strength Indicator (RSSI) of the Radio Frequency (RF) signal between each pair of WBAN sensors. By using this new sensing modality, more non-activity-intensive postures can be detected, without having to add extra components and the associated energy overhead. Chapter 3 introduces this network-integrated proximity sensing. An experimental system is developed for integrating the proximity data with other traditional modalities, such as acceleration and orientation. This multi-modal data is then processed using an HMM framework for accurate posture identification. 1.3.2 Energy Management Since most wirelessly networked devices are operated fiom battery or from harvesting energy [38-43], one of the major research challenges is the issue of power limitations [30],[44-48]. Sometimes it is important to guarantee that the device will work for certain period (c. g. 5 years) before changing the battery [49],[50]. This is particularly crucial for implanted sensors for which the battery replacement can be an involved procedure [51-58]. Therefore, better power management schemes to deal with these issues must be designed. The following issues are dealt with in this thesis. 1.3.2.1 'II'ansmission Power Control Data transaction across on-body sensors can be point-to-point or multi-point-to-point depending on specific applications. While real-time on-body detection of an athlete’s instantaneous posture [19],[59] would require multi-point-to-point data exchange across various on-body sensors, applications such as monitoring vital signs of a patient will require all body-mounted and implanted sensors [60],[61] to transmit data to a sink node, which in turn will relay the information wirelessly to an off-body server. For both cases, the optimal transmission power required for an on-body wireless link between two sensors depends on: 1) the physical distance of the link [62], and 2) its instantaneous channel condition. The distance can vary with mobility driven by human postures, and the channel condition can change due to unpredictable RF attenuation [63] caused by many factors including antenna orientation, clothing, and physical stature of specific subject individuals. We coined the term postural position which defines the instantaneous state of an on-body wireless link as a result of its distance and the RF attenuation. An on-body link’s postural position can be highly dynamic due to the reasons listed above. AS a result, static pre-defined transmission power is not able to provide continuous link connectivity while ensuring minimum required transmission power consumption [62],[64]. Therefore a dynamic link power assignment mechanism for Optimal energy management is needed. 1.3.2.1.] Proposed Orr-body Transmission Power Assignments Three different dynamic on-body link transmission power assignment mechanisms are proposed, namely, Linear, Binary and Dynamic Postural Position Inference (DPPI). In these approaches, the receiver/control node computes a new desirable transmission power level for the transmitter node by incrementing or decrementing the current power level based on the received RSSI values with respect an RSSI threshold range. No changes are needed when the RSSI falls within the range. This closed-loop control logic ensures that, for a given postural position, this process eventually achieves a desirable transmission power level so that the RSSI at the receiver falls within the preset threshold range. Chapter 4 provides detailed information of transmission power assignment mechanisms. The proposed transmission power control mechanism is then enhanced by modeling human body movement as a stochastic linear system and a quantized Linear Quadratic Gaussian control with an Integrator (LQGI). The objective is to develop a model based power control framework in which RF signal strength is predicted and is regulated at a reference value to enhance the overall energy performance of an on-body wireless sensor. The predictive LQGI power control will be studied in Chapter 5. 1.3.2.2 Data Routing with Ultra-low Radio Transmission Range On-body packet routing is needed in the presence of topological partitioning caused due to ultra-short wireless range and postural body movements. Short transmission range is a common constraint for low-power RF transceivers designed for embedded applications with limited energy [62],[64], ofien supplied by harvested operations [65]. Such Situations are particularly pertinent for implantable body sensors. In literature [65-68] the ultra-low-range transceivers vary in range between Om to 1m, with corresponding transmission powers varying between 0.7 SmW to 6mW, which are within a range that can be handled with common harvesting techniques such as piezo-electric generation from body movements [65]. Low RF transmission ranges also mean that postural body movements can give rise to frequent partitioning or disconnection in WBAN topologies, resulting in the need for a body area Delay Tolerant Network (DTN) [69-74]. Such topological partitioning can ofien get aggravated by the unpredictable RF attenuation caused due to Signal blockage by clothing material and body segments. Topological partitioning necessitates store-and-forward routing protocols with performance goals of low end-to-end packet delay, packet loss, and transmission energy consumption. 1. 3. 2.2.1 Store-and-forward Packet Routing In this thesis we have developed on-body store-and-forward packet routing algorithms in the presence of network partitioning. The objective is to minimize 10 end-to-end packet delay by dynamically choosing routes on which the storage/buffering delays are low. While ensuring low storage delay, the algorithms also attempt to minimize the end-to-end hop count so that the transmission energy drainage is minimized, thus leading to long network operating durations. First, using a prototype WBAN, we have developed a topology characterization mechanism in order to demonstrate the network partitioning caused due to human postural mobility. Second, an on-body packet routing fi'amework is developed using a stochastic link cost formulation, reflecting the body postural trends. Third, the performance of the proposed protocols is evaluated experimentally and through simulation using the prototype WBAN. The performance of the routing protocol is then compared with a probabilistic DTN routing protocol PROPHET [74], and a specialized flooding based benchmark algorithm that provides routing delay lower bounds. Chapter 6 provides the details of this proposed routing protocol. Finally, analytical techniques are developed for modeling end-to-end packet delay for the proposed DTN routing algorithms. DTN routing delay obtained from the developed model are then compared with results from on-body experiments from the prototype WBAN and off-body simulation carried out with network topology traces obtained from the prototype WBAN. Using the model and the topology trace data, a detailed analysis is then carried out for identifying non-critical links in order to design a minimal WBAN topology fiom the routing standpoint. Detailed discussion of modeling techniques and performances in the presence of postural disconnections will be presented in Chapter 7. ll Chapter 2. WBAN Laboratory Prototype System A laboratory prototype system was developed for carrying out all experimental work presented in this thesis. Diabetes Direction Pulse Acceleration Direction Out—of-Body smk Server Figure 2.1: Wearable sensor network and health monitoring prototype 2.1 Wearable Sensor Nodes The prototype WBAN was constructed by mounting a set of tiny sensor nodes on different segments of the body (e.g. thigh, arm, ankle, waist, head, etc.), as shown in Figure 2.1. These wearable sensor nodes consist of a Mica2Dot MOTE [75],[76] radio node (running the TinyOS operating system) [77], operating with a 915MHz radio using a Chipcon SmartRF CClOOO radio chip [75], and its sensor card, MT S510, from Crossbow Inc. [78]. The MicaZDot nodes run from a 570mAH button cell with a total node weight of approximately 10 grams. The default CSMA MAC protocol is used with a 12 data rate of 38.4kbps. The sensors are worn with elastic bands in such a manner that a sensor and its antenna orientation with respect to the mounted body segment do not change with a subject’s posture changes. Atrnel ATMega128 Top—side .. .. Figure 2.2: MICAZDOT sensor node [78] The body-worn sensors form a mesh or a star topology depending on point-to-point or multi-point-to-point data requirements in specific applications. Depending on the topology, a body-mounted sensor sends data to another body-mounted sensor or to a sink node. The Sink node collects raw data, and sends processed results or events to an off-body server using a wireless link. This extemal link is created between the on-body sink node (or it can be any on—body node) and to an off-body base station contacted using another Mica2Dot radio node. The base station is connected to a Windows PC (compute server) through a custom-built serial interface, running the RS232 protocol. 13 Processor/Radio Board MPR500CA Remarks Processor Performance Program Flash Memory 128K bytes Measurement (Serial) Flash 512K bytes >100,000 Measurements Configuration EEPROM 4K bytes Serial Communications UART 0-3V transmission levels Analog to Digital Converter 10 bit ADC 6 channel, 0-3V input Other Interfaces D10 9 channels Current Draw 8 mA Active mode < 15 PA Sleep mode Mum-Channel Radio Center Frequency 868/916 MHz ISM bands Number of Channels 4/50 Programmable, country specific Data Rate 38.4 Kbaud Manchester encoded RF Power -20 to +5 dBm Programmable, typical Receive Sensitivity -98 dBm Typical, analog RSSI at AD Ch.0 Outdoor Range 500 fi 1/4 Wave dipole, line of sight Current Draw 27 mA Transmit with maximum power 10 mA Receive < 1 [LA Sleep Electromechanical Battery 3V Coin Cell External Power 2.7 - 3.3 V Connector provided User Interface 1 LED User programmable Size (in) 1.0 x 0.25 Excluding battery pack (mm) 25 x 6 Excluding battery pack Weight (oz) 0.1 1 Excluding batteries (grams) 3 Excluding batteries Expansion Connector 18 pins All major I/O signals Figure 2.3: MICAZDOT mote specifications [78] 2.2 Sensor Node Hardware The MICAZDOT mote from Crossbow Technology Inc. (see Figure 2.2) is a third generation tiny wireless mote module which is typically used for low-power wireless sensor networks. The low-power processor in the Mica2DOT is an Atrnel ATmega 128L whose 18-pin expansion connector provides various interfacing options including analog and digital I/O, 12C, SP1 and UART-based communication. The MTSSIO sensor board 14 connected to the 18-pin connector can be used for light, temperature, acceleration and acoustic sensing. The specification sheet for the MICAZDOT is shown in Figure 2.3 [78]. Pout PA_POW (hex) Current Consumption (dBm) 915 MHz (mA) -20 0x02 8.6 -19 0x02 8.8 -18 0x03 9.0 -17 0x03 9.0 -16 0x04 9.1 -15 0x05 9.3 -14 0x05 9.3 -13 0x06 9.5 -12 0x07 9.7 -11 0x08 9.9 -10 0x09 10.1 -9 0x0b 10.4 -8 0x00 10.6 -7 0x0d 10.8 -6 0x0f 1 1 .1 -5 0x40 13.8 -4 0x50 14.5 -3 0x50 14.5 -2 0x60 15.1 —1 0x70 15.8 0 0x80 16.8 1 0x90 17.2 2 OxbO 18.5 3 0xc0 19.2 4 Oxfi) 21 .3 5 Oxff 25.4 Table 2.1: Chipcon CC1000 Output Power Settings and Typical Current [75] 2.3 MICAZDOT Radio The radio used by the MICAZDOT is an ISM band RF transceiver designed for low-power and low-voltage Wireless applications. It uses Chipcon’s CClOOO radio [78], which employs Frequency Shift Keying (FSK) with Manchester encoding and an effective data rate of 38.4kbps. The radio on the MICAZDOT is capable of multiple 15 channel operation within the intended band. It can also be software adjusted for a range of output power levels. The register in the radio that controls the RF power level is designated PA_POW at address OXOB, and the values and their corresponding RF outputs are provided on Table 2.1 [75]. It shows the closest programmable value for output powers in steps of 1 dBm. 2.4 Software Platform The sensor node software is responsible for data sampling and acquisition, real-time processing, and WBAN communication. Software running on the sensor nodes and the network base station is developed using the nesC language under the TinyOS operating system [77]. TinyOS is an open source component-based event-driven embedded operating system mainly targeted at wireless sensor networks. It is designed as a set of cooperating tasks and processes, and it incorporates rapid innovation as well as operating within the severe memory constraints inherent in sensor networks. Programming in TinyOS is performed in nesC, a dialect of the C programming language optimized for memory-limited sensor networks. NeSC has a C-like syntax, but supports the TinyOS concurrency model, and mechanisms for structuring, naming, and linking together software components into networked embedded systems. TinyOS provides built-in interfaces, modules, components, and sensor-board-specific configurations, which allow programmers to build programs as a set of modules for program-Specific tasks. Interface to standard hardware inputs, outputs, and sensors are provided by the components in TinyOS. The application program is statically linked with TinyOS, and compiled into a small binary file, using a custom GNU tool chain. 16 / Energy Management in WBAN \ Tier-4: Modeling On-body DTN Routing (Ch-7) \ Ultra-Low f Postural .% ,. Single Copy , Power Sensor ' Partitioning ' ' DTN Routing) Tier-3 Packet Routing In WBAN (Ch 6) ---------------------------------------- UIII'a-LOW :§ ~ Postural . Hag; Power Sensor i; . Partitioning E‘ Tier-2: Transmission Power Control (Ch-4&5) Dynamic Power Linear Quadratic Gaussian k Assignment with an Integrator (LQCy f Tier-1: Embedded/Wearable Sensor (Ch-3) \ ' Hardware and Software Mlti-Modal Sensing Mica2Dot MOTE Accelerortletw MTSSIO Sensor Card Orientation TinyOS Operating System ' Network-mtegrated k ' Relative Proximity / Figure 2.4: WBAN System Architecture 2.5 Transmission Power Assignment The energy required for packet transmissions and receptions, which has been addressed by transmission power control techniques, is considered as the primary source of energy drainage in WBAN. The idea is to use the lowest power level that is adequate to maintain acceptable packet delivery performance. Using a lower power level achieves reduced energy consumption, reduced interference and limited heat loss. The 22 different transmission power levels [62],[75] used in our prototype system are shown in Table 2.1 which are used in dynamic transmission power assignments that we will discuss in Chapter 4 and Chapter 5. 17 2.6 Prototype System Components The prototype WBAN described in this chapter is consistently used for the experimental evaluation of all the protocols developed in this thesis. Figure 2.4 demonstrates a layered representation of the various thesis project components on the prototype. 18 Chapter 3. Network-integrated Proximity Sensing for Physical Posture Detection 3.1 Introduction and Related Work In this chapter we have developed a novel network-integrated sensing modality, inter-sensor relative proximity, which is inferred from the measured Received Signal Strength Indicator (RSSI) of the Radio Frequency (RF) signal between each pair of WBAN sensors. By using this new sensing modality, more non-activity—intensive postures can be detected, without having to add extra components and the associated energy overhead. An experimental system is developed for integrating the proximity data with other traditional modalities such as acceleration and orientation. This multi—modal data is then processed using an HMM fiamework for accurate posture identification. In a number of papers in the literature [19],[33],[34], multi-axis accelerometers are the only modality used for the identification of body postures by analyzing the levels of acceleration in different body segments, which are a direct indication of physical activity. These mechanisms are shown to work [35-37],[79] very well for identifying postures such as walking, jogging, and sprinting. However, for applications that require context identification at finer granularities, it is often necessary to differentiate between low-activity postures such as sitting, lying down and standing; sometimes with even finer granularity such as sitting upright or sitting reclined. For these non-activity-intensive postures, the traditional accelerometer-based solutions do not work. 3.2 Uni-Modal Accelerometry This section outlines the posture identification process using a traditional uni-modal approach [19],[33],[34] using only the acceleration information. Controlled experiments 19 using the prototype system illustrated in Chapter 2 and Figure 2.1 are designed in which human subjects are given predetermined sequences of postures (fi'om the set SIT, STD, REC, DWN, WLK, and RUN) to follow, and a three-node wearable sensor network is used for collecting acceleration data from right thigh, upper right arm, and right ankle. Postures, identified using context detection algorithms, are then temporally correlated with the actual posture sequence given to the subjects for evaluating the identification accuracy. 800 . : {Thigh 700‘ 7 i 5004:] = 400- ‘ i i A 7 i ii. ; i‘\Ankle f 300- ‘ ' .. = Acc. Readings (mg). SIT STDWLK’STDSTD WLKSTD SIT SIT REC REC SIT STD DWNSTDRUNSTD STD SIT STD _ SIT: Sit, STD: Stand, REC: Sit-Reclining, PM” sequence 0"“ “me (5) WLK: Walk, DWN: Lying Down, RUN: Run 200 Figure 3.1: Accelerometer data during a controlled posture sequence Figure 3.1 shows the accelerometers’ readings in milli-g (1 mg is 9.81 mm/sz) from all three sensor nodes, while a human subject was following a controlled 20-posture sequence as shown along the horizontal axis of the figure. Each posture Slot in this experiment lasted for approximately 20 seconds. A sampling rate of 20 Hz was used for obtaining reading from the accelerometers. The numbers in the figure correspond to the averages of the accelerations recorded in both the axes of the sensor used. The figure shows how the acceleration readings increase for the activity-intensive postures such as WLK and RUN compared to low-activity postures such as SIT and 20 STAND. In fact the readings for SIT, REC, DWN and STD are almost the same due to the absence of any major physical activity in these postures. The frequency domain representation of the accelerometer data collected is presented in Figure 3.2 for all six postures individually. The graph for WLK, for example, is plotted by applying the Fourier Transform (FT) to the cumulative acceleration data from all the WLK states as shown in Figure 3.2. The same applies to the other postures as well. FFT Amplitude 0 0.02 0.04 0.06 0.08 0.1 Frequency (Normalized by sampling frequency) Figure 3 .2: Frequency domain view of the acceleration readings Observe that while the graphs for WLK and RUN demonstrate a noticeable presence of frequency components in the range 0 to 0.1, the ones for SIT, REC, DWN and STD are ahnost flat over the entire frequency spectrum. The difference in the peak values for WLK and RUN indicates the difference of activity levels in those two postures. These peak values, coupled with suitably chosen thresholds, can be used for identification and differentiation between the WLK and RUN postures. The results in Figure 3.1 and Figure 3.2 confirm that while unirnodal accelerometry is capable of identifying WLK and RUN, it is not sufficient for the low-activity postures. 21 To address this limitation, new sensing modalities are needed in addition to the standard accelerometry. But adding more modalities in a WBAN sensor can be difficult due to the ultra-small form factor, energy and processing constraints, especially for implanted sensors. 3.3 Inter-sensor Relative Proximity In this chapter, we have developed a novel network-integrated sensing modality, inter-sensor relative proximity, which is inferred from the measured Received Signal Strength Indicator (RSSI) of the Radio Frequency (RF) signal between each pair of WBAN sensors. By using this new sensing modality, more non-activity-intensive postures can be detected, without having to add extra components and the associated energy overhead. In this chapter, an experimental system is developed for integrating the proximity data with other traditional modalities including acceleration and orientation. This multi-modal data is then processed using a Hidden Markov Model (HMM) framework for assessing the instantaneous body postures. The HMM is leveraged for dealing with the proximity sensing errors caused by a subject’s clothing, body structure, irregular RF propagation, and the variability in sensor mounting. We have developed a WBAN system [24],[60],[6l] that is capable of detecting a wide set of postures including SIT, SIT-RECLINING, LYING-DOWN, STAND, WALK and RUN, by leveraging our proposed inter-sensor relative proximity sensing modality and an HMM processing model. An online video demonstrating the preliminary working prototype can be found in [80]. 22 3.4 Target Sensor Modalities Three sensor modalities, namely, acceleration, network-integrated proximity sensing and orientation are used. A two-axis [19],[33] piezoelectric accelerometer in the Mica2Dot sensor card is used for detecting body movements. Acceleration data is generated in the units of gravitational acceleration g. While a near-zero acceleration may mean a very low activity posture such as sitting or lying-down, a high acceleration can indicate a high activity posture such as jogging or running. The novel network-integrated proximity sensing or relative proximity between the sensor nodes is the second sensor modality that is measured in dB using the received signal strength indication (RSSI) of the radio frequency (RF) signal. Each sensor is set to periodically send a Hello message with a preset transmission power that is enough to reach all sensors on the body. Based on those Hello packets, each node creates and maintains a neighbor table, with information regarding RSSI for all other sensor nodes on the body. This way each node maintains a measure of the relative proximity with respect to the other nodes. High RSSI values (high signal strength) indicate that the body parts are positioned relatively close to each other like during a sitting posture. Similarly, relatively lower RSSI values indicate that the corresponding body parts are relatively farther apart (e. g. during a standing posture). Sensor orientation is the third modality that can indicate the orientation of a body segment to which a specific sensor node is attached. Orientation information can be used for identifying low-activity orientation-specific postures such as lying down and reclining. The two-axis [19],[33] piezoelectric accelerometer in the MTSSIO sensor card is also used for orientation detection. The constant component of the accelerometer’s 23 output indicates a sensor node’s orientation. Orientation output is extracted by integrating the acceleration output, and can be assessed for both X and Y directions by the corresponding accelerometer outputs. Therefore, the orientation indicator shares the same units as that for the raw accelerometer output. Offline Online Off-body Indoor workout, Indoor patient and fitness evaluation elderlymonitoring On-body Outdoor workout, Outdoor patinets, fitness evaluation soldiers and Sports monitoring Table 3.1: Computation Modes and their Applications 3.5 Computation Modes As Shown in Table 3.1, body context identification can be categorized into four computation modes: off-body offline, on-body offline, off-body online, and on-body online. For the off-body case, all sensor data is wirelessly collected to an off-body processing server (see Chapter 2) which is used for the context identification. In on-body scenarios, the identification processing is performed at the sensor nodes themselves, either at a single node or at multiple nodes for improved processing load distribution. The offline and online processing modes represents whether the identification is done in real-time or not. For online processing, the amount of available sensor data is generally less than what is available in the offline scenarios. From an application standpoint, the on-body processing is more suitable for outdoor applications since a separate processing server may not usually be available. In indoor settings, however, such servers may be available and therefore the off-body applications can be supported. As summarized in Table 3.1, real-time monitoring applications, 24 off-body or on-body, are better supported using the online processing mode. Applications that require post-collection evaluation are better suited for the offline mode. Results presented in this chapter correspond to off-body and offline computation mode. The prototype system described in this chapter performs off-body and offline posture identification. 3.6 Sensor Placement and Modality Usage Three sensor nodes are mounted at three body locations, namely, the right thigh, the upper right arm and the right ankle. The thigh sensor is used for capturing body acceleration, while all three sensors are used for detecting the relative proximities between all sensor pairs, and both arm and ankle sensors are used for sensing the orientations of those body parts. Through extensive experimentation with different subject individuals it was found that the above sensor placement can provide enough information diversity for all three sensing modalities for them to be applicable to our proposed posture identification process. Sensor Node Sensor Supported Target ID Placement Modality Pastures 1 Upper Right Arm Orientation, SIT, DWN, Proximity STD 2 Lower Right Orientation, SIT, REC, Ankle Proximity DWN, STD 3 Right Thigh Acceleration, WAK, RUN, Proximity SIT, STD Table 3.2: On-Body Sensor Modality and Placement Summary A summary of placement, supported modality, and target posture information is shown in Table 3.2. While all three nodes are programmed to provide RSSI-based proximity data, the nodes on the arm and ankle are used for generating orientation 25 information, and the sensor node on thigh is used for assessing a subject’s level of bodily acceleration. The last column identifies which set of physical postures that each specific sensor node contributes toward measuring. Throughout the rest of the chapter the target postures will be abbreviated as: SIT (sit straight), STD (stand), REC (sit reclining), DWN (lying down), WLK (walk), and RUN (run). Note that while more sensors provide a richer set of data to work with, they also make the overall sensor-wearing process increasingly cumbersome. Therefore, a key objective of the system design is to achieve high posture-identification success with as few sensor nodes as possible. Also, it was found that due to the variability of the RF links caused primarily by body movements, antenna mis-orientation, and signal blockage by clothing material, not only does the network topology become unpredictably dynamic, but the proximity information indicated by the RSSI values can also vary over a very large range. This has the potential for introducing serious inaccuracies in the posture identification unless specific measures are taken to suppress the effects of such measurement errors. A Hidden Markov Model has been used to specifically address these measurement errors and variability. 3.7 Posture Modeling and Generation The posture transitions of a human subject are modeled as a Markov Process in which the subject’s posture transitions are assumed to follow a memoryless process [81],[82]. The transition probabilities across the postures, as shown in Figure 3.3, represent a subject’s behavior that is assumed to remain stationary for a certain time interval. The corresponding transition matrix, termed as A, remains fixed during such an interval, and can vary across the intervals when there is a broad change in behavior. In 26 the following experiments we generate a sequence of 50 posture states using the transition probability matrix: ”0.5 0.2 0.1 0.2 0 o 1 0.5 0.5 0 0 0 0 0.2 0 0.5 0.3 0 0 A=iai,j]= 0.3 0 0.1 0.4 0.1 0.1 , 0.1 0 0.1 0.2 0.4 0.2 __ 0 O 0.1 0.2 0.3 0.4_ in which states 1 through 6 represent the postures SIT, REC, DWN, STD, WLK and RUN respectively. Figure 3.3: Posture state transition machine 27 is not applicable to ACfiVityi/ow Moderate High Accelerometry C Level @— B: i v E IE differentiate between ¥ th tur V ese pos es Accelerometry is applicable for _ posture detection High RSSI is not applicable to differentiate SIT DWN Q I lRECl I D between these postures Vertical Horizontal Arm Sensor - Orientation is not applicable to differentiate between these postures - SIT: sitting - REC: sit-reclining - DWN: lying-down - STD: standing - WLK: walking - RUN: running Vertical Horizontal Figure 3.4: Posture identification using multi-modal thresholds As a part of each experiment, a human subject is handed the resulting posture sequence and is instructed to follow the sequence with 20 sec being spent in each posture thus the entire experiment lasts for 1000 see. Note that the transition matrix A is chosen 28 based on long observation of typical behavioral patterns of multiple human subjects in our laboratory setting. 3.8 Threshold-based Identification The flowchart in Figure 3.4 depicts a mechanism in which context identification is accomplished by applying different thresholds for all three sensing modalities. After the low- and high-activity postures are separated using the degree of acceleration recorded by the node on the thigh, a proximity threshold (applied in terms of RSSI) is used to distinguish between STD (stand) and the other remaining postures, namely, SIT, REC, and DWN. The lying-down (DWN) posture can subsequently be separated using the orientation information from the node on the arm. Finally, the differentiation between SIT and REC is performed based on the orientation information from the ankle. Details about the exact threshold values used for different sensor modalities are presented in Table 3.3. Results presented in this section correspond to an off-body and offline computation mode. Threshold Moderate High Avg. Arm Ankle Group Activity Activity RSSI Ornt. Ornt. Level (mg/s) Level (mg/s) (-dBm) (mg) (mgL T hr] 5 20 80 460 470 Thrz 5 30 70 470 480 Thr3 8 30 80 480 490 Thu 8 30 90 490 500 Thr5 8 30 100 500 510 Tim; 8 30 110 510 520 Tiny 8 30 120 520 530 Thrg 8 30 130 530 540 Table 3.3: Threshold group values for context identification Sensor reading for all three modalities and the corresponding actual postures for all 50 posture slots are reported in Figure 3.5. For the sake of brevity, the postures SIT, 29 REC, DWN, STD, WLK and RUN are identified by the letters S, R, D, T, W and U respectively. The actual state (the posture that the subject is in) during a slot is reported A (a) Thigh accelerometer output $320 . .. . ‘ Actual States Activityh‘avelof . ; ; l . . _ , ' V240‘?‘;;;;g_: ThighSensorii"'??ff'ili§“‘:‘.;i." o . . '1' TTSSTSSS’I‘W’ITWTSSSSSSSTSSSSSRSRSSRRRRSDTSSTDTUTTSST Activity Level in W O Time(s) A (b) Average RSSI values m320 ‘,I.': ;I‘I;." '3, :ActualStates .;:;:':‘...;f;“AngSSIVaIues;:.2:';ff 5240‘;::i::‘mt'if:"‘::lA“:‘ 0 on «3 S > .‘ '.i ~ ..,. .: . < 111111 I I IIIIIIIIIIIIIII III IIIIIII TTSSTSSSIWIIWISSSSSSSTSSSSSRSRSSRRRRSDTSSTDTUTTSST Time(s) 320 (c) Arm accelerometer output ’33 ILL‘Ei-ActualStatesin‘Ji AnnSensorAcc.iT;lii" E l-I ..I;;'.:l‘::.:I::‘:: -l; I: .9 E s: g . TTSSTSSSTWIIWISSSSSSSTSSSSSRSRSSRRRRSDTSSTDTUTTSST Time (s) (d) Ankle accelerometer output ActualStates AnkleSensOrAcc 0 ll TTWSSTSSSIWI IWISSSSSSSTSSSSSRSRSSRRRRSDTSSTDTUTTSST Time(s) Figure 3.5: Sensor outputs and actual postures 30 by the corresponding letter on the horizontal axis during the slot. With each slot lasting for 20 seconds, the entire experiment corresponds to 1000 seconds, representing 50 posture slots. The graph in Figure 3.5:a reports the actual posture states and the corresponding activity levels, which are computed as the absolute values of the first order derivatives of the raw accelerometer outputs. The derivative represents the difference between two successive acceleration samples collected at a 20Hz sampling rate. The computed derivative numbers are then integrated using a moving average with window size of 5 sampling slots. Finally, those integrated derivative numbers for both X and Y directions (using the accelerometer outputs for both X and Y axes from the thigh-mounted sensor) are averaged to produce the activity levels that are plotted in Figure 3.5:a. As expected, the activity levels are high for the W and U (WALK or RUN) slots, and low for all other posture slots. Average proximity information from all three sensor nodes, along with the actual postures, is reported in Figure 3.5:b. Each node periodically (once in every Hello interval of 1.5 seconds) computes the average RSSI value based on the radio signal reception through Hello packets from the other two nodes, and then wirelessly sends that data to the thigh-mounted sensor. This thigh sensor then computes a master average based on the averages received from the other two sensors and its own average. This final average (in -dBm), which is reported in Figure 3.5:b, is then wirelessly transmitted to an off-body machine for further processing. In these readings, high RSSI dB values indicate high received radio signal strength and vice versa. 31 The following observations should be made from Figure 3.5:b. First, the average RSSI has an overall trend to be the lowest for SIT (S) and the highest for STAND (T). This is consistent since the body parts are generally closely situated during sitting, and further apart while standing. The average RSSI values for the other two low-activity postures SIT -RECLINE (R) and LYING-DOWN (D) fall in between those for S and T. Second, while generally maintaining this trend, there are certain anomalies caused by several factors including radio signal blockage by the clothing material, unintentional change of sensor node and antenna orientations, and various other imperfections in sensor mounting. Figure 35:0 and Figure 3.5:d show the X—direction orientation indication (as introduced in Section 3.4) for the sensor nodes attached to the arm and the ankle respectively. Orientation indication is computed by first averaging the raw accelerometer output over 20 samples (i.e., 1 second), and then integrating those average values using a moving average with window size of 5. Both sensors on the arm and the ankle are mounted such that high X-direction orientation values in Figure 35:0 and Figure 3.5:d indicate horizontal orientations of the corresponding body segments, and low values represent relatively vertical orientations. Note that the Y-direction orientation information is not used in these experiments. The arm sensor orientation in general can be used to detect the LYING-DOWN (D) posture, since it is evident in the plot that the arm sensor orientation readings in D postures are distinctively more horizontal (higher values) compared to those during other postures. Also, the ankle sensor orientation can be used to detect both LYING-DOWN (D) and SIT-RECLINING (R), because the orientations of the ankle in these two postures 32 are also distinctively more horizontal (higher values) compared to the other two low-activity postures SIT (S) and STAND (T). Note that the sensor data patterns, as seen in Figure 3.5 for all modalities, are consistent with the threshold-based context identification logic presented in Figure 3.4. Threshold values of all sensor modalities at different sensors are depicted in Table 3 .3. Each set of threshold combinations is grouped together, and eight such groups are depicted in the table. The first and the second columns represent the moderate and the high activity level thresholds to be applied on readings from the thigh-mounted sensor node for difl‘erentiating between the WLK and RUN postures (see Figure 3.4). The third column represents RSSI thresholds for the master average RSSI values collected and computed at the thigh sensor node. The last two columns indicate threshold values to be applied on the orientation readings from the arm and the ankle-mounted sensor nodes respectively. 90% - g E a Subject-3: Subject-2 5.; 80% — I , / ~ 2 A . ? ’ 0 E ‘ I 2 g0 70%- 4' 'i 1 a 3 I ‘ 8 ? s b' tl/ ? g 60%- 2~ ~ “513‘? 50% i ; i i ; i 4 ; Thrr Thrz Thrs Thr4 Thrs Thre Thr7 Thrs Threshold Values Combinations Figure 3.6: Detection accuracy for multiple human subjects Figure 3.6 depicts the threshold based context detection accuracy computed over the 50-state posture sequence generated by the A matrix reported in Section 3.7. Using the 33 thresholds specified in Table 3.3, the comparison algorithm from Section 3.7 has been applied to the multi-modal sensor data obtained fiom all thee body-mounted sensors for identifying the instantaneous body posture. The identified posture is then compared with the subject’s actual posture for computing the success rate as reported in the figure. Such success rates are presented as percentage matches for different threshold groups and for different human subjects. Three individuals in these experiments were asked to follow the same controlled posture sequence as used in Figure 3.5 for several rounds, before the identification performance was computed. Observe that in spite of the errors contributed by sensor and antenna mis-orientation and radio signal blockage by clothing material, this threshold based mechanism can detect the six postures with up to approximately 84% accuracy. However, since the identification success rate is heavily sensitive to the threshold values, choosing the right threshold values is an important design step for this mechanism to work. A potentially restricting aspect of this threshold-based mechanism is that the optimal threshold values (threshold groups in this case) are also sensitive to the individual subjects’ physical and motor aspects during his or her postures. For example, while the threshold group Thr5 yields the best identification accuracy of 84% match rate for subject-2, the performance for subject-3 maximizes at 82%, for the threshold group Thr3. In fact, at Thr5, for subject-3 the system delivers a poor posture identification rate of only 74%. These results allude to a practical limitation of the threshold-based posture identification in terms of the need for person-specific threshold dimensioning. Other experiments further indicated that the optimal threshold value can change even for an individual based on his or her behavioral changes over time. In the next section we have 34 developed a Hidden Markov Model (HMM)-based mechanism for adaptive and subj ect-independent posture detection. 3.9 Capturing Stationary Behavior Using Hidden Markov Model The inability of the threshold based mechanism to handle the degraded quality of sensor data stems from the fact that the identification process does not leverage the stationary nature of human behavior over certain time intervals. To address this limitation, we adopt a stochastic posture identification solution that attempts to leverage the stationary nature of human posture by modeling the posture state machine as a Hidden Markov Model (HMM) [83-86]. The key concept of the HMM [83] are as follows. A stochastic process is represented by a discrete time Markov Chain consisting of multiple states which are hidden from an observer in the sense that an observer cannot directly determine which state the system is in at any given point in time. However, a number of observable parameters, stochastically representing the states, are visible to the observer. The idea of HMM formulation is that if the state transition probability matrix and the observation generation probabilities are known (or measurable) to the observer, the latter can estimate the current state of the Markov Chain. Using HMM it is also possible to compute the probability of occurrence of a specific state sequence [84-87]. 3.9.1 HMM Mapping The posture identification problem with multi-modal sensing framework is mapped as an HMM formulation as follows. 35 Posture State Space: N postures are modeled as N hidden states with the state space represented by S = {S1, S2, SN}. In this specific case N = 6, for postures SIT, SIT-RECLINING, LYING-DOWN, STAND, WALK and RUN. Observation: At each state, the observation is represented by a vector 0, which is constructed by combining four sub-vectors 0 = [C U X U R U K], where C represents the activity level information from the thigh sensor, X represents the master average RSSI value from all three sensors, and R and K represent the orientation indications from the arm and ankle sensors respectively. HMM observation vectors are constructed from the multi-modal sensor data as shown in Figure 3.5. Each sub-vector is created as follows. The activity level observation at any point in time is represented by the sub-vector C = {c1, c2 ..... cMC}, in which each cm (m =1, 2, MC) is a binary variable which can be either ‘0’ or ‘1’. The peak-to-peak activity level range (see Figure 3.5:a) is divided into MC equal windows, and then depending on which window the current activity level falls in, the corresponding cm is set to ‘1’, and the rest of the sub-vector elements are set to ’0’. Note that the value of MC determines the granularity of observation, which in turn, is expected to influence the quality of the hidden posture state identification process. The flindow _B_oundary (WB) points for the sub-vector C is represented by WBC. The number if WB points is one less than the value of MC. Observation sub-vectors X, R, and K for RSSI values and orientation indications from the arm and the ankle sensors are constructed using the same mechanism as used above for the activity level sub-vector C. The corresponding granularity factors (e. g. the sub-vector size) are indicated as MX, MR and MK respectively, and the window boundary points are represented by WBX, WBR, and WBK respectively. 36 At any time instant t, all four sub-vectors are combined into an overall observation vector 0,. Also, an overall observation granularity factor M is computed by adding the individual granularity factors MC, MX, MR and MK. The minimum value of M in our system was chosen to be 9, with corresponding values of MC, MX, MR and MK to be 3, 2, 2, and 2 respectively. We have experimented with various values of M, ranging from 9 (coarse granularity observation) to 15 (fine granularity observation). For M to be 15, MC, MX, MR and MK were chosen to be 4, 5, 3, and 3 respectively. Consider an example in which M is chosen to be 9 with MC, MX, MR and MK as 3, 2, 2, and 2, and the window boundaries WBC, WBX , WBR, and WBK are chosen as {8, 30} mg/s, 90 dB, 490 mg, and 500 mg respectively. Now with raw sensor outputs representing activity level of 4 mg/s, RSSI of 70 dB, and arm and ankle orientation indications of 470 mg and 480 mg, the resulting sub-vectors C, X, R, K will be [1,0,0], [1,0], [1,0], and [1,0] respectively. Therefore, the overall observation vector 0 will be [1, 0, 0,1, 0,1, 0,1, 0]. As indicated in Figure 3.3, the parameter 0, represents the observation vector at time slot t, with T as the final observations in an experiment. In all our experiments, the value of T is 50. In other words, 50 observations, each corresponds a state lasting for 20 seconds, are generated to feed into the HMM estimation system. Transition Probability Matrix: The posture transition probability matrix is represented as A = [“111] , where ai,j:p(q:=Sjlqt—1:Si)a ISi,jSN (3.1) 37 A is an N x N matrix, where N corresponds to the number of postures (states), which is 6 in our case. The quantity q, denotes the actual posture at time t. The parameter aij represents the probability that the next posture is j, given the current posture of the subject is i. Observation Probability Matrix: As done for the observation vector 0, the observation probability matrix B is constructed by combining four sub-matrices as B =[BC UBX UBR UBK] , where BC, BX, BR and BK correspond to activity level, RSSI and orientation indications from the arm and the ankle sensors respectively. The elements of sub-matrix BC, whose dimensions are N x MC, are represented by: bm -_-p(C=[cl = 0,....,cm = l,....cMC = O] |q, =Sj), ISjSN,ISmSMC, (3'2) where C represents the activity level observation sub-vector. The parameter bi," represents the probability that in posture state j, the element cm in the observation sub-vector C is ‘1’ and the rest of the elements in C are all zeros. In other words, when a human-subject is in postures state j (f can be one of six targeted postures in our system), the quantity bi," indicates the probability that the observed activity level falls in the mth window of observation within the sub-vector C. Following the same mechanism as used above for the activity level, observation probability sub-matrices BX, BR, and BK are constructed for observed RSSI and orientation indications from the arm and the ankle sensors. The dimensions of those sub-matrices are N x MX, N x MK, and N x MR. Combing all four sub-matrices, as shown below, the overall observation probability matrix B with dimension N x M is constructed. 38 B = [BC sub — matrix BX sub — matrix BR sub - matrix BK sub - matrix] where 'ch1 .. b1,cm .. bLCMC I —bl,.x1 " bkfm '° 1’1,qu I BC: bj,c1 .. bjICm .. bjaCMC ,BX = bj,x1 '° bj,xm °° bj,xMX _bN,c1 ,, bN,Cm ,, bN,CMC_ _bN,x1 .. bem .. bNJMX_ pblfl.l .. erm .. bum I P b1,.k1 " bl,Icm .. [91$ij - BR= bin -- be... -- brim and BK = 1’qu -- [’ka .. bLkMK thfl .. bN,,m .. bNa’MR _ _bN,k1 .. kam .. bNakMK _ Initial State Distribution: This is represented by a vector 7r=[7t,.] of length N, so that: ”i=p(qo=Si)a ISiSN (3-3) The quantity 7:, represents the probability that the posture Markov chain is N initialized at state i. By definition, 2 77: = 1 . i=1 Based on the above definitions, a system, modeled using HMM, can be fully specified by the parameters A, B and 1: which are represented together as a tuple: xl=(A,B,7r) (3.4) As presented in the next section, we first compute the individual probabilities of the system being in each possible posture state at a given time. As shown in the derivation, these probabilities depend on the system’s xi , and the observation sequence {01 02 0 3 . 0T}- After the probabilities are computed, the posture state identification is 39 accomplished by finding the most likely state, which is the one with the highest current probability. 3.9.2 Posture Detection using HMM The probability of observing a given sequence 0 = {01.02.---0T} of length T time steps is represented as P(0|).), and can be evaluated using the forward-backward procedure [87], as follows: N P(0/l)=ZlaT(l)9 (3.5) where a, (i) is referred to as forward variable, and defined as: a,(i)EP(01,02,...0,,q, =Si [1). 1S i S N (3.6) It represents the probability that the partial sequence 01, 02, 0,, until time step t, has been observed and the current posture state at time t is S,-, given the HMM model It. a, (l) is a vector of dimension N (which is the total number of possible states). Another variable ,6, (i), referred to as backward variable, is defined as: flt(i)EP(0t+1,...,0T |q, =Si,/l). 1S i S N (3_7) This represents the probability that the partial sequence from time step (t+1) to the end has been observed and the current posture state at time t is 5,, given the model It. ,6, (l) is also a vector of dimension N. Now another variable 7, (i) is defined such that: 7r(i)=P(qr = Si IOJ.) (3.8) 40 where 7, (1) represents the probability of being in state S; at time t, given an observation sequence 0, and the model it. Eqn. 3.8 can be expressed in terms of the forward-backward variables as: ar(i)flr(i)= a.(i)fl.(i) “0"” few (2') ‘3” 7.(i)= which is a vector of dimension N at time t. Using 7, (l) we can solve for the individually most likely posture state q, at time t [83], as: arg max q’:1sisN [70(1)]: 1515 T (3.10) This q, represents the detected posture state at time t. 3.10 Experimental Results 3.10.1 Manual Calibration In this section we describe the performance of HMM based posture identification and its performance in comparison with the threshold based approach described in Section 3.8. The same transition probability matrix "0.5 0.2 0.1 0.2 o 0" 0.5 0.5 0 o 0 0 A=[a,- .1: 0.2 0 0.5 0.3 0 0 . ’1 0.3 0 0.1 0.4 0.1 0.1. 0.1 o 0.1 0.2 0.4 0.2 _0 0 0.1 0.2 0.3 0.4_ 41 as used for the previous experiments, is used for generating a posture sequence to be followed by the human subjects. Note that for the results in this Section, the A matrix used for posture sequence generation is also used for the HMM model formulation. In other words, it is assumed that the A matrix used for HMM is already trained. During an initial set of known states, the B matrix is first computed, and then the actual posture identification process was initiated. This initial period is referred to as an observation calibration phase. As for the Initial State Distribution matrix 1:, we have used [0, 0, 0, 1, 0, 0], for all the experiments results presented here. This means that in all experiments the subject should start with the posture STAND. These A, B and 1: matrices constitute the HMM system parameter A. State identification using/l has been carried out using the HMM technique described in Section 3.9.2. Figure 3.7 reports the posture identification performance with HMM in comparison with the threshold based mechanism as introduced in Section 3.8. As done before, the success rates are measured by comparing the identified postures with the actual postures from the generated posture sequence using transition probability matrix A. M MC, MX, MR, MK WBC WBX WBR WBK 9 3,2,2,2 {8,30} 90 490 500 10 3,3,2,2 {8,30} {80,90} 490 500 11 3,4,2,2 {8,30} {70,80,90} 490 500 12 3,5,2,2 {8,30} {70,80,90,100} 490 500 13 3,5,3,2 {8,30} {70,80,90,100} @90,500} 500 14 3,5,3,3 {8,30} {70,80,90,100} (490,500} (490,500} 15 4,5,3,3 {8,30,40} {70,80,90,100} (490,500} (490,500} Table 3.4: Observation sub-vectors and window boundaries for different observation granularities The success rate for posture identification using HMM is reported with seven different observation granularities corresponding to M = 9, 10, ll, 12, 13, 14, and 15. For 42 each such values of M, the corresponding values of MC, MX, MR and W, and their observation window boundaries are summarized in Table 3.4. Subject-l $3 fins: 2:: $3 Ens; ES: $3 GTE SE: $3 ASHE SE: $3 Bus: 22: $3 87% 22: $8 8qu 22: $3 Ne; $313. _ H _ _ % % % % % % 0 0 0 0 O 0 m 9 00 7 6 5 582 93583 Subject-2 {coo Gun—‘6 ESE $3 Eng 22: $3 GTE 22: $3 ANT—.5 2:: $3 Eng 22: e3: Sun—>5 SEE $3 ans; :2: KL.» M 2:. e\eoc NE... {eon 15,—. 100% 90%_,_, £332 owfiaoocom 80% r 70% r 60% ‘ 50% Subject-3 $3 GTE 22: $3 Eng 22: $3 San—.6 22: $3 STE :2: $3 STE :2: $288—$255 $23522: $3 2: $3 "Ea $3 1.; _ S _ _ % % % % % % 0 0 O 0 0 0 0 9 oo 7 6 5 £032 owfiaoouom Figure 3.7: Posture identification performance 43 The first entry for M = 9 (MC=3, MX=2, MR = 2 and MK = 2) indicates that the three window levels for the C sub-vector are realized with two window boundaries WBC of 8 mg/s and 30 mg/s. Similarly, two window levels for the X sub-vector are realized with one window boundary WBX of 90 dB. Observe in the table that with increasing observation granularities (higher MC, MX, MR and MK) a larger number of window boundaries are needed to implement higher number of observation window levels. The following observations are to be made from Figure 3.7. First, the HMM approach delivers better state match rates (for example 84% to 96% identification success for human subject-2) compared to the best case performance using the threshold-based mechanism (84% identification success for the same subject), that is with the threshold group 4 (8, 30, 70, 490, 510) as shown in Table 3.3. Second, higher observation granularity (larger M) for HMM provides better posture identification success rate, with performance saturation occuning beyond the granularity factor around M = 12. Third, once a sufficiently large observation granularity (e.g. M = 15) is chosen for HMM, unlike in the threshold-based scheme, no optimal parameter dimensioning is needed. This is a significant advantage in terms of implementation feasibility. Finally, with similarly large observation granularities, the HMM continues to provide superior posture identification performance in a human subj cot-independent manner. This further reinforces the practicality of the mechanism in not having to dimension any individual-specific parameter which may cause significant performance variation as observed for the threshold-based mechanism. 3.10.2 Automatic Observation Calibration For the results above, the observation probability matrix B has been constructed during an observation calibration phase before experimenting with each individual human 44 subject. This calibration process (construction of matrix B based on observations) somewhat compensates for the inconsistencies in the observation values due to variations in clothing, personal posture specialties and other ambient differences. In fact this calibration process accounts a great deal for the consistently superior performance of HMM compared to the threshold-based strategy, as presented in Figure 3.7. In this section we implement a self-calibration process of the B matrix, so that the proposed posture identification mechanism can be more practically implemented without having to manually calibrate the B matrix for each individual subject. We use the Baum-Welch iterative algorithm [83], for which the key idea is to start with initial B matrix, and then iteratively adjust it based on the stochastic difference between the identified (using HMM) posture state sequence and the expected sequence based on the notion of the state transition matrix A. Details of the Baum-Welch derivation and the algorithm are included in the Appendix. 100 f l _ = . i 132 f i % :53 90+B3§ , ; a E 2 \ 0 go 80—«-~r/ E \3 § Bl a 70 60 . I . , I ; ; 1 4 7 10 13 16 19 22 Number of Iterations in Baum-Welch Figure 3.8: Automatic self-calibration of the B matrix 45 Figure 3.8 demonstrates the performance of this self-calibration process in terms of the posture identification accuracy over multiple iterations. Here we used the observation sequence of human subject-2 of the last experiments, with observation granularity factor M = 12. Observe that with all three different initial B matrices, the identification accuracy gradually increases over time with Baum-Welch iterations. For all three cases, the posture identification process started delivering the best performance within 12 iterations. In a deployment sense, this means that after wearing the sensors, the subject should continue with his or her regular behavior for a while for allowing the network to self-calibrate the HMM B matrix. After that, the identified posture recording should start. 3.11 Summary Conclusions In this chapter we present a novel network-integrated sensing modality, inter-sensor relative proximity, which is inferred fi’om the measured Received Signal Strength Indicator (RSSI) of the Radio Frequency (RF) signal between each pair of WBAN sensors. The concept of RSSI-based proximity is experimentally developed and then integrated within a Hidden Markov Model (HMM-based stochastic processing framework for accurately identifying human body postures in a subject-independent manner. It was first shown that the traditional uni-modal approach using only the acceleration information do not work well when it is necessary to differentiate between low-activity postures, and we addressed that by proposing the relative proximity sensing modality. Then, it was demonstrated that although a naive threshold-based mechanism can be used for reasonable detection performance, the intrinsic errors and unpredictability of the on-body data collection process require a delicate dimensioning of the used threshold 46 values for consistent posture identification performance across various human subjects. To avoid this, an HMM-based detection process is applied with observation self-calibration using the Baum-Welch algorithm. It was shown in this chapter that the HMM method with our novel sensing modalities are able to consistently deliver significantly better detection performance than the threshold-based mechanism in a more individual-independent manner. 3.12 Appendix: Iterative Hmm With Automatic Observation Calibration As preposed in [83],[86], it is possible to calibrate the HMM parameters in ll. such that the quantity P(0|,l), representing the conditional probability of an observation sequence (of length T) is maximized. In our specific application of self-calibration as discussed in Section 3.10.2, it is required to adjust the observation probability matrix B while keeping the other two parameters A and it in A constant. The Baum-Welch algorithm [83] is used in our implementation to iteratively obtain an estimate of B that results in a A which is guaranteed to locally maximize P(0|A). As defined in Section 3.9.1, the element b,-_,,, in the matrix B represents the probability that in posture state j, the elements cm, x,,,, rm and km in the observation vector 0 are ‘ l 's’ and the rest of the elements are all zero. The quantity by" can be computed as: T 27:0) b S1. of =Vm jam T 273(1) t=1 (3.11) where the denominator represents the probability that the system is always in state j with all possible observations. The nmnerator represents the probability that the system is in 47 state j with a specific observation such that the elements vm, where v,,, = {cm x,,,, r,,,, km} in the observation vector 0 are ‘ l 's’ and the rest of the elements are all zero. Using Eqn. 3.11 as the iterative step for changing the B matrix, we have implemented the following algorithm for implementing self-calibration as explained in Section 3.9.2. 1) Collect observations 0 = 0102...0T 2) Initialize A using a starting B matrix with constant A and 7t 3) Given observation sequence 0 = 0102...OT and A, compute: y,(j), VIStST, ISjSN 4) Compute new B matrix by updating the elements bj,m based on Eqn. 3.11 5) Set new knew using the new B matrix 6) Compute a new quantity MAXLIKELIHOOD as: MAX LIKELIHOOD = max[P(01...0T Ir), 10(01 ...0T WM] 7) 7»: Knew 8) Go to step-3 and repeat till the quantity MAXLIKELIHOOD converges Log Likelihood 1 3 5 7 91113151719 Number of iterations of the Baum-Welch algorithm Figure 3.9: Performance of Baum-Welch iterative algorithm 48 The fact that the newly estimated B matrix in Step 4 is computed based on the actual observation sequence, ensures that the estimation would improve the quantity P(0|/l). This accounts for the monotonically increasing nature of the MAXLIKELIHOOD, as evidenced in Figure 3.9, which demonstrates the convergence performance of the Baum-Welch algorithm in terms of the evolution of the log of the quantity MAXLIKELIHOOD. Observe that with all three different initial B matrices, the MAXLIKELIHOOD monotonically increases over the algorithm iterations, and converges approximately after 12 iterations, which is consistent with what has been reported in Figure 3.8. 49 Chapter 4. Transmission Power Assignment with Postural Position Inference In this chapter we address the issue of energy-aware on—body communication by developing a posture-aware transmission power control framework. An on-body link’s postural position can be highly dynamic due to the unpredictable RF attenuation caused by a slew of factors including subject’s clothing, antenna orientation, and physical stature of specific subject individuals. In real-time data exchange across various on-body-sensors with point-to-point or multi-point-to-point data transaction, the optimal transmission power depends on the physical distance of the link, and its instantaneous channel condition. As a result, static pre-defined transmission power is not able to provide continuous link connectivity while ensuring minimum required transmission power consumption. In this chapter we propose a dynamic link power assignment mechanism for optimal energy management in on-body links data exchange. 4.1 Related Work The energy conservation mechanisms in [2],[14],[44] attempt to develop synchronized sleep scheduling across on-body sensors so that the overall energy consumption is controlled by the communication duty cycle. These mechanisms do not control the transmission power of individual on-body links as done in this chapter. Transmission power control can be executed simultaneously with node sleep scheduling as a complementary energy-saving strategy. Several RF Transmission Power Control (TPC) papers [88-90] in the literature use node localization for computing link distance, which is subsequently used for power assignment using known models of RF signal attenuation with distance. Performing 50 localization for on-body sensors can be complex due to high node mobility triggered by human posture changes, and energy expensive due to the need for localization infiastructure such as ultrasound to perform Time Delay of Arrival (TDOA) [91] computation. Such difficulties to run localization for on-body sensors make localization oriented TPC protocols unusable for body area networks. The protocol ATPC in [62] proposes a non-localization—based mechanism in which a closed loop control is executed based on the received signal strength measurement. Experimental evaluation of ATPC that has been reported in [62] includes large static wireless networks deployed in terrains such as parking lots and in-building corridors. Although ATPC is the closest to the approach adopted in this thesis, the primary hurdle for mapping ATPC on body area wireless links stems from the fact that the on-body wireless link characteristics are significantly more dynamic due to human postural mobility, antenna orientation, clothing, and the physical stature of specific subject individuals. Additionally, this protocol does not consider the control overhead associated with closed loop power control mechanism as an algorithmic cost, which can be very large when applied to on—body links with fi'equently varying link qualities. As a result, the ATPC protocol, which was designed and tested only for relatively static and long-distance wireless links, does not apply for highly dynamic on-body links. Power control mechanisms for links between on-body sensors and off-body static sinks are explored in [64]. Although the RF link characteristics in this setting are closer to that of on-body links than those in [62], they do not quite represent the wide variations in link qualities when both nodes of a link are on-body. Also, the assumption of unlimited energy availability at the off-body sink node, as adopted in this chapter and in [2], 51 influences the TPC algorithm and energy accounting in ways that are not suitable for severely energy-constrained and completely on-body links as targeted in this chapter. The power control mechanisms for IEEE 802.11 MAC protocol in [92—95] implement closed loop control with RTS and CTS packets carrying the feedback control information. Full power RTS/CTS and controlled power data transmissions are sent through separate channels [93],[94], and the transmission power is incremented and decremented stepwise till a desired power level is achieved. These mechanisms, adapted specifically for 802.11 networks, are not directly portable to the on-body systems for the following reason. For a non-802.11 MAC layer, since there are no RTS/CTS packets, separate feedback control packets will be necessary. Since the cost of implementing power control is of paramount importance for on-body links, the objective will be to minimize the usage of such control packets while maximizing the overall energy efficiency through effective power control. This is not an issue for the mechanisms in [92-95], since fi'ee RTS/CTS control packets are available in 802.11 on a per data packet basis. Transmission power control has also been studied extensively in the context of cellular networks. In [96-98], closed loop transmission power control for Code-Division Multiple-Access (CDMA) systems are proposed, where a separate feedback channel with universal frequency for control data is used. The lack of a separate feedback channel in an on-body network makes such cellular network power control mechanisms unsuitable. The lack of a feedback channel poses the same problems imposed due to the lack of per data packet RTS/CTS control as discussed above. Additionally, the time constant for power control in the cellular networks are much larger than what is needed in the 52 on-body scenarios — causing those closed loop mechanisms in [96-98] to be too slow in the presence of high postural mobility. 4.2 Dynamic Transmission Power Assignments The objective of this chapter is to develop a closed loop power assignment fi'amework that deals with solely on-body links with a wide range of link quality variations due to the body specific factors as outlined above. Three different dynamic on-body links transmission power assigrment mechanisms are proposed, namely, Linear, Binary and Dynamic Postural Position Inference (DPPI). The DPPI proposed mechanism has been experimentally evaluated and compared with the binary search and the traditional fixed power increment/decrement strategy (termed as linear search), which has been used in many closed loop mechanisms in the literature [64],[96],[92-95],[97],[98]. The proposed mechanisms are distinct in that unlike majority of the transmission power control mechanisms in literature [44],[14], it does not rely on the availability of location information for individual sensor nodes, and uses a novel technique of postural position inference which is specific and can be applied to body area wireless networks. 4.3 Characterization of On-Body RF Links This section presents an experimental characterization of on-body wireless links and 3 its quality variations with different transmission power, postural positions, and subject individuals. 4.3.1 Experimental Settings We construct a Body Area Network by mounting a set of sensor nodes on different segments of the body (e.g. thigh, upper arm, ankle, waist etc), as illustrated in the 53 prototype system in Chapter 2 and Figure 2.1. In this prototype, the CC1000 chip in MICA2DOT mote offers a hardware register to specify the transmission power at one of 22 different power levels, corresponding to a range [75] between 21.5mW and 63.5mW. These power levels are represented as indexes 1 through 22. The sensors are worn with elastic bands in such a manner that the sensor and its antenna orientation with respect to the mounted body segnent do not change with frequent posture changes. The sensors can form a mesh or a star topology depending on point-to-point or multi-point—to-point data requirements in specific applications. Since the scope of this chapter is primarily at the link level, the topological configurations are of very little or no interest. From this point onwards, the links referred to in this chapter belong to a star topology. All body-mounted sensors in this topology send data to another body-mounted sink node. This node collects raw data, and sends processed results or events to an off-body server using a wireless link. This external link is created between the on-body sink node and to an off-body Mica2Dot radio node connected to a Windows PC (compute server) through a custom-built serial interface running RS232 protocol, as shown in Chapter 2 and Figure 2.1. 4.3.2 Target link and Posture Sequence An on-body wireless link between a sensor node on the upper arm and a sink node at the waist has been used for studying link quality variations. Since hand is considered to be the most mobile part of the human body, the arm-mounted sensor has been chosen specifically to demonstrate the impacts of postural mobility on link quality variations, and the subsequent need for adaptive transmission power assiglments. Link quality is characterized by observing the Received Sigral Strength Indication (RSSI) values at the sink node for a given static transmission power from the 54 arm-mounted sensor node. The variation of RSSI represents the changes in link quality as a result of body movements, RF attenuation by subject’s clothing and body segments, RF multi-paths, and other changes in the surroundings. On-body Link x E WirsleSS/Ifilk‘xli Out-of-Body Server Figure 4.1: On-body sensor positions and the used posture sequence Three different subjects, one female and two males, were asked to follow a sequence of right hand movements corresponding to four different sitting positions as shown in Figure 4.1. These hand positions represent natural sitting postures, and also indicate scenarios with varying degee of RF attenuation due to siglal blockage and sensor node movements. For each subject, each posture in the sequence lasts for approximately 10 seconds, and the entire sequence is repeated three times resulting in a total experimental duration of 120 seconds. 4.3.3 Transmission Power Levels For each posture in the above sequence, link characterization is also carried out with different transmission powers. We have reported the results with four different power levels 7, 13, 18 and 22, corresponding to actual transmission powers of 24.8, 34.5, 43, and 63.5 mW respectively. The rationale for reporting only these power levels is as 55 follows. Level 22, the maximum available power, provides the best packet delivery, but the worst transmission energy usage. Level 7, the available minimum, delivers the worst packet delivery, although with very little energy usage. Power level 18 turns out to be the minimum power level that provides around 100% packet delivery. Finally, level 13 is reported, because it is somewhere in the middle of power levels 7 and 18, and provides a reasonable balance between transmission energy consumption and packet delivery. Sensor on the arm transmits four packets, one at each of the above power levels, every one second interval. The sink node located at the subject’s waist region measures the packets’ Received Sigral Strength Indicator (RSSI) and sends the data to the off-body server (see Chapter 2 and Figure 4.1) for analysis and post-processing. Note that these bundled transmissions of four packets together ensure that the RS SI corresponding to all four transmission power levels are captured with the exact same posture along with the clothing and any other on-body artifacts influencing the RF sigral attenuations. 4.3.4 Multi-scale Variations of Link Quality The variation of RSSI (in dBm) [75] at the sink node is shown in Figure 4.2. For the sake of clarity, the RSSI values are shown only for the power levels indices 7, 13 and 22 (24.8mW, 34.5mW and 63.5mW, respectively). These three power levels have been chosen based on experiments as explained later in this section. The time axes on the gaphs in Figure 4.2 are divided into postural position slots of width 10 seconds. The slots are then marked by the posture sequence numbers from 1 through 4 (see Figure 4.1), which repeats for three cycles. 56 5 v75 \ : fish 5280 ’r-J “-85 — . ,. ’4‘."- ..I" .0“; I . '"kno “H'WQ‘RRVUIK/I ‘. a yr LIV”, [ha/"If '90 Sub-3 ’ PI-7 /' " ' i ‘\ x _ ~95 ' 10 20 30 40 50 60 70 8O 90 100110120. Time(s) Figure 4.2: Link quality variations with varying postural positions The following observations can be made from Figure 4.2. First, as expected, the link quality does depend on the transmission power. Second, the RSSI values change quite significantly with postural positions. For example, the link on Subject-2 with power level index 13, the maximum sigral strength is -77 dBm in posture 2 of cycle 3, while the 57 minimum sigral strength is -93 dBm in posture l of cycle 3. That represents a peak—to-peak swing of 16 dBm. Third, there are distinct differences in the link qualities across the subjects, even with the same transmission power and at the same posture. For example, using power index 22, the average RSSI for Subject-1’s link is -66 dBm during posture 4 of cycle 3, whereas for Subject-3, the RSSI during the same posture with the same power level is -74 dBm. Finally, even for the same subject, with the same transmission power level, the RSSI can be different for the same postures across different cycles. For example, the RSSI values for Subject-2 during posture 1 are siglificantly different between cycle-1 and cycle-3. To summarize, the experimental results in Figure 4.2 demonstrate that on-body RF links can vary not only with postures, subject individuals, and transmission powers, but also with time even when all the above factors are fixed. -60 l l l l l l I l l l I Position-4\ I . l ; A'70“ L' I"II!!. 8 , Posrtlon-l . I I ' ' g I 9 , e ’ ll ' l - l :7 '80 7 3 I | I Position-2 ' l m : I ' | '/ I Z" w l l ' I I l I l l I , I '901 l I l = ' ' I i l l » - l l i Position-3. -100 A ’ ‘ i 2 4 6 8 10 l2 l4 l6 18 20 22 Transmlssion Power Index Figure 4.3: Impacts of transmission power at different postures Figure 4.3 demonstrates the impacts of transmission power on the RSSI for the four postural positions shown in Figure 4.1. While a subject remains in each of those 58 positions, the transmission power from the sensor on the upper arm is changed across the entire available range from level 1 to level 22 (21.5mW to 63.5mW) and the corresponding RSSI values are noted. At each power level, 20 packets are sent to the sink which collects RSSI data points for the successfully received packets. The results obtained demonstrate the spread of RSSI in Figure 4.3 for a given position and at a given power level. This spread of RSSI indicates that even within a given posture, there are some intra-posture body movements that affect the on-body RF link qualities. The results in Figure 4.3 also demonstrate that the minimum power required for a successful link creation can vary depending on the postural positions. For example, while in position 4, the link starts delivering packets with power level index of 1, in position 3, the link starts delivering packets only at a power level index of 8. The final observation from Figure 4.3 is that for a given postural position, the average RSSI values can be modeled approximately as a linear function (also reported in [62],[99-101]) of the transmission power index, although the slope across different positions can vary. This experimental observation is the key for our proposed power assigrment mechanism based on postural position inference as presented in Section 4.5.5. 1.2 . , Posrtlon-4 _ g 0.8 — \ Ratio .2. \ ‘ '76 0-6 l Position—2 . . $3 0.4 _ Posrtlon-3 g 0.2 ‘ Position-1 Q 0 I I I I I I f I I I I 0 2 4 6 810121416182022 Powerlndex Figure 4.4: Impacts of transmission power on packet loss 59 Packet losses are recorded from the same experiment corresponding to Figure 4.3, and are reported in Figure 4.4. This shows that the required transmission power level to achieve a minimum packet delivery ratio varies across different postural positions. This implies that for an application with certain amount of packet loss tolerance, the optimal transmission power can vary depending on the instantaneous posture of a subject. Therefore, an adaptive transmit power assiglment mechanism is highly desirable for such on-body links as discussed in this chapter. 4.3.5 Impacts of On-body Parameters on Link Quality The following experiment was carried out for understanding the impacts of on-body factors in addition to just the distance between the nodes on a link. Sensor orientation and on-body postural obstructions for a link between the upper arm and waist sensors have been targeted as such factors to be understood. Figure 4.5: Variation of sensor orientations and on-body obstructions As shown in Figure 4.5, four different combinations of the orientation and on-body obstructions for the link have been experimented with. Orientation of a sensor was defined by the direction of its antenna alignment, and is indicated by the arrows marked next to the sensors. The sensor in the picture is too small to clearly show its orientation. For all four scenarios, while the orientation of the waist sensor was kept constant, the 60 relative orientation was changed by rotating that of the arm sensor. On-body obstruction of the link has been modulated by having the subject put his hands on his chest. -50 l W I I U T n . . . r r Orlentatlon-l -60 a. . . Orientation-2 with Obstruction 0 . A Orientation-1 No Obstruction . . t . l S _70 _ No Obstruction . 0 ' . . . I % . . 0 ‘ fl ‘ I | V . I l—« . 0 ‘ . 3 3 I I I U) -80 c 0 A i I I m t l I I I I ‘34 ' ' l l I l l 90 - I l l I l ' ' I I - ’ i I | I I I I Orientation-2 , i . I I I I I l with Obstruction -100 0 2 4 6 8 _10 12 l4 16 18 20 22 Transmrssron Power Index Figure 4.6: Impacts of sensor orientation and on-body obstructions The photos in Figure 4.5 demonstrate four different link conditions in terms of the sensor orientation and obstructions, but for all four, the distance between the sensors was maintained constant. This control made sure that any link quality variations across the four scenarios are contributed solely by the changes in orientation and/or obstructions, and not due to a distance change. Figure 4.6 presents the RSSI values for different power levels for the experimental scenarios in Figure 4.5. These results clearly demonstrate that even when the link distance remains constant, various secondary postural influences such as sensor orientation and on-body obstructions can affect the link quality as much as the distance and postural positions do. This conclusion is evident when the amount of RSSI variations in Figure 4.6 is compared with those in Figure 4.3. 61 Figure 4.7: Orientations of a lower-body link with different postures 4.3.6 Validating Linearity of RSSI for Other Postures To establish the linearity of RSSI vs. transmission power relationship (as observed for the upper-body link in Figure 4.1) in other parts of the body, we conducted several experiments on links in different parts of a subject’s body. Figure 4.7 shows such an experimental setup in which a lower-body link between an ankle sensor and a waist sensor has been characterized. '60 I l l l | T l l l l . Position-8 (I I I I -70-i \ x I E i I I I E a Position-7 g 5; I I I I _ I I . g 5 x ' I I I I I I v ~80 _ . x X I E I I I I a f x A I a g i 3 I l l . I I i * i I I ‘ | I Position-5 -90 ~ 1 I . l I I I I I I I I I Position-6 -100 ‘ L 0 2 4 6 8 10 121416 18 20 22 Transmission Power Index Figure 4.8: RSSI characteristics power for a lower-body link 62 The RSSI and transmission power characteristics for this link with four postures, as indicated in Figure 4.7, are shown in Figure 4.8. It is evident that the linearity of RSSI as observed in Figure 4.3 extends very well for the postures in Figure 4.7. Results from the links in other parts of body also demonstrated similar linearity relationship. 4.4 Fixed Power Assignments Each on-body sensor under this design is assigned a static transmit power level for sending data to the sink node. This power needs to be high enough to achieve a desired packet delivery rate (see Figure 4.4), while it should be low enough for conserving energy of the resource-constrained on-body and implanted sensors. Based on the multi-scale link quality variations as observed in Section 4.3, identifying a power level that can work in a posture, clothing, and person independent manner can be a challenging problem. 4.4.1 Relevant Performance Metrics The performance of transmission power assignment will be evaluated using two primary metrics, namely, Packet Delivery ratio (PDR) and Energy per Packet (EPP). The target is to maximize PDR and minimize EPP. PDR is defined as the fraction of packets sent by an on-body sensor that are delivered to the sink node. The quantity EPP is computed by dividing the total communication energy, both for transmission and reception, spent by the on-body sensors (including the sink) by the number of successfully delivered data packets. Note that the numerator includes communication energy costs for data as well as any control packets. Although not used for the static scheme, such control packets are used extensively for the closed loop systems as described in Section 4.5.1. Note that the EPP metric represents a combined measure of 63 both energy consumption and packet drops. Using EPP, it will be possible to differentiate between two power assignment strategies for which the total energy consumption may be the same but one delivers more packets than the other. A number of secondary metrics, namely, transmission energy, reception energy, and control overhead, will be also used. The transmission energy cost for a packet is computed as: E tx = V ' Itx ' S / C , where V, Itx, S, and C represent the supply voltage, current drawn, packet size, and channel capacity respectively. For the results in this and in the next section, we have used Vto be 2.5V, and It, to be 9.9mA, 13.8mA and 25.4mA for power levels 7, 13 and 22 respectively. The data and control packet sizes are 45 and 22 bytes, and the channel rate is 38.4kbps. All these figures correspond to the MicaZMote hardware [75] including the CC1000 radio chip. The reception costs are computed using the same formula by replacing the parameter I“, by the receive current I m which is set to be 8mA [75] for the CC1000 chip. 4.4.2 Fixed Power Assignment Results The PDR and EPP results are captured for the fixed power assignment at power levels 7 (24.8mW), 13 (34.5mW) and 22 (63.5mW) with the posture sequence as described in Section 4.3.2. The experiments were carried out on the same three subject individuals as in Section 4.3. Figure 4.9 and Figure 4.10 show the moving average of PDR and EPP within a sliding window of 10 seconds. Note that like in Figure 4.2, the time axis is divided into postural position slots of width 10 seconds. The slots are then marked by the posture sequence numbers from 1 through 4 (see Figure 4.1), which repeats for three cycles. 64 l.l 1 341,234jlv233;4 2 ' . 0 9- Lied . \..\_LJ ' / / ; “303 ‘ PI-13 PI-22 ‘x ch0.7 ~ » \ i 0.6 ‘ Av. for PI-7= 84% Av. for PI-13=96% 0'5 ‘ Av. for PI—22=99% Sub-1 0.4 . e r a i . 1.1 1 1 j 2 1 5 ‘x 0.9 — . , , “”~. 5”“ \ n: 0.8 — i ' W“ i E o 7 1 V i‘“ Y ;_ l ' , f “.‘mm; PI-7 0—6 ‘ Av. for Pl-7=81% 0.5 - Av. for PI-13=93% Sub-2 Av. for PI-22=99% 0.4 I I l l 1.1 1 z 0.9 “ M03 ‘ PI-22 a -7 i E,“ “0.7 ‘ \ 0-6 ‘ Av. for PI-7= 79% f Sub-3 0.5 ~ Av. for PI-13=83% Km“? - Av. for PI-22=97% * 0.4 I l I I I I I I l I l ‘ 10 20 30 40 50 60 7O 80 90 100 110 120 Time (3L PI Figure 4.9: PDR performance with fixed power assignment 65 1.8 1 2 . 3 4 1 2 . 3 4 1 2 3 4 1.6 4 M - l j l ' E 1-4 ‘ i \ Sub-1 .—. PI—13,Av.: 1.05 mJ/pkt : , PI-22. Av.: 1.54 mJ/pkt 31.2 — . ; ”M; I”... E 1 ~ ' Lu , XI 0‘ ’ k / 0_8 ‘“ “wu4mtq...«.w'”W»~»>uu«..~~ulM“*”Jl i...” '1’, J Pl-7, Av.: 0.90 mJ/pkt 0,6 I I I l | I I I I I I 1.8 A 1.6 ‘ M / I /\ ”I 32 1 4 _ . E - PI—13,Av.: 1.09 mJ/pkt PI—22,Av.:1.57mJ/pkt Sub-2 $ 1 Hf—iu ,9" W?— 0.8 H °"""’""“u«unm;l tuna” . Ewen/f ‘N'IMQH-N_w”'u'l him \ PI-7, Av.: 0.92 mJ/pkt 0_6 I I I I I I F I I 7 ‘17 1.8 Sub-3 1.6 _W g 1.4 - PI-13,Av.:1.05 mJ/pkt PI-22,Av.: 1.54 mJ/pkt H . 51.2 — Q-r Q4 1 _ 0.8 - .. «4* mum“... ’V \ PI-7, Av.: 0.90 mJ/pkt 0,6 l I I I I I I I I I I 10 20 30 40 50 _60 70 80 90 100 110 120 Tlme (s) The following observations are to be made. First, as expected, increasing Figure 4.10: EPP performance with fixed power assignment transmission power causes larger EPP while providing better communication quality through higher PDR. Second, since packet drops inflate EPP, every time there is a 66 , HM» an m "Ami 0 8 " We’WW‘rwuu-‘M in“... vies-- ‘m u’ 1.8 ‘ 7 l 2 3 4 1 2 : 3 4 1 2 3 4 1.6—W §I.4~ ’ i \- Sub-1 312 PI—l3,Av.:1.05 mJ/pkt .PI-22,Av.:1.54nu/pkt ' H 1 9 . - We WW": On Q 1 PI—7, Av.: 0.90 mI/pkt I I 0.6 1 . . I 1 ; 1 I . 1.8 A 1.6 - p... /“‘““\ /\‘1 ‘ 5 1-4 * PI-l3 AV'109mJ/pkt PI—22 Av-157mJ/ kt a , .. . , .. i; p Sub-2 D-u E 1 — . firm—:- 0 8 )‘H‘*‘{ I (lfiub‘ “/r ‘5‘ ' “WI\PI 7, Av.: 0 92 mJ/pkt 0.6 I I I I I T I 1.8 Sub-3 LNW \ 1.4 - PI—13,Av.:1.05 mJ/pkt EPP (mJ/Pkt) ... E; PI—22, Av.: 1.54 mJ/pkt 0.8 H 43"."‘W'5'Nm’nw/fi i 94* ‘ ecu am a k I; \PI-7 Av.: 0 90 mJ/pkt um!“ 0.6 I 10 20 30 40 50 .60 70 80 90 T1me (s) 100 110120 Figure 4.10: EPP performance with fixed power assignment The following observations are to be made. First, as expected, increasing transmission power causes larger EPP while providing better communication quality through higher PDR. Second, since packet drops inflate EPP, every time there is a 66 down-spike in the PDR, there is a corresponding up-spike in the EPP results. Third, while low power levels (e.g. 7 and 13) may be sufficient for 100% PDR for most of the times, there are occasions during which the packet drops due to body movements can be unacceptable, and therefore a higher power level, causing larger EPP, needs to be adopted. Hence a dynamic power assignment is needed for achieving both high PDRs and low EPPs. As can be seen in the figures, the wide variations of PDR and EPP across different subjects further reinforce this requirement for dynamic power assignments. r________________'l‘_r_ansmitter Node _ . ______ Receiver Node (Sink/Control) Data Packet 1 Measure Packet : Transmission z Receiver RSSI value at Current Power Level i E E I Data Generator g Current Th): Power 3 Level i 5 >~ E : : 5 '8 i : 5 Update = —<.= E New (RTLMH): Transmission 5 Power Level 4—— : | Power Level Computation I , E Control Packet JNew Power Receiver "5' """"" "5"" Transmission Level I ‘ at Full Power Figure 4.1 1: Closed loop power assignment model 4.5 Dynamic On-Body Power Assignments 4.5.1 Closed Loop Control A closed loop mechanism, as shown in Figure 4.11, is adopted for implementing dynamic on-body power assignments. Based on specific application requirements, data 67 packets are periodically sent from an on-body sensor node to a receiver sink node, which is also referred to as the control node in the diagram. Each packet is marked with a monotonically increasing sequence number and the transmit power level information. Upon receiving a data packet, the control node first decides if the corresponding RSSI falls within a pre-defined threshold range (between RTL and RT”) in which case the currently used transmit power level is considered optimal. If, however, the RSSI falls outside the threshold range, it is perceived that the transmit power level is too high or too low. In this case, the control node computes a target transmission power level that should result in an RSSI within the threshold range. Once computed, this power level is sent back to the transmitter node using a separate control packet with the maximum possible transmission power. Upon receiving such a control packet, the transmitter node updates its transmission power and continues packet transmissions at this new power level until a new control packet, instructing a different power level, is received. If and when the control node infers a packet loss (by observing unusual delay in packet reception or gaps in packet sequences) caused by abrupt link quality deterioration due to postural position changes, the control node assumes that the current power level being used by the transmitter is insufficient. It sends a control packet to the transmitter to increase the power level to a value between its current and the maximum possible value. This process is repeated till the control node starts receiving packets, and then the RSSI-based control operation as described above resumes. Note that all the available power levels (1 through 22) are made available during the above iterative assignment process. 68 4.5.2 Choice of RSSI Thresholds The RSSI threshold range (RT 1, RT H) is determined based on the packet delivery rate (PDR) variation as a function of the received RSSI values. To characterize the RSSI vs. PDR performance, we have conducted an experiment in which while keeping the transmission power constant, a link’s distance is changed by shifting the receiver’s position with respect to the transmitter node. At each position, 500 packets are sent, and the receiver records the RSSI for all the received packets and the number of packets dropped. From this data, the average RSSI and the corresponding PDR values are computed and reported in Figure 4.12. 1.2 1 . RTLL. , RTHL - e- ‘rt: 1* * ' i ' 0-8 . : Threshold : d E 0.6 ' L ”‘33 J. _ a... 1 l‘ ; 'I 0.4 I I - I I 0.2 _ I . : . ‘ - O i i i 1 i T' i i 1 -100 -95 -9O -85 -80 -75 -7O -65 -6O RSSI(dBm) Figure 4.12: RSSI threshold range for acceptable packet delivery rate As shown in Figure 4.12, the smallest RSSI that corresponds to near perfect delivery performance is approximately -88 dBm, which is chosen to be the lower threshold RTL. The upper threshold RTH is chosen to be -82 dBm for which the dynamic power assignments, as described in Section 4.6, deliver the best possible energy performance. More details about the choice of RT" are presented in Section 4.6.2.6. 69 The primary reason for choosing a target RSSI threshold range, as opposed to a single target RSSI value, is to minimize the frequency of corrective control actions and its associated energy and capacity overhead. Also, given the 22 discrete power levels for the Mica2Dot hardware, for a given state of an on-body link, a specific power level at the transmitter may not be able to produce an exact RSSI value at the receiver. 4.5.3 Target Power Computation by Linear Search In this approach, the sink/control node computes a new desirable transmission power level for the transmitter node by linearly incrementing or decrementing the current power level based on the received RSSI values with respect to the threshold range (RTL, RT”). No changes are needed when the RSSI falls within the range. The closed-loop control logic in Figure 4.11 ensures that, for a given postural position, this process eventually achieves a desirable transmission power level for a link so that the RSSI at the sink falls within the preset threshold range. The step size for power changes can be chosen based on the necessary responsiveness. This linear search-based approach is expected to work well with small incremental changes in link quality during intra-posture body movements such as moving the hand slightly while being in any of the positions in Figure 4.1. The linear power level search during such incremental changes can quickly find a new desirable power level without having to incur excessive control overhead in terms of control packets from the sink to the source sensor node. However, for inter-posture body movements, such as when a subject transitions across the positions in Figure 4.1, this linear approach can be slow and control expensive due to the large amount of corrective changes needed in the transmission power level. 70 4.5.4 Computation by Binary Search Better responsiveness and lighter control for inter-posture body movements can be achieved via a binary search. In this approach, if the RSSI at sink is lower than the threshold RTL then the next power level is chosen to be right at the mid-point between the current and the maximum possible power levels. Similarly, when RSSI is above RTH, the next level is computed as the mid-point between the current and the minimum possible power levels. As in the linear case, the closed-loop control logic ensures that the transmission power eventually converges to a desirable level for the RSSI at sink to be within the present threshold range. While providing a lighter control solution for inter-posture movements, the binary search can be slow and expensive for intra-posture scenarios, in which the transmission power level has to go back and forth over a wider range even for small incremental change of the link quality. In other words, for small changes in the link quality, this search mechanism is likely to overreact and thus takes many steps to converge within the RSSI threshold range, leading to oscillations and sluggishness. This mechanism suits well for adults who generally remain relatively still within a posture, but can be expensive for children for whom generally the intra-posture instabilities are intrinsic. To summarize, although both linear and binary search mechanisms ensure eventual convergence to the optimal transmission power level, they are control-expensive and slow to react for inter-posture and intra-posture body movements respectively. Sluggish convergence can cost either low PDRs or high EPPs. Transient RSSI levels above RTH may cause high EPPs while providing perfect PDR. Whereas, RSSI values below RTL may deliver excellent EPP performance while dropping a large number of packets. 71 Additionally, a slow convergence leads to large number of control packets from the sink to transmitter, causing the energy per packet numbers to be even higher. 4.5.5 Control with Dynamic Postural Position Inference The fundamental limitation of the above two mechanisms stems from the fact that no knowledge about on-body link quality variation is leveraged during the power assignments. Without such information, the mechanisms amount to blind searches for a transmission power that can result in a desirable RSSI. In Dynamic Postural Position Inference (DPPI), the knowledge of on-body link characteristics is used for inferring a subject’s current postural position for assigning the best possible power level to a link. The DPPI mechanism is explained in Figure 4.13. Possible New Posture Position: b 1 ,” Current Posture I RSSI ,’ Position: b B..«' I I G ,I’Possible New I osture Position: b2 I I I 1 1 l 1 iP’ a Power Level Index Figure 4.13: Posture-driven DPPI for dynamic power assignments Based on the observed linear relationship between the transmission power and RSSI in Figure 4.3, we can express: 72 Ri(b)=s(b)°Pi +c(b), (4.1) where Ri(b) is the RSSI at the sink for a transmission power level P,- (i = I, 2, 22) and for a body postural position represented as b. The parameters s(b) and C(b) represent the slopes and intercept of the straight line. The dependency of these parameters on the current postural position is evident from the characterization graphs in Figure 4.3. The solid straight line in Figure 4.13 represents a postural position b and a stable power assignment P,- for which the RSSI value is shown to be within the target threshold range. Now assume that for the same transmission power level, due a body position change, the RSSI has changed to a value higher than threshold RT H. In this case, the dotted straight line above the solid line represents a possible new position b]. The goal is to infer this new postural position in terms of the slope and the intercept for the corresponding straight line. Once the equation of the straight line for this new position is found, a desired transmission power level can be computed by targeting the threshold mid-point RT to be the desired RSSI. At the current power level P,», when the postural position changes to b1, the new RSSI value can be written as: Ri(bl)=5(bl)°Pi +c(b1). (42) Upon observing this new RSSI value is higher than the threshold RT H, the sink (control) node initiate a position inference process by sending a control packet to the transmitter to send packets at a lower power level Pj. At the sink, this new power level produces RSSI: 73 Rj(bl)=5(b1)'Pj+c(b1)- (4.3) Eqns. 4.2 and 4.3 can now be solved for the slope as: 5(b1)=[Ri(b1)"Rj(bl)]/(Pi - Pj), and for the intercept as: C(b1)=[Pi 'Rj(bl)_Pj 'Ri(b1)l/(Pi — Pj), These two parameters represent the subject’s current position b 1, which can now be used for computing a desirable transmission power as: {RT eig- -R,-—P,- «twin/(P. —P,-)} IR.(bt)—R,-< E 16.3 53 a r: 12 is V’ B 32 8 s3 4 0 24 Power Index -60 — ‘" 20 A _ 16 X :7 ‘ + 12 is g -80 q R ‘w I“ WA _ 8 E “41141.11 1.1 m in 1 .. -90 — u! I . Ir' / \1 + 4 Thr. ange L‘nea' RSSI — 0 10 20 30 40 50 60 70 80 90100110120130140150160 Time (s) 77 Figure 4.16: Continued -50 1 1 W I W r I f F 1 f 1 1 T r 24 -60 — Power Index _- 20 A K 5 -70 r 1 ‘L 16% v SI I I f" “11" 1225‘ I-I . 1' ‘I ‘ H I I o g -80 .-. ....... .I ........... * I ................... ‘ 5 g .I I III I I i“ .... I with .16", I" 8 g, -90 - " f . 400 Thr. Range -50 t I I -60 _ Power Index ”a? g -70 ‘ g -80.. r 94 _90 .2 ............. -100 ’50 I I I I I I I l I I r 1 1 I 24 Benchmark ' -60 - M I 20 A Power Index - .. , 5 a ._ 16:: Q '70 ‘ \F.“ a L“ * III I 11 "12% w -80 - , o 3 LJ r 8 an -90 _ Thr L3,, RSSK T 4 -100 ° 58 0 10 20 3O 40 50 6O 7O 80 90100110120130140150160 Time (s) 78 4.6.2.1 Transmit Power and RSSI Dynamics Figure 4.15 demonstrates the evolution of assigned power levels and the resulting RSSI for two fixed assignment (power indexes 22 and 13) and three dynamic assignment (Linear, Binary and DPPI) mechanisms. A best case scenario, termed as the Benchmark, is also defined for each control cycle (see Figure 4.14). The benchmark results are constructed by selecting the lowest possible transmit power from all seven implemented mechanisms, for which a packet was delivered to the sink. This is computed offline and provides an experimental performance upper bound to compare DPPI’s performance with. The following observations should be made from Figure 4.15. First, with fixed high power (e. g. PI=22) assignments, the RSSI at the sink is mostly above the higher threshold RTH, which is expected to provide excellent packet delivery rate (PDR), but at the expense of high Energy Per Packet (EPP). With fixed low power (e. g. Pl=13) assignments, more often the RSSI remains within the desirable threshold range, causing the EPP performance to be better. But as shown in Figure 4.15, packet losses during link-obstructive postures can affect the PDR performance. These can be validated in the time averaged results presented in Table 4.1. Power Av. Av. EPP Tx Energy Rx Energy Assignment lPDR (mJ/pkt) (mJ) (mJ) Index-13 83% 1.37 118 39 Index-22 99% 1.59 203 43 Linear 92% 1.32 132 52 Binary 94% 1.09 1 16 49 DPPI 98% 0.95 103 46 Benchmark 99% 0.87 94 43 Table 4.1: Performance summary of different power assignments Second, all three dynamic assignment mechanisms manage to maintain the RSSI values within the threshold range longer, indicating a better balance between PDR and 79 EPP. Also, given that the subject’s movements were mostly inter-posture as opposed to intra-posture, the binary search worked better than its linear counterpart. However, for binary, the oscillation (see Section 4.5.4 for explanation) of the transmission power level and the subsequent departures of RSSI out of the target threshold range are quite evident in several instances including those during the time frames 105-205 and 1103-1303. The DPPI mechanism performs the best by avoiding this oscillation problem via its postural position inference-based assignment as described in Section 4.5.5. Finally, since the benchmark corresponds to the minimum transmission power level for a successfully delivered packet across all seven experimented assignments, it’s RS SI values are always the lowest and often dwell below the lower threshold R TL. 4.6.2.2 Packet Delivery Ratio (PDR) Figure 4.17 shows the moving average of PDRs, for the DPPI and binary assignments, computed using an averaging sliding window of 10 seconds. As shown in Table 4.1, these two assignments have the best two PDRs among the dynamic mechanisms. Observe that there are several time durations (e. g. lOs-20s) when the binary mechanism loses packets, whereas the DPPI is able to deliver them. A closer look to the RSSI values in Figure 4.15 for that time duration reveals that the binary assignment was dropping packets due to an oscillation in the assigned power level and the subsequent RSSI values beyond the desired threshold range. The oscillation started soon after a body position change by the subject at around 10 seconds time mark. Departures below the lower RSSI threshold during such oscillations resulted in packet dr0ps. 80 1.1 f g 3 1 , é ; 0.9 _ R ,‘ U \I-n-JI I U a: 0.8 - / i I I DPPI ‘ . ’ E 0.7 — ¥ Binary: 0.6 - i * ‘ 0.5 — 0.4 I I I I I I r I I T j I I I I o 10 20 30 40 so 60 7o 80 9o 100110120130140150160 Time (s) Figure 4.17 : PDRs for DPPI and binary search-assignments For DPPI, however, packets are not dropped because the RSSI values in those time durations are well within the threshold range. This was accomplished by a quick inference of the new position (i.e. the correct straight line in Figure 4.13) soon after the subject’s posture change, and then by adjusting the new power values based on the inferred postural position. As shown in Table 4.1, the resulting PDR is a very high and close to the best case benchmark performance. The results in Figure 4.18 show the impacts of posture transitions on the packet delivery performance. The figure shows the number of consecutively lost packets as a function of time. It can be observed that fixed power assignment using PI-l3 experiences higher packet losses during posture transitions than the dynamic assignment schemes. This is due to the possibility of long periods of link disconnection, resulting from posture changes (e. g. a transition between postures 3 and 4 in the second, third, and fourth posture cycles). In contrast, dynamic power assignment schemes experience lower packet loss in general. DPPI is less affected compared to the binary search mechanism, mainly because of its ability to generally better estimate the power level required for the next packet transmission. 81 \D I "U 'T‘ p—A t» "" 4:. I. A No. of consecutive packets lost “1L, $111141! 10 20 3O 4O 50 6O 7O 80 90 100 110120130140150 Time(s) Figure 4.18: Packet drops during posture transitions 4.6.2.3 Energy Per Packet (EPP) Figure 4.19 shows the moving average of EPPs, for the DPPI and binary assignments, computed using an averaging sliding window of 10 seconds. It can be seen that energy performance of DPPI is consistently better than binary search. The energy advantage of DPPI is contributed by: a) lower transmission power levels (see Figure 4.15), lower packet drops (see Figure 4.17), and smaller closed loop control overhead, as explained in the next subsection. 1 In addition to the average EPP figures, the last two columns in Table 4.1 report the cumulative total transmission and reception energy expenditures, for both data and control packets, during the entire experimental period of 160 seconds. 82 I" N Binary % \ DPPI .1 III/V g—n 00 l EPP (mJ/Pkt) I r o I 0.61 I I 1 I I I I 1 1 rfii,rrr r 0 10 20 3O 40 50 60 70 80 90 100110120130140150160 Time(s) Figure 4.19: EPP for DPPI and binary search assignments 4.6.2.4 Energy Overhead of Closed Loop Control The energy costs for the closed loop controlled assignments manifest in the form of transmission and reception of the control packets from the sink to the transmitter nodes. The cumulative control packet communication cost over time is shown in Figure 4.20. Note that this control communication energy for the Linear assignment is the maximum among the dynamic mechanisms. This is simply because of its slower convergence and the subsequently frequent control activities in the events of inter-posture movements. It can be verified from Figure 4.15 that the total count of power assignment changes for the Linear is significantly more than the other two dynamic mechanisms. Although the situation is better for binary search, it also has to send quite a few control packets during the oscillations followed by the postural changes by the subject. The control packet communication costs for DPPI, however, are smaller than the binary, thus indicating fewer control packets from the sink to the transmitter. Faster convergence via postural position inference accounts for this control overhead reduction. This low 83 control energy overhead of DPPI also contributes to its excellent EPP performance as shown in Figure 4.19. A O 1 Cont. Pkt. Energy (ml) H N DJ O O O O 1 L 1 1 I I I I I I I O 20 40 60 100 120 140 160 Tim8e0( s) Figure 4.20: Cumulative control energy expenditure over time 4.6.2.5 Results for Different Subject Individuals Time averaged PDR and EPP results for three subject individuals, one female and two males, are summarized in Table 4.2. All subjects go through the same experimental process as described in Section 4.6.1. Results indicate that the PDR and EPP performance advantage of DPPI holds for all three subject individuals with different body statures and clothing outfits. Although it is possible to get a slightly better PDR using high power fixed assignments (e.g. power level index of 22), the energy cost for that can be very high. Observe that the binary assignment does better than the linear assignment for Subject-1 and Subject-3, but it is slightly worse for Subject-2 in terms of PDR. Our investigations revealed that Subject-2 was more active within postures, causing the liner assignment to handle those intra-posture movements better than binary, for which control oscillations are triggered by such small body movements. The PDDI scheme, however, is able to handle such cross-subject habitual variations and provide the best performance 84 consistently. Also note that the performance of PDDI is closed to the best case benchmark performance (both PDR and EPP) for all three subject individuals. Power Assignment PDR EPP PDR EPP PDR EPP 1 1 1 Table 4.2: Power assignment performance for multiple subjects To summarize, by using its unique ability of postural position inference, the DPPI is able to optimally assign on-body link power in a subject-independent manner while consistently maintaining better balance between packet delivery and the incurred energy cost. We have conducted similar experiments with different on-body sensor positions and posture sequences, and found that the above performance trends also hold in a position and posture independent manner. l .3 Control Scheme: Dynamic Postural Position Inference EPP (mJ/Pkt) _ E: E; .o \O 1 _O 00 1 -87 -86 -85 -83 —82 -81 -80 -78 -77 -76 -75 -74 -72 -71 -70 RSSI Upper Threshold (dBm) Figure 4.21: Energy expenditure with varying RSSI thresholds 85 4.6.2.6 Impacts of RSSI Thresholds In order to choose an appropriate RSSI threshold range, the DPPI mechanism was characterized (see Figure 4.21) with varying values of the upper threshold RT H, while keeping the lower threshold fixed at -88 dBm. With increasing RT H, the transmission energy cost is expected to increase because of higher transmission powers. With this, the packet delivery ratio is also expected to improve. Therefore, the changes in Energy Per Packet (EPP) numbers will depend on which of the above two effects dominate. Figure 4.21 demonstrates that initially with increasing RTH, the EPP reduces because the increase in PDR (and decrease in the number of control packets) dominates the increase in transmission energy costs. However, beyond approximately -82dBm, that relative dominating effect reverses, causing the EPP to start increase. This explains why -82dBm, which provides the best EPP performance, has been chosen as the RT3 (see Section 4.6.2) for all experiments. 4.6.2.7 Results for Different Pastures A subject individual with sensors mounted on his arm and the waist in position 1, as shown in Figure 4.1, is asked to follow the posture sequence of: {Sit (SIT), Lie-Down (DWN), Stand (STD) and Walk (WLK)}. Each posture lasts for 10 seconds, and the entire sequence is repeated four times, resulting in a total experiment duration of 160 seconds. The RSSI threshold range was chosen as before to be -88 to -82 dBm. Note that the power assignment mechanisms discussed in this chapter do not make any assumption about the posture durations. However, as a general rule, when the ratio of the interval between posture changes to the response time is low, power control mechanisms are not very beneficial. 86 Figure 4.22: Power levels and RSSI dynamics with posture changes, for different power assigmnent strategies '50 srr DWN STD WLK SIT DWN STD WLK SIT DWN STD WLKVSIT pWN STD WLK — 24 -60 - ‘ 20 A K O 540 — . t 16 g :7 Power Index ‘ 12 B 3.80 - 5 of. / —— 3 13.. '90 J V - __ 4 Thr. Range PI: 22 -100 0 -50 l I I I I I I T I I I I I I I 24 '60 I RSSI Power Index Pack tL0$ ' __ 20 E I ' . ~— 16 g; a") ~ in m ‘ a. refs - E r: : - I “‘ 12 s m , B -80 E III“! IFJIM :rNIuI r 8 33 hi" I I : ' II 'I)‘ -90 — f/ U - 'V 4 Thr. R ge , PI: 13 400 10 20 30 40 50 60 7Q 80 90 100 110120 130140 1501600 T1me (s) 87 Figure 4.23: Continued I 7 I I I I 24 r- 20 I .1 16% I ~ 12.: I 6 ........ :L‘ 8 m 11' , s- 4 0 r r 1 1 1 1 24 ' Oscillation . I . / ’ I " 2° A . ' M“ “ l6 >< E E IIII f I I II I ‘I 121; (0-30 71- 1" {a ,,,,,,, . z . .1 , ........... , _ o I ‘1‘ ,. I . WWI ........ I. I 1 ............ .8 °‘ -90 - I \1‘ "* * : I , / 4 _50 I I I I T I 1 T I r I I I 24 -60 I Power Index “' 20 A ‘ 16 >< £401 3 : 12 15 m_ _ B 9 8° ......... ~- 1 8 ‘3 -90 - INT g ~ 1 ‘ ’ 4 \ \ ‘ I Thr. Range . DPPI , . { RSSI IJ . '100 10 20 30 40 50 60 70 .80 90 100 110120 130140 150160 0 T1me (s) Figure 4.22 demonstrates the evolution of assigned power levels and the resulting 88 RSSI for two fixed assignment (power indexes 22 and 13) and three dynamic assignments (Linear, Binary and DPPI). Same observations and conclusions can be made as in Section 4.6.2.1 and Figure 4.15. First, with fixed high power (e.g. PI=22) assignments, the RSSI at the sink is mostly above the higher threshold RTH, which is expected to provide excellent packet delivery rate (PDR), but at the expense of high Energy Per Packet (EPP). With fixed low power (e.g. Pl=13) assignments, more often the RSSI remains within the desirable threshold range, causing the EPP performance to be better. But as shown in Figure 4.22, packet losses during link—obstructive postures can affect the PDR performance. These can be validated in the time averaged results presented in Table 4.3, which summarizes results for a set of indoor and outdoor experiments. Indoor Outdoor Power Av. Av. EPP Tx Rx Av. Av. EPP Tx Rx Assgn. PDR (ml/pk!) Energy Energy PDR (mJ/pkt) Energy Energy ("11) (M (In-l) (In-I) Index-l3 82% 1.05 112 37 84% 0.98 109 38 Index-22 96% 1.34 205 41 96% 1.29 198 40 Linear 89% 0.83 126 53 90% 0.74 106 49 Binary 91% 0.74 110 49 91% 0.69 98 46 DPPI 94% 0.66 96 43 95% 0.60 87 42 Table 4.3: Indoor and outdoor performance summary of different power assignments Second, all three dynamic assignment mechanisms manage to maintain the RSSI values within the threshold range longer, indicating a better balance between PDR and EPP. Also, given that the subject’s movements were mostly coarse-grain inter-posture, as opposed to fme-grain intra-posture, the binary search worked better than the linear. However, for binary, the oscillation of the transmission power level and the subsequent departures of RSSI out of the target threshold range are quite evident in several instances including those during the time frames 308-408 and 1403-1603, where the subject is in a high motion posture of Walk. Finally, the DPPI mechanism performs the best by avoiding this oscillation problem via its postural position inference-based assignment as described in Section 4.5.5. Table 4.3 summarizes the average of all the performance indexes for all the assignment mechanisms. While the results show that dynamic 89 mechanisms perform better than static for both outdoor and indoor experiments, it can be observed that the overall energy performance is slightly better outdoors compared to indoors. This can be attributed to the fact that dynamic mechanisms use fewer control packets outdoors due to better channel conditions as there are fewer multipaths. SIT DWNSTD WLKSIT DWNISTD WLK SIT DWN STDWLK SIT DWN STDWLK m 0.9 “ D I I . D-a I _ i f 0.8 ~ : ' / i \DPPI 0.7 ‘ Binary j ‘ I 06 l r I I I I T I I I T I I I I O 10 20 3O 40 50 6O 7O 80 90 100110120 130140150 160 Time (s) Figure 4.24: PDR for DPPI and binary search assignments Figure 4.24 and Figure 4.25 show the moving average of PDRs and EPPs respectively, for the DPPI and binary assignments, computed using an averaging sliding window of 10 seconds. Note that the number of control bits used to provide feedback is slightly higher (i.e. 4 bits) for DPPI compared to Linear and Binary mechanisms. This difference is already accounted for in the EPP metric. Also, for protocols with relatively large preamble size (e.g. 144 bits for 802.11), the additional energy cost due to those extra bits can be considered insignificant. As shown in Table 4.3, these two assignments have the best two PDRs among the dynamic mechanisms. Observe that there are several time durations (e. g. 105—30$) when the binary mechanism loses packets, whereas the DPPI is able to deliver them. A closer look to the RSSI values in Figure 4.22 for that time duration reveals that the binary assignment was dropping packets due to an oscillation in 90 the assigned power level and the subsequent RSSI values beyond the desired threshold range. It can be seen that the energy performance of DPPI in Figure 4.25 is consistently better than the binary search. The energy advantage of DPPI is contributed by lower transmission power levels (see Figure 4.15), lower packet drops, and smaller closed loop control overhead. In addition to the average EPP figures, the last two columns in Table 4.3 report the cumulative total transmission and reception energy expenditures, for both data and control packets, during the entire experimental period of 160 seconds. 1'4 SIT DWNSTD WLK srr DWNSTD WLK srr DWNerWLK’srr DWNSTDWLK 1.2 d I 4' : ~ ' I .1 g , : Binary, Avg: 0. 74 mJ/Pkt . LE 1 _ . DPPI: Avg. 066 mJ/Pkt * = :03. .~ \ I‘r a. . ; I. . » ’\ I 0.6 — , . \ L 0.4 I I i I I I I I I I i i I I I 0 10 20 30 40 50 60 70 80 90 100110120 130140 150160 Time (s) Figure 4.25: EPP for DPPI and binary search assignments 4.7 Summary and Conclusions A closed loop transmission power assignment framework for on-body wireless links has been developed in this chapter. Postural positions as it pertains on a given wireless link are dynamically inferred based on measured RF signal strength and packet drops on a link by link basis, and then optimal power assignment is done by fitting those measurement results on a model describing the relationship between the assigned power and the resulting signal strength. Extensive experimental results are provided to demonstrate the model building and algorithm performance on a prototype body area 91 network. It has been shown that power assignment with the proposed Dynamic Postural Position Inference (DPPI) can provide consistently better packet delivery and energy performance compared to a range of static and other dynamic assignment strategies. It has also been compared with a performance benchmark established by sampling the best operating points across a number of static and dynamic power assignment strategies. The experimental results show that DPPI, using its novel postural position inference strategy, can deliver subj ect-independent performance that is closed to the experimental benchmark. 92 Chapter 5. Posture-Predictive Power Control using Linear-Quadratic Gaussian Control It was shown in Chapter 4 that the optimal transmission power required for an on-body wireless link between two sensors depends on the physical distance of the link, and its instantaneous channel condition. The distance can vary with mobility, driven by human postures, and the channel condition can change due to unpredictable RF attenuation [63] caused by a slew of factors including antenna orientation, clothing, and physical stature of specific subject individuals. As a result, static pre-defined transmission power is not able to provide continuous link connectivity while ensuring minimum required transmission power consumption. Therefore dynamic link power assignment mechanism for optimal on-body energy management is proposed. In this chapter, the dynamic transmission power control mechanism presented in Chapter 4 is enhanced by modeling human body movement as a stochastic linear system and a quantized Linear Quadratic Gaussian control with an Integrator (LQGI). The objective is to develop a model-based transmission power control framework in which RF signal strength is predicted and is regulated at a reference value to enhance the overall energy performance of an on-body wireless sensor. The LQGI framework has been a popular way to design optimal stochastic control for various applications [102-107] such as aircraft control, adaptive optics systems and MEMS camera control. However, to the best of our knowledge, there have been no attempts to use the LQGI approach to the on-body transmission power assignment as attempted in this work. 93 LQGI is used for regulating the Radio Signal Strength Indicator (RSSI) of the receiver node at a fixed reference level for an on-body link. We modeled the RSSI variation process, which consists of its relationship to the transmission power and the body configuration process, as a linear stochastic system. In this LQGI approach, a Kalman filter estimates the state of the system. Simultaneously, a linear quadratic regulator with an integrator, based on the state estimate fiom the Kalman filter, provides optimal power control. 5.1 LQGI Framework 5.1.1 Problem Formulation In this section we present the proposed LQGI-based posture prediction and transmission power assignment mechanism. To implement LQGI, the RSSI process and the body posture processes both are modeled as linear, stochastic systems. Both processes are shown as an augmented system in Figure 5.1. xq (k +1) = Aqxq (k) + qu(k) q(k) 6100 = quq(k) + W(k) P1 0 Q y 36(k +1) = a3?(k) + bu(k) 70c) = cY(k)+du(k) rm P2 v(k) W(k)—-—' u(k) Figure 5.1: Block diagram of the augmented system P1 in Figure 5.1 represents the posture change process and P2 denotes the RSSI process. The discrete-time state-space representation of the augmented system in Figure 5.1 is given by 94 x(k +1) = Ax(k) + Bu(k) + Gw(k) Y(k) = Cx(k) + du(k) + w(k) + v(k) (5.1) where A, B, G, C and d are state matrices, and w(k) e 92 , v(k) e 93 are white noises with the following properties: E(W(k)) = 0, E(W(i)W(j)) = Q and E(V(k)) = 0, E(V(i)V(J')) = R respectively, with E (w(i)v( j)) = 0 , where the term E(x(i)) is the mean value of variable x, and E (x(i)x( j)) is the covariance of variable x. A discrete-time Kalman filter is designed with the steady-state Kalman filter gain as: MS =23CT(CXSCT+R)_1 ' (5.2) where 2 s [102] is the solution to the following algebraic Riccati equation: 2, = AZSAT + GQG T — AZSCT (CZSCT + II)"1 CESAT The tracking error is defined as 3(k)=J’(k) -y,ef where y ref 6 ER is the reference RSSI level. An integrator is implemented to eliminate the steady-state tracking enon The incremental tracking error integral is given by: I (k +1) = I (k) + e(k) = I (k) + Cx(k) + du(k) — yref (5.3) and it is desired to regulate the control action. The augmented system and integrator is reformulated as a linear quadratic regulator. This introduces a new state equation: xtrack (k + 1) = Atrackxtrack (k) + Btrack u (k) _ yref (5.4) ytrack (k) ___ Ctrack xtrack (k) 95 The delay operator is denoted by q‘1 such that q—lg(k) = g(k — 1) . By multiplying each side of the xmwk (k) state equation by the difference operator (1 — q 4) we can obtain: x(k+1)— x(k)]_ {w(k)} track —1 track (1- q )x (k+1)=[1(k+1)_1(k) g(k) —xd (k) (5.5) Define (1— q " )u(k) = v(k — 1) . We can obtain: xtrack k nxn OnXl:|[-xd(k_ 1)]+ +|:B-q]l —l k 1_ ()= [CW 1 80(4) d(‘1 )u()- ( q >ny (5.6) =Atrack xtrack(k_ l)+BtraCkv(k— 1) track and yd (k-l) is given by: ytrack(k_ 1): (1_ q—l)ytrack(k)_ (1_ q—1)Ctrackxtrack (k) ___: dthrack track (k- 1) The overall performance cost function can be written as ”v.2: track (k)ll2 +r2"v(k)“2 ) (5.7) = 205d track (k)TQtrack xg‘ack (k)+ v(k)TRtrack v(k)) k0 T Qtrack : Ctrack Ctrack and Rtrack where = r2 > 0. The quantityris a weight factor on control v(k), i.e, difference between u(k+l) and u(k). The optimal control that minimizes the overall performance cost function J in Eqn. 5.1 is given by 96 k—l u(k) = —K"’“ckx”ack (k) = —Kax(k) — Ke Ze(k) (58) k0 where the optimal control gain matrix is given by T T Ktrack = [Ka Ke]= (Rtrack + Btrack PBtrack )—1 Btrack P Atrack where P is 3 the solution to the following algebraic Riccati equation AtrackTPAtrack _ P- AtrackT P Atrack Ktrack + Qtrack = 0 5.1.2 Quantized LQGI In this approach, saturation and quantizer blocks are added to the LQGI system, as shown in Figure 5.2, in order to generate control (or transmission power u) from a finite set of discrete levels. Figure 5.2 shows quantized LQGI with “S” and “Q” denoting saturation and quantizer respectively. The absence of both the saturation and quantizer blocks is just the LQGI system. “KF” in Figure 5.2 denotes the Kalman filter. The saturation block applies an upper (5 dBm) and lower (-20 dBm) limit on the control input signal. The quantizer block rounds the control input signal at each period of time to the nearest discrete value. As in Eqn. 5.7, r is a weight factor on control v(k), i.e, difference between u(k+l) and u(k). The quantized LQGI (LQGIQ) approach is used to regulate how frequently the controller changes the transmission power level, and subsequently, it regulates the number of control packets sent for a period of time. For lower values of r , there are less penalty on the differences in control, and more penalty on the tracking error as in Eqn. 5.7, therefore, the power level changes more frequently, and the tracking error decreases, respectively. On the other hand, for higher values of r , there is more penalty on 97 differences in control efforts, and less penalty on tracking error, hence, the transmission power level changes less frequently and the tracking error increase. “2 y ref 6(k) , | H “r ya, (k) y(k (k) + £(k) Figure 5.2: Block diagram of quantized LQGI Control 5.2 Performance Results A subject individual with sensors mounted on his arm and the waist was asked to follow the four-posture sequence as shown in Figure 5.3. The movement between posture positions is estimated to take 10 sec, and the entire sequence is repeated nine times, resulting in a total duration of 360 sec. Sensor on the arm transmits two packets every second, one with the linear search power assignment and the other with the binary search. The linear and binary search mechanisms were described in Section 4.5. 98 ‘~~ \ ‘~ On-body Link Wireless Lir‘ik‘x‘}~ On-body Out-of-Body Server Sensors Figure 5.3: On-body sensor positions and the used posture sequence Results from these two approaches are collected experimentally from the prototype WBAN as described in Chapter 2 and Section 4.3.1. Data for the transmission power and the corresponding RSSI values are also collected during these liner and binary search control experiments. These data, collected through the off-body server (see Figure 5.3 and Chapter 2), is then used for simulating different LQGI control approaches as presented in Section 5.1. The simulated LQGI variations include: LQGI with r=2 (LQGI_2), LQGIQ with r=2 (LQG10_2) and LQGIQ with r=700 (LQGIQ700), where LQGIQ denotes the quantized LQGI approach, as defined in Section 5.1.2. The weight factor r’s values are chosen to be very small and very large for representing the low and high energy penalties due to the control packets from the sink to the source sensor. The five control approaches (two experimental and three simulated) are evaluated and compared using the same parameter settings as. in Chapter 5. 5.3 Relevant Performance Metrics The performance of transmission power assignment is evaluated using two primary metrics, namely, RSSI Target Error (RTE) and Energy per Packet (EPP), as described in 99 Chapter 4. The target is to minimize RTE and EPP. RTE is defined as how far the current RSSI from the target RSSI. As presented in Section 4.5.2, the RTL and RTH are chosen to be -88dBm and -82dBm for the linear and binary searches, and ymf for the LQGI approaches is chosen to be right in between RTL and RTH which is ~85dBm. The quantity EPP is computed by dividing the total communication energy, both for transmission and reception, spent by the on-body sensors (including the sink) by the number of successfully delivered data packets. Note that the numerator includes communication energy costs for data and control packets. A number of secondary metrics, namely, transmission energy, reception energy, and control overhead, as described in Chapter 4, are also measured and evaluated. 5.4 Results and Interpretation 5.4.1 Transmit Power and RSSI Dynamics Figure 5.4 demonstrates the evolution of assigned power levels and the resulting RSSI for linear, binary, and the three LQGI-based power assignments. The linear and binary search mechanisms are described in Section 4.5. Power values of CC1000 from -20 to 5 dBm correspond to the power levels from I to 22 are used in the figures. The following observations should be made from Figure 5.4. First, although for the majority of the time the linear and binary search approaches manage to maintain the RSSI within the target threshold range, it fails to be in the range for a significant fiaction of the experimental duration. As explained in Section 4.5.4 and Figure 4.15, the linear approach suffers fi'om the slow stepwise assignment, while the binary suffers from the oscillation problem due to overreactions. The resulting departures 100 of RSSI out of the target threshold range are quite evident in several instances including those during the time frames 405-703, 1203-1503 and 2605-2805. Figure 5.4: Power level and RSSI dynamics with posture changes 15 A RSSI\ 8 Thr. range -70 a 5 I k I: II] A 3 r 5 - m a WWW 1W\ 80“” G I—l .° I w I, a I-.. I V -90 g Tx Pow/er‘xv I" Linear -25 -100 15 E RSSI Tx Power ,3 -70 '3 IS A E a g. -80 a g v .2 a .3 a a-rs - -90 E ‘" Binary -25 -100 0 20 40 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 Time (s) 101 Figure 5.5: Continued 15 ’é‘ Tx Power + -70 m 3 5 ‘ E a o -80 m a. 'u I: '5 “ I.“ .9 m 3 3 g-IS — -90 .3. E-‘ -25 -100 A 15 CE T Pow 3 x er -_ -70 2 5 ‘ o E °‘ L -80 m .5 -5 3 a g g - -90 ad §-15 ~ [— LQGIQ_2 -25 -100 15 5'3 -70 2’ 5 1 0 A E I -80 5, an “o a -5 ‘ : .2 m m (I) ."’ Tx Power of. g . -~ -90 m -15 g LQGIQ_700 -25 -100 0 20 4O 60 80 100 120 140 160 180 200 220 240 260 280 300 320 340 360 Time (s) Second, it can be seen from the LQGI_2 plot in Figure 5.4, that there is a need for modifications to the control, due to the transmission power not being constrained to the transceiver RF power output of —20 to 5 dBm. Therefore, LQGIQ control in Figure 5.2 is 102 implemented. There are two significant changes as a result of the quantized control: 1) the transmission power in LQGIQZ plot of Figure 5.4 meets the constraints of the transceiver; 2) the “smooth” signal on LQGI_2 becomes “stair-step” as shown in LQGIQZ. The penalty r is kept the same in both approaches to show the effects of the saturation and quantizer blocks on the control. Finally, LQGIQ_700 plot can be compared with LQGIQ_2 plot to show the effects of r on LQGIQ control. Notice that when r=2, the controller changes its transmission power level quite frequently. While LQGIQ700 plot shows when the penalty r is increased, the controller changes its transmission power level less frequently. The penalty values of r=2 and r=700 are chosen so that the reader can easily observe this contrast. .9 Ur 0.0109 \ \ LQGI LQGIQ LQGIQ 2 2 700 O I Exp. Results : Sim Results 2.5 g I m g m RTE, SD '31 5 : F3 I E”: 1 i I I 0.0112 : I I I I Linear Binary Figure 5.6: RSSI average error and standard deviation 5.4.2 RSSI Target Error (RTE) Figure 5.6 shows statistical analyses of the tracking RSSI error e(k) , where error average and Standard Deviation (SD) are shown in this figure. Errors for the linear and binary approaches are computed as follows. If the received RSSI value is not within the threshold range, the error will be the absolute difference of the RSSI value and the closest 103 threshold value (either RTL or RTH), otherwise the error is considered to be zero (if RSSI value within the threshold range). With the LQGI approaches, the error is computed as defined in Section 5.1. Figure 5.6 shows that LQGI_2 and LQGIQ_2 both have the smallest tracking average error and SD among all approaches. In other words, the RSSI for these approaches varies the least from the reference trajectory y ref than the others. This is due to the controller being able to yield the “best” RSSI without regard to transmission power constraints. Once the constraints are taken into consideration, as seen in LQGIQ_2, the standard deviation of the tracking error is increased. Notice that a higher penalty in LQGIQ_700 results a higher average RTE and SD. Linear and binary approaches, on other hand, both show high RTE and SD, even with having the threshold range, as described in Section 4.5. 5.4.3 Energy Per Packet (EPP) Figure 5.7 shows the average EPPs for linear and binary approaches compared with different LQGI approaches. It can be seen that LQGIQ_2 has the best EPP performance among all mechanisms. The average EPP for LQGIQ_2 was 0.68 mJ/Pkt. The reasons for LQGIQZ’S best performance are as follows. First, use of quantizer helps to reduce the extreme high transmission powers that are used with LQGI_2, as shown in Figure 5.4. Second, the low penalty on the control by using small r also helps LQGIQZ to reduce the transmission powers by having more control packets compared with LQGIQ700. 104 0.795 .0 00 0.781 : Exp. Results E Sim Results I g 0.75 : E 0'71 0.70 E g: 0.7 : LL] I ' I g0 0.65 g < : 0.6 LQGI LQGIQ LQGIQ - 2 2 700 Linear Binary Figure 5.7: Average EPP for different dynamic search assignments Finally, linear and binary approaches show slightly higher EPP (0.71 and 0.7 mJ/Pkt, respectively) compared with LQGIQZ. The slow step search in the linear search and the power assignment oscillation in the binary search account for this performance loss in EPP compared to the LQGIQZ scheme. Both linear and binary search approaches, however, achieve better EPP compared with LQGI_2 and LQGIQ700. This is because fewer control packets are used in the search-based approaches by having an RSSI threshold range as opposed to a single reference RSSI. The average EPP of LQGI_2 and LQGIQ7OO were 0.795 and 0.781 mJ/Plct, respectively. 5.4.4 Energy Overhead of Closed-Loop Control The energy costs for the closed-loop controlled assignments manifest in the form of transmission and reception of the control packets from the sink to the transmitter nodes. The total control packet communication cost is shown in Figure 5.8. 105 104.4 y—s O 0 Sim Results 00 O 53.65 59-5 CO 4.64 Total Control Energy (ml). O\ o O LQGI LQGIQ LQGIQ 2 2 700 Linear Binary Figure 5.8: Cumulative control energy expenditure Note that the control communication energy for the LQGI_2 approach is the maximum among all mechanisms. Because no qualtizer with low penalty on the control are applied in this approach to target yr.) , where the total control energy was 104.4 mJ/Pkt. LQGIQ700 has the lowest total control energy of 4.64 mJ/Pkt, because of its high penalty on the control due to the high r. Linear, binary and LQGIQ_2 , all have total control energy in between the two extreme values, because the threshold RSSI range and the quantizer in these approaches worked to reduce the number control packets from the sink to the source. The total control energy of the linear and binary power assignments are very closed, and it was 48.43 m] with linear and 49.01 m] with binary. 5.5 Summary and Conclusions A closed-loop transmission power assignment framework for on-body wireless links was developed in this chapter. Human body movement has been modeled as a stochastic linear system and a quantized Linear Quadratic Gaussian control with an Integrator (LQGI) approach has been utilized for optimal power control. Experimental results from linear and binary search-based closed-loop design along with simulation results from 106 LQGI approaches are presented and compared. It was shown that power assignment with quantized LQGI model and small weight factor can provide lower error and energy performance compared with the search-based closed-loop strategies. 107 Chapter 6. DTN Routing in Body Sensor Networks with Dynamic Postural Partitioning In most WBAN applications, ultra-short radio transmission range is a common constraint for low-power RF transceivers designed for embedded applications with limited energy and small form-factors. For such ultra-short transmission range, postural body movements can make the WBANS highly prone to topological partitioning, resulting in a body area Delay Tolerant Network (DIN). Such topological partitioning can often get aggravated by the unpredictable on-body RF attenuation. In this chapter, we have developed on-body store-and-forward packet routing algorithms in the presence of network partitioning. The objective is to minimize end-to—end packet delay by dynamically choosing a route on which the storage/buffering delays are low. While ensuring low storage delay, the developed algorithms will also attempt to minimize the end-to-end hop-count, so that the transmission energy drainage is minimized, thus leading to long network operating durations. 6.1 Introduction 6.1.1 Short RF Transmission Range Short transmission range is a common constraint for low-power RF transceivers designed for embedded applications with limited energy [62],[64], often supplied by harvested operations [65]. Such situations are particularly pertinent for implantable body sensors. Examples of ultra-low range transceivers in the literature include [66] with O-lm, [65] with 0.2-1m, [67] with 0.2m, and [68] with 0-1m transmission ranges. The corresponding transmission powers vary between 0.75mW to 6mW, which are within a range that can be handled with common harvesting techniques such as piezo-electric 108 generation from body movements. Information available in the literature on such low power RF transceivers is summarized in Table 6.1. Reference Tx Tx. Power Rx. Power Range Consumption Consumption (meter) (mWatt) (mWatt) [65] 0.2 - 1 1.5 — 3.5 ~2.5 [66] 0 - 1 2 2 [57] 0.2 0.75 - 3.75 0.75 — 3.75 [68] 0 - 1 6 5.1 Table 6.1: Low-power and short-range RF transceivers 6.1.2 Routing with Network Partitioning Low RF transmission ranges also mean that postural body movements can give rise to frequent partitioning or disconnection in WBAN topologies, resulting in a body area Delay Tolerant Network (DTN) [69-74]. Such topological partitioning can often get aggravated by the unpredictable RF attenuation caused due to signal blockage by clothing material and body segments. Although real-time applications such as patient monitoring may not be supported in the presence of topological partitioning, non-real-time applications such as athlete’s physiology monitoring can still be supported using on-body DTN packet routing across disconnected partitions. Performance goals for such protocols will be to obtain: 1) low end-to-end delay, 2) low packet loss, and 3) low transmission energy consumption. 6.1.3 Objective and Contributions The objective of this chapter is to develop on-body store-and-forward packet routing algorithms in the presence of network partitioning. The objective is to minimize end-to-end packet delays by dynamically choosing routes on which the storage/buffering delays caused due to topological disconnections are low. While ensuring low storage 109 delay, the algorithm also attempts to minimize the end-to-end hop-count so that the transmission energy drainage is minimized, thus leading to long network Operating durations. Note that in the absence of network congestions in low data-rate WBANS, the storage delays due to topological disconnections are usually much larger compared to the congestion delay. That is why the congestion delay is not modeled in this chapter. Specific contributions of the chapter are as follows. m, we have developed a prototype body area network for motivating the on-body packet routing problem and validating the proposed routing algorithm. Second using the prototype network, we have developed detailed topology characterization mechanisms in order to demonstrate the network partitioning caused due to human postural mobility. M a probabilistic and a distance vector packet routing framework are developed using a stochastic link cost formulation that captures multi-scale topological localities in human postural movements. m the performance of the proposed protocols is experimentally evaluated using the prototype body sensor network, and is compared with a probabilistic [74], a utility-age-based [108],[109], and an opportunistic [110] DTN routing protocol from the literature. My, an off-line simulation model is developed for validating the experimental performance trends obtained from the prototype WBAN. 6.2 Related Work Many body area network implementations using on-body sensor communication have recently been reported in the literature [14],[2],[111],[112]. A number of these papers focus mainly on the on-body MAC layer issues. The system in [14] uses a slotted multipoint-to-point architecture in which the data fiom multiple on-body sensors are sent to a sink node in a collision-flee manner. The transmission slots are synchronized using 110 beacons periodically sent by a pre-designated sink node. The mechanisms reported in [2] use an on-body adaptation of the standard IEEE 802.15.4/ZigBee-based MAC. The work reported in [l l 1],[112] investigate on-body MAC-routing cross-layer issues via distributed transmission coordination in the presence of specific routing structures. In [111], the authors present an energy-efficient slotted MAC in the presence of a Wireless Autonomous Spanning tree Protocol (WASP) that is used for on-body packet routing. The mechanism is cross-layer in that the MAC slot allocation is customized for the underlying routing tree, thus providing routing-specific energy economy at the MAC layer. The protocol in [112] adopts a similar tree-based cross-layer approach, but designed specifically for reducing packet delivery delay over an on-body spanning tree. This protocol also handles body mobility by adaptively re-constructing and maintaining the spanning tree used for packet routing. From the on—body routing standpoint, most of the existing WBAN systems adopt star or tree topologies on a connected graph; meaning a physically connected end-to—end path between any pair of on-body sensors is assumed at any given point in time. However, these models do not apply for the targeted DTN routing paradigm in this chapter, which handles topology partitioning leading to scenarios in which end-to-end physical connectivity between node pairs may not be present at times. Such partitioning is caused mainly due to the ultra-short-range RF transceivers as reported in Section 6.1.1. The existing research on routing in disconnected networks (i.e. Delay Tolerant Networks or DTNs) are categorized [69],[70] as: 1) replication-based (multiple copy) [71],[74],[108], 2) knowledge-based [72],[113], and 3) hybrid of the above two [73],[108],[113]. The replication approach explores the ways several copies of a packet 111 can be disseminated among several carrier mobile nodes to increase the chance that it would reach the desired destination. While providing good delay performance, the primary limitation of these protocols is their energy and capacity overheads due to excessive packet transmissions. For ultra resource-constrained WBANS, such overheads are not acceptable. - The knowledge-based strategies are typically for single copy forwarding and they make use of information about connectivity dynamics to make efficient forwarding decisions [72],[1 13]. The hybrid approaches [73],[108],[113] combine the replication and knowledge-based strategies. The general principle behind these approaches is as follows. When a node with a packet to be forwarded encounters another node, the forwarding rule should determine if the packet (or a copy of the packet) should be transferred to that node or it should continue to be buffered. The rule is based on the estimate whether the encountered node is more likely than the forwarding node to visit the destination. For the above mechanisms to work as anything beyond epidemic/viral routing [114], the nodes need to have certain degree of spatial and temporal locality in their mobility and meeting patterns. The scheme PROPHET [74], which is an extension of epidemic routing [115], develops a probabilistic fi'amework for capturing the spatio-temporal locality present in the node mobility pattern within a dynamically partitioned wireless network. The authors in [73] define a high-dimensional Euclidean space, called MobySpace, constructed upon nodes’ mobility patterns. The specific MobySpace evaluated is based on the locality of movements defined as the frequency of visits of nodes to each possible location. Node interaction localities can be also captured in the form a per-link utility as detailed in [108],[116]. The link utility can be formulated as its 112 age [109],[110],[ll6], formation frequency [116], and other historical parameters that can effectively capture the nodes’ interaction localities. Two additional routing protocols, namely opportunistic [108],[110],[116] and randomized [110],[ll6] are also analyzed in the literature for applications in which either there is no node-interaction locality or such localities can not be evaluated. With opportrmistic routing, a source node directly delivers its packets to the destination node, and buffers them till the link with the destination is formed. In randomized routing, packets are randomly routed following the hot-potato logic [110]. Both these protocols are hugely outperformed by the locality-based protocols [110],[116] due to their knowledge about the properties of the links. The above mechanisms are all applied to networks spanning across local to wide areas, few extending all the way up to the inter-planetary scale [117]. The objective of this part of the thesis is to apply the key DTN routing concepts, as identified above, in an ultra short-range body area environment. The challenge is to develop mechanisms for capturing the locality of on-body node movements caused by human postural mobility. A key contribution of our work is to formulate mechanisms that capture multi-scale topological localities in human postural movements. Unlike the existing utility-based [108],[109],[116] and probabilistic [74],[115] DTN routing protocols that capture only short-term node interaction locality, in this work we device mechanisms for capturing movement localities at both short and long terms. Such multi-scale locality is shown to improve the packet routing performance in an on-body context. 113 6.3 Characterization of On-Body Network Topology This section presents an experimental characterization of WBAN network topology with different postural positions. 6.3.1 Experimental Settings A WBAN is constructed (see Figure 6.1), as illustrated in the prototype system in Chapter 2, by mounting seven sensor nodes (attached on two upper-arms, two thighs, two ankles and one in the waist area). Each wearable node consists of a 915MHz MicaZDot MOTE (running TinyOS operating system), with Chipcon’s SmartRF CC1000 radio chip [76], and the sensor card MTSSlO from Crossbow Inc. [78]. The Mica2Dot nodes run from a 570mAH button cell with a total sensor weight of approximately 10 grams. The default CSMA MAC protocol is used with a data rate of 38.4kbps. Modalities: - Blood pressure - Heart rate - Breathing rate ............ ._ ,v , . -Diabetes . -. - Temperature; g - Humidity ’ ' - ECG - Movement - Proximity - Direction Itzzfi'a— ;@ ..... 9 [:3 l C o l - o' a. . n '0 | " I ’. 0 o o 0 ‘ ' 0 o c. .' I . 0' o a . O. I ' V 'l ’ l o . o‘ ‘0'. '0 o a ‘ o. . o I . '0 l. . O . ‘ . 0 I . I ' . ' . ‘ .' o ‘ I 9 - u . . ' A . . ' A . . - ' o f : () l n - t-Of-B 'I a ‘ 0‘ o. a. o e 0 s 0 o . 0.. . . a. o. e. t O O .o o. server . _____ 2'51. ,0" 6; ...... g7 Figure 6.1: On-body Mounted Sensors 114 Via software adjustments of the CC1000’s transmission power, the transmission range is set to be in between 0.3m-0.6m. By doing so, we are able to emulate the ultra-low transmission range for the embedded transceivers [65-68] s reported in the literature. Note that the variation of the range is caused due to the variability in antenna orientation, clothing, and other on-body RF attenuation characteristics. The sensors form a mesh topology with one or multiple simultaneous network partitions. The topology and the number of partitions change dynamically based on the postural positions of the subject individuals. All experiments in this chapter correspond to multi-point-to-point routing in which data from all other nodes are sent to node-6 (see : On-body Mounted Sensors), which is designated as the on-body sink node. This node collects raw data, and sends processed results or events to an off-body server using a wireless link. This external link is created between the on-body sink node and to an off-body Mica2Dot radio node connected to a Windows PC through a custom-built serial interface, running R3232 protocol, as described in Chapter 2. 6.3.2 Variations of Topology and Network Partitions Experiments were carried out for observing the impacts of postural mobility on network partitioning. A human subject, fitted with seven sensors, was asked to follow a pre-determined sequence of postures (SIT, SIT-RECLININ G, LYING-DOWN, STAND, WALK and RUN), each lasting for 20 sec. The status of three WBAN links (1-3, 4-6, and 5-3) during such an experiment is shown in Figure 6.2. The presence and absence of a link’s connectivity, as sampled by the nodes on the link, is represented by l and 0 respectively. 115 l 3 .‘3 m E .4 0 0 Link: 1-3 SIT REC DWN l .. l § :73 fi r—I 0 l 0 20 40 Link: 4-6 Time (S) [0: OFF, 1: ONl STD WLK RUN 1 I . ll § 5 i=5 .4 0 I . _ 60 80 100 120 Lmk: 5—3 Time (s) [0: OFF, 1: ONI Figure 6.2: Variation of link connectivity with postural mobility Each node maintains a neighbor table based on Hello messages sent periodically with low transmission power once in 1.4 see. A time-out period of 2.8 sec. is used for purging entries from the neighbor table. The link status in Figure 6.2 is constructed by combining 116 the neighbor table information from the nodes relevant for the exhibited links. Experimentally, the neighbor table information is periodically sent by all seven on-body nodes to the off-body server (in Figure 6.1) using the fiill transmission power of the Chipcon’s CC1000 radio. The following observations can be made from Figure 6.2. First, few links are connected only during certain postures, which can lead to significant topology variations and network partitioning across the postures. For instance, link 5-3 (between left front thigh and upper left arm nodes) shows the effect of distance on connectivity. The link is connected during most closed postures such as SIT and REC. However, for the stretched out postures such as LYING-DOWN, STAND and WALK, the link is mostly disconnected. Similar trends are observed for the other links including link 1-3 and link 4-6, as shown in Figure 6.2. 4 6 Avg. Nodes is W 8 .. , 4a a No. of i E '8 2 * Partitions i, ' g, z LNUU / “5 ob - ’ 2 o' 3: 1 ~ , Z 0 SIT REC DWN STD WLK 0 0 20 4O 80 100 120 TirisieQ (s) Figure 6.3: Topology and partition properties with posture changes The second observation is that even within a posture, a link may have intermittent disconnections (e.g. link 1-3 is disconnected during the SIT posture from ‘0-20’ see. interval). The reasons for such intra-posture disconnections include minor body 117 movements, RF signal blockage by body segments and clothing material, and also the relative orientations of the node-pairs forming the link in question. The topology level impacts of the body posture variation are reported in Figure 6.3. Observe the wide swing of the node degree (1.5 to 3.8 across the six postures/activities) which indicates a high level of dynamism in the on-body mesh topology. Also observe the number of simultaneous network partitions which vary from 1 to 5, indicating frequent topological partitioning as hypothesized in Section 6.1.2. As expected, the postures with relatively lower node degree correspond to higher number of network partitions. 40% 1 INode-l INode-2 30% .1 QNode-3 ‘2 .9 lIIlNode-4 gg : S 3": ' g V : I. \ o INode-6 E ’5 l5 ; \ . t5: = - I: ’= . \ E '-' IE 5:; § 10% . s :- 65 la \ "—" '-' I: I: \ = L" I: I: \ :l 2 I: ‘3 § 0% _ n... .E E 4.:- ‘ [E x . 0 1 2 3 No. of Neighbors Figure 6.4: Distributed of number of neighbors Figure 6.4 demonstrates the distribution of number of neighbors experimentally obtained for each node in the network for a duration of 1320 see. spanning six postures (SIT, SIT-RECLINING, LYING-DOWN, STAND, WALK and RUN), each lasting for 20 sec. Figure 6.4 shows that for most of the nodes, the number of neighbors vary between 2 and 4, and the probability does not exceed 315% in the best case. This demonstrates as to how the network dynamically partitions based on human postural 118 movements. Such topological disconnections necessitate on—body store-and-forward routing. 6.4 Store-and-Forward Routing With Multi-Scale Movement Locality This section develops routing protocols that leverage short and long term node interaction localities in the presence of partitioned and time-varying WBAN topologies as demonstrated in Section 6.3. 6.4.1 Postural Link Cost with Multi-Scale Locality As discusses in Section 6.2, a key requirement for store-and-forward routing in partitioned topologies is to be able to identify any spatio-temporal locality present in the node movement patterns. In the context of on-body topologies, we propose a novel paradigm of Postural Link Cost Formulation (PLCF) in which a time-varying cost is formulated for each WBAN wireless link based on the locality in the connectivity pattern for the link in multiple time scales. This postural link cost is then applied for executing store and forwarding protocols, which are an adaptation of epidemic routing [59] that leverages the localities of link connectivity in Delay Tolerant Networks (DTN). With posture and activity changes of a subject, the PLCF link costs are automatically adjusted such that the packets are forwarded to next-hops which are most likely to provide an end-to-end path with minimum intermediate buffering/storage delays. The link metric we propose is specifically designed to minimize data delivery delay by reducing the amount of packet buffering time at intermediate nodes. Let us define a Link Likelihood Factor (LLF) Bf}- (0 —<- H]- S 1) which represents the likelihood for the link Lid: (between nodes i and j) to be connected during a discrete 119 t time slot t. If the quantity Pi]- can be designed appropriately to track the locality of link connectivity then it can be used as the link cost [118] for probabilistic routing. We propose that the LLF be dynamically updated after the tth time slot as: Pifj =Piijl + (l —P,.”.' ) - a) if link LU is connected :1 _1 . . . . (6.1) Pi]. =P.fj ~a) 1f lznk La,- 15 dzsconnected t When the link is connected, P,j increases at a rate determined by the t constanta) (0 S a) $1), and the difference between the current value of P. ,- and its maximum value, which is 1. As a result, if the link remains connected for a long time, the t quantity P.1- asymptotically reaches its maximum value of 1. When the link is t disconnected, P1,- asyrnptotically reaches zero with a rate determined by the z constanta) . To summarize, for a givena) , the LLF PU- responds to the instantaneous connectivity condition of the link Lid- . Note that the LLF above captures the locality in short-term link connectivity in a manner conceptually similar to the age-based utility formulation, as developed in [109],[l 16]. It is, however, not the same because in the designs in [109],[116], the routing utility of a link is increased incrementally when the link is formed, and is reduced to zero as soon as the link is disconnected. This formulation of utility misses out the fact that even after disconnection, the formation probability of that link may be higher than a currently-connected link. In other words, those definitions of utility fairly differentiate across currently connected links, but not across the currently non-connected links. In the 120 formulation of utility in Eqn. 6.1, motivated by the logic used in PROPHET [74], we track the short-term locality even when a link is not physically connected. This extended persistency in LLF is expected to improve performance over the existing age-based utility definitions as used in [109],[116]. The next design step is to dimension the pararneterw for capturing link localities at a longer time scale. From Eqn. 6.1, the rate of change of the LLF per time slot can be written as: §(Pifj)= (1—1’55-0} if link Li,j is connected t t—l . . . . (6-2) §(P,-,j) = — P, j - (1 — (0) If lmk Li,j is disconnected t Eqn. 6.2 indicates that for a high a) (e.g. 0.9), Pi,j increases fast when the link is connected, and decreases slowly when the link is not connected. Conversely, for a t loww (e.g. 0.1), Pi,j increases slowly when the link is connected, and decreases fast when the link is not connected. Ideally, it is desirable that for a historically good link (i.e. 1‘ connected frequently on a longer time-scale), Pi, j should increase fast and decrease slowly, and for a historically bad link, it should increase slowly and decrease fast. This implies that the parametera) needs to capture the long-term history of the link; hence it should be link specific and time varying. Based on this observation, we define Historical Connectivity Quality (HCQ) of an on-body link Lid- at time slot t as: l t _ r wi,j_ zLiJ Twindow r=t—TW (6'3) indow 121 r The quantity L“ is 1, if the link is connected (see Figure 6.2) during the time slot r, and 0, if it is not connected. The constant T window represents a measurement window (in number of slots) over which the connectivity quality is averaged. The parameter [0,-i]- (0 5 (0,21- 5 1) indicates the historical link quality Lid- as a fraction of time the link was connected during the last T window duration. The parameter T window should be chosen based on the human postural mobility time constants. Experimentally, we found the optimal T window values that work well for a large number of subject individuals and range of postures to be in between 7 sec. and 14 see. Figure 6.5 shows the evolution of LLF (Pifj) and HCQ (COL-)with time. The top graph shows an example link activity with the first half indicating a steadily connected link with a single fiame (1.4 sec.) of disconnection at time frame 10, and the second half indicates a steadily disconnected link with single frame of connection at time fi'ame 41 sec. The middle graph shows the evolution of (0):j)with a T window set to 7 frames. l The bottom graph shows the evolution of Pi}- with constanta) (i.e. 0.9 and 0.1) and t link-specific time varying 601., j from Eqn. 6.3, indicating the historical link quality. When the link is steadily well connected (during the first half), a high constanta) (i.e. t 0.9) responds well to a momentary disconnection by decreasing Pi} slowly, but recovering quickly when the link becomes reconnected. A low constanta) (i.e. 0.1) 122 responds poorly in this situation by doing just the opposite - that is a fast decrease and slow recovery. 0: OFF, 1: ON 1 LiJ lllllllllllllllllllllllllllllllll Time Frame Figure 6.5: Evolution of multi-scale locality in terms of LLF and HCQ Similarly, when the link is steadily disconnected (during the second half), a low constanta) (i.e. 0.1) responds relatively better than a high constanta) (i.e. 0.9) by t t increasing P.1- slowly for a momentary connection, and decreasing ‘Pij quickly after the 123 link becomes disconnected. The lines for two constant a) values clearly show that a single constant value fora) is not able to handle both good-link and bad-link situations equally effectively. As hypothesized, the link-specific and time-varying (1),-{j , on the other hand, is able to handle both situations well by mimicking the behavior of a) = 0.9 during the historically good-link situation, and that of a) = 0.1 during the historically bad-link situation. These results clearly demonstrate the effectiveness of the HCQ and LLF concepts for designing routing utilities that can capture both short and long term localities of the on-body link dynamics. With this multi-scale approach, the proposed mechanism should be able to outperform both age-based (utility) [109],[1 l6] and probabilistic [74] routing protocols that use only short term locality information. Note that unlike the entities in Figure 6.2 and Figure 6.3, the LLF and HCQ in Figure 6.5 show the link connectivity localities which depends on the short and long term history of the link. The localities captures in Eqns. 6.1 and 6.3 are responsible for this memory-based behavior in Figure 6.5 in contrast with the instantaneous behavior in Figure 6.2 and Figure 6.3. 6.4.2 Probabilistic Routing with Postural Link Costs (PRPLC) Combining Eqns. 6.1 and 6.3, an on-body node i can construct and maintain the Link t Likelihood Factor P, j , for all j eN, j at: i, where N represents all WBAN nodes (i.e. 7 nodes in Figure 6.1). In other words, a node observes and maintains its likelihood to be in direct (one-hop) contact with all other nodes in the network at any given point in time. The routing goal is to reduce the end-to-end packet delivery delay by choosing high 124 likelihood links, thus reducing the intermediate storage delay caused due to packets stuck at nodes on low-likelihood links. The routing philosophy is when a node i needs to forward a packet to node d (d is the sink node), and it meets a node j, the packet is forwarded from node i to node j only if the l condition PM < 13er is found true. In other words, a higher link likelihood of node j to node d indicates that the latter is more likely to meet node (1 than what node i ’s chances are. That justifies the packet transfer fi'om node i to j with a goal of minimizing the end-to-end packet routing delay. This forwarding logic assumes that each on-body node is guaranteed to intermittently come within up to 2-hop distance from the destination node. In other words, node i is intermittently able to see other nodes that intermittently come in direct contact with node d. In our experimental topology this assumption was always found true. In fact for a WBAN topology, it is generally true that depending on the specific postural patterns, all nodes intermittently form direct links with all other nodes in the network. This observation makes the assumption generally applicable for WBANS which usually have a small network diameter. This distributed routing mechanism for a multipoint-to-point implementation is summarized in the pseudo-code presented in Figure 6.6. An extension of link cost formulation without the above assumption is presented in Section 6.7. Each on-body sensor node needs to execute the algorithm as presented here. Using the periodic Hello mechanism, as outlined in Section 6.3.2, each node-i gradually t develops the P”- values with all other nodes in the network. The node also uses the same 1 Hello messages to send the quantity P, j , its Link Likelihood Factor (LLF) with the 125 common destination node-d (e.g. node 6 in Figure 6.1), to all other nodes that are currently connected to node—i. This way, each node will know the individual LLFs of all of its direct neighbor nodes to the common destination node-d. At any given point in time, if there are packets stored in node-i’s buffer (originated at node-i or at some other node), node-i checks if any of its directly connected neighbors has a higher LLF to the destination node-d compared to its own LLF to node-d. If node—i’s LLF is the highest then it continues to keep the packet in its own buffer. Otherwise it finds the directly connected node with the highest LLF to the destination node-d, and forwards packets to that node. This ensures that node-i forwards a packet to the node that is most likely to meet the destination node, thereby reducing the expected end-to-end delivery delay. While the pseudo-code in Figure 6.6 shows a multipoint-to-point implementation for traffic from all on-body nodes to a common destination, the same concept is applicable for point-to-point routing. In that case, each node will require maintaining the Link Likelihood Factors (LLFs) to all possible destinations as opposed to only the common destination, as done in Figure 6.6. Another difference will be that each packet may be forwarded to different next hops depending on its specific destination. The rest of the forwarding logic will be similar to what is presented in Figure 6.6. 126 Routing Logic for node-i to forward packets to sink-d at time slot-t while (true){ for (all nodej[jeN,j¢i]){ l cofd- = 2L2]- Twindow // compute HCQ r =t‘T window if ( Lg, j = I) // 1f link Li ,j is connected -1 —1 Pi,- = Pi; + (1" Fifi )"”i,j else // if link Li, j is disconnected —1 Pair =ij wits . t _ 4a,,- — I) Send Pitd to node-j } Find node-k so that P]: d is maximumfor[keN,k¢i,d,L:.k =1] for (all buflered packets to be forwarded to sink node-d){ if (Li. d = I) // node-i has direct link to node-d Deliver the packet to sink node-d; else{ 'f (Pia >Pifd) // node-k has better link likelihood with sink-d Forward the packet to node-k; else ' Continue buflering the packet in node-i. Figure 6.6: PRPLC routing with LLF capturing multi-scale connection localities 127 6.4.3 Single-Copy Probabilistic Routing (PROPHET) A single-copy version of the probabilistic routing protocol PROPHET [74], which uses only short term link locality information, is implemented in our laboratory prototype for comparing it with the proposed PRPLC with multi-scale link localities. PROPHET relies on epidemic algorithms by doing pair-wise exchange of packets between nodes (as they come in contact with each other) to eventually deliver them to destinations. At a node A, a probabilistic metric called delivery predictability, is established for each of its known destinations B. This metric indicates how likely it is for node A to be able to deliver a message to destination B. Nodes buffer packets if there is currently no available path to the destination. An index of these packets called a summary vector is maintained by the nodes, and when two nodes meet they exchange summary vectors. Updated summary vector information is then used to decide which packets to request from the other node. In the evaluations in [74], the forwarding strategy is when two nodes meet, a packet is transferred to the other node if the delivery predictability of the destination is higher at the other node. The concept of delivery predictability in PROPHET has some similarities with the Link Likelihood Factor used in the PRPLC routing, and is updated [74] via three update equations using update constants Rm: 7: and fl . Since these update constants are not designed to be link-specific and they do not adapt with historical link qualities, the protocol PROPHET somewhat corresponds to the constanta) scenarios in PRPLC as explained in Figure 6.5 and Section 6.4.1. As a result, while the Link Likelihood Factor with adaptive historical link quality in PRPLC can capture the long-tenn localities in postural body movements, it is not possible via the delivery predictability updates using 128 constant B,,-,.7. and ,6 , as used in PROPHET. The performance benefits of PRPLC over the generic design of PROPHET will be presented in Section 6.5. 6.4.4 Distance Vector Routing with Postural Link Costs (DVRPLC) In DVRPLC, nodes maintain end-to-end cumulative path cost estimates to the common sink node. As in PRPLC, the primary goal is to reduce the end-to-end packet delivery delay by choosing a high likelihood end-to-end path, thus reducing the intermediate storage delay caused due to packets buffered at nodes on low likelihood links. Let us define a Link Cost Factor (LCF) Ci}- (0 5 Ci]- 3 Cmax) which represents the routing cost for the linkL ,- (between nodes i and j) during the discrete time slot t. We propose that the LCF be dynamically updated after the tth time slot as: =C: 1 (l— a)? .) if link Lg is connected C}: =C.’:.maxl+(C C :1)-(1— a); j) if link L, j is disconnected (6.4) When the link is connected, Ci,- decreases at a rate determined by (1 —' (0:1) , where 60:1- (O s coil. S 1) is the Historical Connectivity Quality, as defined in Eqn. 6.3. If the link remains connected for a long time, the quantity Ci,- asyrnptotically reaches its minimum value 0. When the link remains disconnected, Ct ,- increases at a rate determined by the quantity (1" COL) , and the difference between the current t cost C j and its maximum value 1. This formulation ensures that a link’s routing cost 129 always reflects the likelihood of the existence of the link while capturing its historical connectivity trends. Note that the time evolution of LCF in DVRPLC follows a rationale that is very similar to that of LLF in PRPLC. The main difference is that while the LCF reduces for connected links, the LLF increases in such situations. Similar difference exists when a link remains disconnected. To summarize, like in PRPLC the cost in DVRPC captures both short and long term link localities for minimum delay packet routing. t Let 7w be the end-to-end cumulative cost from node-i to the sink node-d. According to distance vector routing logic, when a node i needs to forward a packet to the sink node d, and it meets a node j, the packet is forwarded to node j only if the t t condition 713d <4”; is found true. In other words, a lower path cost through node j indicates that the latter is more likely to forward the packet to node (1 than what node i ’s chances are. That justifies the packet transfer from node i to j with a goal of minimizing the end-to-end packet routing delay. This distributed routing mechanism for a multipoint-to-point implementation is summarized in the pseudo-code presented in Figure 6.7. Note that the DVRPLC protocol attempts to minimize end-to-end cumulative routing costs. The objective is that due to this end-to-end cost minimization, DVRPLC should be able to outperform (from a delay standpoint) PRPLC which always interprets its LLF only at the link level and not in an end-to-end cumulative manner. 130 Routing Logic for node-i to forward packets to sink-d at time slot-t while (true){ for (allnodej[jeN,j¢i]){ t t a)“. = Z Li}. /Twindow // compute HCQ r =t ‘ window if ( Lg, j = I) // if link L," j is connected C5,,- =Cit,3'1 '(1- mg!) l _. Send 713d to node 1 else // if link Lid is disconnected -l —1 Cir = C5,; + (Cmax ‘ Ci; HI “ 605,1) if(i = dAND 7:0, > led) t t t . . . 7i d = C i d // 71-, d IS node-1 to smk—d end-to-end cost } Find node-k such that 7]: d is Minimum AND 1 t . . . . 7k,d <7i,d mm” ID EM} it l.d,L§-,j =1] for (all buffered packets to be forwarded to sink node-d){ if (L: d = I) // node-i has direct link to node-d Deliver the packet to sink node-d; else{ if (a valid node-k was found){ Forward the packet to node-k l 72d = C 1., k + 71:, d // update the end-to-end—cost }else Continue buffering the packet in node-i. Figure 6.7: DVRPLC routing with link cost capturing multi-scale connection localities 131 To execute the algorithm in Figure 6.7, each on-body sensor node-i uses the periodic Hello mechanism, as outlined in Section 6.3.2, in order to gradually develop the Cl; values with all other nodes in the network. It also iteratively updates the quantity 7,1,, using the computed Ci]. values with respect to all its neighbors. The node then uses the Hello mechanism to send the quantity 7,1,, , its end-to—end cumulative path cost to the common destination node-d (e.g. node 6 in Figure 6.1), to all other nodes that are currently connected to node-i. This way, each node gets updated about the path costs of all of its direct neighbors’ to the common destination node-d. 6.4.5 On-body Store and Flood Routing (OBSFR) In order to determine the best case delay performance among the above protocols, On-body Store and Flood Routing (OBSFR), a modified flooding protocol for partitioned networks, has been implemented. With flooding, multiple copies of a packet from a source node can reach to the destination through multiple routes, and the first arrived copy at the destination indicates the minimum possible end-to-end storage/buffering delay that can be achieved by PRPLC and DVRPLC protocols. Although a regular packet flooding mechanism can be applied to this application, a few additional routing syntaxes are needed in order to avoid packet losses in certain scenarios that arise specifically due to network partitioning. In addition to a unique identifier {source_id., seq_no. } , a packet also carries a list of node-ids indicating its path so far from the source node. When a node-i receives a packet for the first time (detected from its unique identifier), it buffers the packet till it encounters at least one node that is not there in the list of node-ids found in the packet. Upon encountering at least one such 132 node, the packet is handed over from i to such nodes using broadcast, and then deleted from i’s buffer. Like in regular flooding, upon any subsequent reception of the same packet, node i will ignore it. This modified flooding protocol is used for reducing the number of packet drops in the presence of network partitioning. Consider the following situation. Using the conventional flooding (i.e. not using the list of node-ids) when node i broadcast the packet to a node j, it is possible that node j had already broadcast forwarded the same packet and therefore it simply discards it after receiving from node i. If node i and j are currently forming a network partition that does not contain the packet’s destination, then the packet is dropped from this partition and will never be forwarded to its final destination. However, with the modified flooding that uses the list of node-ids, node i will not broadcast the packet to node j, since in this situation node j is already in the list of node-ids in the packet. As a result, node i will buffer the packet till it encounters a node that is not already traversed trough by the packet in question. This improves the chance for the packet to be forwarded out of the current partition (formed by nodes i and j), thereby reducing the overall packet loss probability. This modification can be applied only to small networks with few nodes, and will not scale for large sensor network with tens of nodes to be added in the list of node-ids in the packets. Note however that even with the above flooding modifications there exists a partition packet saturation situation in which a packet may be lost. Consider the scenario in which after node-i receives a packet for the first time it gets into a partition with two other nodes p and q so that all three nodes are fully connected within the partition. Now since nodes p 133 and q do not appear in the list of node-ids in the packet, node i will broadcast forward the packet to both nodes p and q and delete it from its own buffer. At this point, nodes p and q will broadcast forward the packet to each other since q does not appear in the list of p’s copy and p does not appear in the list of q’s copy of the packet. After this round of forwarding, both p and q will also delete the packet from their own buffers. This will cause the packet to be dropped from this partition and will never be forwarded to its final destination. The OBSFR mechanism for a multipoint-to-point implementation is summarized in the pseudo-code presented in Figure 6.8. Logic for node-i to forward packets to sink-d while (true){ for (all buflered packets to be forwarded to sink node-d){ for (allnodej[jeN,j¢i]){ if(L§-,j = I and j elist of node_ids in packet ){ // j is a neighbor of i, and the packet did not // visit node-j before Broadcast the packet; Remove it from node-i ’s buffer Break; // done with this packet forwarding } else Continue buffering the packet at node-i; } } } Logic for node-i after receiving a packet if ( the packet was not received before) if (this is not the destination) Bujfer the packet in for future forwarding; else Discard the packet; // it was received before Figure 6.8: OBSFR routing logic for packet delay lower bound 134 In spite of these occasional packet drops, this On-body Store and Flood Routing (OBSF R) protocol ensures that the successfully flooded packets to the destination do represent the minimum possible packet delivery delay that can be achieved by our proposed PRPLC protocol. However, due to its inherent flooding nature, the transmission energy cost for OBSFR will be expected to be significantly larger compared to PRPLC, DVRPLC, PROPHET, and other utility-based mechanisms. Note that in the absence of network congestions in low data-rate WBANS, the storage delays due to topological disconnections are usually much larger compared to the congestion delay. The protocol OBSFR is designed to deliver the delay lower bound in the absence of any delays caused due to packet congestions. Although the broadcast-based Epidemic Routing (ER) [115] could have been used for finding the delay lower bounds, we have chosen to implement OBSFR for the following reasons. First, unlike in ER which requires summary vector exchange across neighbor nodes to minimize content transfers, OBSFR uses a node-list in each packet to accomplish the same goal. This helps OBSF R to significantly reduce wireless traffic and energy drainage compared to ER, especially when large numbers of packets are buffered. Second, while in ER a node continues to buffer content even after it is given to another node epidemically, in OBSF R, the provider node removes the packet from its buffer, leading to a much smaller buffer budget compared to ER. The flipside of the above two aspects is that in certain rare situations as explained above as partition packet saturation, OBSFR may not be able to deliver a packet to its desired destination. But its significant capacity, buffer, and energy advantages over the Epidemic Routing, especially in the context of the resource-constrained WBAN sensors, have prompted us to design OBSFR 135 which uses mores constrained flooding than ER, and can work efficiently in a small WBAN with only few nodes. 6.5 Experimental Performance The same seven sensor laboratory prototype network, as shown in Figure 6.1, is used for the results presented in this section. Packets originated from all on-body sensors were routed to the common destination node-6, attached on the right ankle. Most presented results correspond to packets originated from node-3, representing the longest hop (i.e. also worst case) packet routing scenario in most of the body postures. Few results have also been presented for packets originated from node-5 and node-1, indicating the generality of our proposed routing from other segments of the body as well. 6.5.1 Polling-Based Channel Access for Collision Control In order to avoid the CSMA MAC collisions inherent to Mic2Dot’s TinyOS networking stack, we have implemented a higher layer polling-based TDMA access strategy that is managed by the common sink node (i.e. node-6 in Figure 6.1). The primary motivation for TDMA over CSMA access strategy is to operate the WBAN in an energy-efficient manner. The sink node polls the other on-body sensors in a round-robin fashion. A node forwards its packets (both data and Hello) only when it is polled by the sink for giving access to the channel. For our seven-node network (see Figure 6.1), a polling time frame of 1.4 sec is used which is divided into 7 time slots, one for each on-body node (the sink node also needs a slot for sending Hello packets etc. for link cost formulation as described in Section 6.3). Although the data packets and the Hello messages fiom the nodes are transmitted at power adjusted transmission range of 0.3m-0.6m for emulating the low transmission range as outlined in Section 6.3.1, the 136 polling control packets are transmitted by Node-6 at full power so that all on-body nodes receive such packets for effective polling, leading to collision-free channel access. If a node misses a polling packet fi'om node-6, it simply misses one transmission opportunity. As shown in Figure 6.9, each 1.4 sec frame is divided into seven 200 msec time slots. . Each slot is further divided into three 60 msec sub-slots and a 20 msec guard time between adjacent slots. The first sub-slot is used for channel access polling packets fiom the sink node at full power. The second sub-slot is used for data and Hello packet exchange between on-body nodes at low power, emulating the transceivers discussed in Section 6.3.1. ii [[1] Polling packet from sink node E [\3 Hello/Data packet from regular nodes . I E Topology information packet T1me. E i e-1 Node-2 Node-3 Node-4 Node-5 Node-6 o o o 01.4 ,fr...' '5 “x. . “x. M ’ . -. . \°' La \ ‘Kfl -. "" '1‘: | ':\ . '=._ ‘. a“. "3k. [5‘ - l I \ l ': 200 ms :' 2‘ 1400 ms Frame Cycle ——9E 200 ms v C _‘ . ‘7 I : I I I ‘ I ’ ‘ I I I 60 ms each 20 ms Figure 6.9: Collision-free MAC access via polling The third sub-slot is used for a topology gathering process in which each on-body node sends its neighbor information to an off-body machine (see Figure 6.1) at full transmission power. Using time-stamped neighbor information from each on-body node, 137 it is possible to reconstruct the on-body topology evolution as a result of postural body movements. As presented in Section 6.6, such reconstructed topology information is used for offline simulation analysis of the proposed packet routing algorithms. 6.5.2 Performance Metrics The performance of - on-body routing is evaluated using three commonly used [108],[110],[113],[1 16] primary metrics, namely, end-to-end Packet Delay (PD), Packet Hop Count (PHC), and Packet Delivery Ratio (PDR). The index PHC is a direct measure of the communication energy (i.e. for transmission and reception) expenditure of the routing mechanism. Unlike for routing in conventional un-partitioned networks, the PD in partitioned on-body networks depends mainly on the storage delay at the intermediate nodes as a result of network disconnection. The PHC here mainly impacts the number of transmissions per packet forwarding, indicating the energy expenditure; it does not impact the packet delay so much. The target is to minimize PHC while also minimizing the PD by avoiding large packet storage delays by routing a packet through links with low disconnection probabilities or high Link Likelihood Factor as defined in Section 6.4.1. The PRPLC protocol, as presented in Section 6.4.2, is designed mainly to minimize the on-body PD values. 6.5.3 Traffic Generation and Data Collection The source node generates a data packet every 4 polling frames (each frame is 1.4 sec), with a packet size of 46 bytes. Each packet is marked with a monotonically increasing packet—ID so that by observing the received packet-ID, the packet delivery ratio (PDR) can be computed. Also, all on-body network nodes are coarse-grain time-synchronized by the sink node-6 at the beginning of each polling frame. This allows single-trip packet delay (PD) to be computed from a source node to the sink node-6. On 138 its way to the sink node, a data packet collects the entire route information in the form of a list of the intermediate node-IDs. This allows the extraction and analysis of route information including the PHC values. 6.5.4 Packet Delay (PD) End-to-end packet delivery delays from source node-3 on the left upper arm to the sink node-6 on right ankle for PRPLC and DVRPLC are reported in Figure 6.10. Three different versions of PRPLC and DVRPLC was implemented; two with static values of a) (i.e. 0.9 and 0.1) and one with adaptivew , capturing the long-term locality in terms of Historical Connectivity Quality of the on-body links. For each of these scenarios, a separate experiment was run for 1320 see. (i.e. 22 minutes), sending 230 packets, and spanning 6 different postures (SIT, SIT-RECLININ G, LYING-DOWN, STAND, WALK and RUN), each lasting for 20 see. Figure 6.10 reports the average of packet delay computed from each such experiment. All adaptive to results correspond to a connectivity quality measurement window (i.e. T window ) of seven polling frames or approximately 9.8 sec. Value of T window in this neighborhood has shown to demonstrate the best performance for multiple subject individuals, indicating a fairly good estimation of the time constant of the long-term postural movement locality. 139 I—a O 3000 Average Delay (3) N O (0) = 0.1) (a) = 0.9) Dynamic (0 Figure 6.10: Packet delivery delays with static and adaptive a) scenarios The following observations can be made from Figure 6.10. First, with adaptivea) , both PRPLC and DVRPLC protocols are able to successfully capture the long-term locality in postural movements (see Section 6.4.1). As a result, the packet delays for the adaptive to scenarios (3.6 sec and 3.11 sec for PRPLC and DVRPLC respectively) are significantly reduced compared to those for the constant a) implementations which leverage only the short term movement locality as explained in Section 6.4.1. Second, with all implementations, DVRPLC achieves better packet delay compared with PRPLC, mainly because of its end-to-end path cost formulation as explained in Section 6.4.4. Because of its delay superiority, this point onwards we will present results only for the adaptive to scenarios. Unless stated otherwise, the references to the protocols PRPLC and DVRPLC will correspond to their adaptive to implementations, reflecting the multi-scale locality which was not captured in PROPHET [74] and other utility-based mechanisms [109],[l 16] in the literature. 140 #GOO N Average Delay (8) 0 PRPLC PROPHET DVRPLC OBSFR UTILITY OPPT. Figure 6.11: On-body packet delivery delay for different DTN routing protocols Figure 6.11 reports the experimentally obtained average packet delays for a number of protocols including the proposed PRPLC, DVRPLC, OBSFR, an utility-age-based protocol (UTILITY) [116], an opportunistic protocol (OPPT) [110], and the single-copy probabilistic protocol PROPHET (with its delivery predictability update constants PM ’7’: and ,3 chosen as 0.75, 0.98, and 0.25 as reported in [74]). Observe that the flooding protocol OBSFR achieves significantly better packet delay (i.e. the experimental lower bound) compared to the other protocols mainly due to its multi-forwarding nature as explained in Section 6.4.5. On the other extreme, the opportunistic protocol OPPT, in which a source node delivers a packet to the destination only when it experiences a direct link with the destination, shows the worst delay because of the very low connection fiequency between the source node 3 and the destination node 6 in Figure 6.1. With static update constants PM, ,7, and fl , PROPHET suffers fiom the same shortcomings (i.e. leveraging only the short-term locality) of PRPLC with constanta) , as shown in Figure 6.10. As explained in Section 6.4.1, the age-based utility approach (UTILITY) also suffers from the same short-term-only locality, which explains 141 its poor performance compared to the packet delays for PRPLC and DVRPLC (i.e. 3.6 sec and 3.11 sec). With adaptive to , these two protocols are able to successfully capture the multi-scale link localities caused due to postural body movements. It should be noted that in spite of their superior delay performance with respect to PROPHET and age-based UTILITY, there is still room for improvement when compared to the experimental delay lower-bound as demonstrated by the OBSF R flooding protocol. $100% . BPRPLC, Avg: 2.15 g [I] PROPHET, Avg: 2.11 8 80% J DVRPLC, Avg: 2.41 5:; 60% _ $2: OBSFR, Avg: 2.33 gin . $33: a UTILITY. Avg: 2.06 .3 40% " : $555: I OPPT, Avg: 1.0 g 20%— he re 0% _ he: Ell] 2 3 Packet Hop Count (PHC) Figure 6.12: Distribution of Packet Hop Count (PHC) 6.5.5 Packet Hop Count (PHC) PHC serves as a measure for routing energy expenditure (i.e. for transmission and reception) for the on-body sensors. Figure 6.12 demonstrates the distribution of PHC experimentally obtained for all the protocols implemented on our prototype. The figure shows that packets in DVRPLC and OBSFR take slightly longer routes compared to the other protocols. As shown in Figure 6.11, the packets in those two protocols also experience the lowest packet delay. This means that the DVRPLC and flooding protocols route packets through better quality links, leading to smaller delays, even though it requires more number of end-to-end hops. The distribution graph in Figure 6.12 also shows that while majority of the packets from node-3 to node-6 are routed in 142 2-hops, certain packets take one, three, or four hops. Also note that certain packets are delivered directly from node-3 to node-6 (from the upper left arm to the right ankle in Figure 6.1), especially during the closed postures such as sitting. Since in the opportunistic routing protocol (OPPT) packets are delivered only when a source node comes in direct contact of the destination, all packets are delivered with PHC 1. Figure 6.13 shows the number of data packet transmissions. It is computed as the ratio of the total number of transmissions and the number of successfully delivered packets at the sink. This index captures the additional forwarding costs for multiple packet transmissions in flooding-based protocols such as OBSFR. The large number for OBSFR explains the impacts of its multi-forwarding compared to all other single-copy DTN routing protocols. Note that there were no link layer packet retransmissions during these experiments; any channel errors have resulted in dropped packets, and are captured by the Packet Delivery Ratio (PDR) reported in the following Section. & 05 Total N23 of Trans. Per Pkt O PRPLC PR DVRPLC OBSFR UTILITY OPPT. Figure 6.13: Number of transmissions per delivered packet 6.5.6 Packet Delivery Ratio Packet losses are observed due to the following two reasons. First, due to postural mobility, there are transient blackout periods during which a neighbor may appear to be 143 connected in a node’s neighbor table, when in fact it is no longer connected. These blackout periods are created during a node’s neighbor time-out period, which is in the vicinity of 2.8 see, as reported in Section 6.3.2. Packet transmissions during such blackout periods end up in packet losses since no link layer reliability is used. All six protocols suffer from such packet losses. The second type of losses, applicable only to flooding, is due to the partition packet saturation, as explained for the OBSFR protocol in Section 6.4.5. Figure 6.14 demonstrates that due to its multi-packet forwarding, the flooding-based OBSFR looses fewer packets compared to all the other protocols, even though the packet losses due to partition packet saturation are present only for OBSFR. Poor PDR for the OPPT protocol in this case was caused due to a very unreliable link between the source and the destination nodes (i.e. nodes 3 and 6 in Figure 6.1) which are physically situated at two extremes of the subject’s body. Since the OPPT protocol relies on direct source-destination contact for packet delivery, the source-destination link quality affects this protocol most. 90% PDR 80% 71% 70% PRPLC PR DVRPLC OBSFR UTILITY OPPT. Figure 6.14: Packet delivery performance 144 6.5.7 Routing Packets from and to Different Body Segments Delivery delays for packets from different body segments to the sink node placed on the right ankle (i.e. node 6 in Figure 6.1) are shown in Figure 6.15. Observe that as the physical distance between a source and the destination increases, the average packet delays for all the protocols increase. Relatively though, all the experimented routing protocols maintain the same trend for the packet delay as observed in Section 6.5.4. The average packet hop-counts from source nodes 5, 1, and 3 were experimentally logged in the range of 1.25, 1.5, and 2.3 respectively 8 _ E PRPLC /' ' / ' [U PROPHET . Z DVRPLC D OBSFR B UTILITY I OPPT. Ch 4* Average Delay(s) A Src = 5 Src = (Left Thigh) (Waist ) (Upper Left Arm) Figure 6.15: Delivery delay for packets from thigh, waist and arm to right ankle (i.e. node 6) Delivery delays for packets from the upper left arm (i.e. node 3) to different body segments are shown in Figure 6.16. It should be noted that although the absolute delay values are different, the overall trend in packet delay follows the same pattern for all the sink nodes that we have experimented with. 145 _ I: PRPLC - ' - 8 III PROPHET \ / 43 28/ ZDVRPLC 12.36s “315 ' ’5? 3: 6 2 BOBSFR «.-.-.- :3 E1 UTILITY :-:-:-: a I OPPT. ___ ;::::: d.) g0 ‘63 > < 0 ‘ Sink=2 Sink=5 ' Sink—_- (Upper Right Ann) (Left Thigh ) (Right Ankle) Figure 6.16: Delivery delay for packets to arm, thigh and ankle from the upper left arm (i.e. node 3 in Figure 6.1) 6.5.8 Impacts of Postural Stability For all the experiments so far, each individual physical posture was made to last for 20 see. In order to study the impacts of variable postural stability on the routing performance, the subject was instructed to repeat the same sequence of postures as in Section 6.3, but with different posture durations ranging from 10 sec. to 40 sec. 10 - OPPT. UTILITY ~- 60 (u; PROPHET 5 - __ 50 3' E 3 “ 3‘ 0 4.. I— Q 6 1 40 3 °° t -- 30 Oh > < 4 — E E l —— 20 . ° ‘5 DVRPLC OBSFR O 0 r I l 0 10 20 Posture DuratiOITQS) 40 Figure 6.17: Impacts Of posture duration on packet delay 146 Figure 6.17 shows the impacts of posture duration on average packet delay for all six on-body routing protocols. Due to its significantly higher values, the packet delays for the OPPT protocol are plotted as a separate axis in Figure 6.17. Observe that the packet delays for all the protocols generally increase with higher posture durations. This is because longer posture duration implies that a connected link remains connected for longer duration and also a disconnected link remains disconnected longer. As a result, a packet that is buffered in a node due to network partitioning remains buffered for longer duration, leading to higher end-tO-end packet delay. In a relative sense, all the experimented protocols maintain the same performance trend for the packet delay as Observed in Section 6.5.4, Figure 6.11. 95% ‘ ; 90% ‘ \ — M" 85% - / Q 80% +PROPHET p" +PRPLC 75% — +038“ +DVRPUC 70% -jl_____ . +m I - :5- -' OPPT. 65% I l l 10 20 40 30 Posture Duration (3) Figure 6.18: Impacts Of posture duration on packet delivery ratio Figure 6.18 shows the impacts Of posture duration on the PDR metric. As explained in Section 6.5.6, the primary reason for drops is transient blackouts due to postural mobility. With higher posture durations, the degree Of mobility is less, and therefore the drops are less frequent. This explains a general increase in packet delivery ratio with higher posture durations. 147 29.31 sec/ . 8 6 4 Average Delay (8) 2 0 PRPLC PROPHET DVRPLC OBSFR UTILITY OPPT Figure 6.19: Packet delivery delay with intra-posture movement 6.5.9 Impacts of Intra-posture Movements All the experiments so far correspond to the inter-posture sequence (SIT, SIT -RECLINING, LYING-DOWN, STAND, WALK and RUN), as introduced in Section 6.3.2. Figure 6.19 presents packet delay for similar experiments, but carried out with an intra-posture sequence comprising Of the positions SIT, SIT-RECLINING, RECLINING-RIGHT-CROSS, RECLINING-LEFT-CROSS, RECLINING-RAISED-RIGHT, and RECLINING-RAISED-LEFT, where CROSS and RAISED refer to cross-legged and leg-raised sub-postures while sitting. The primary objective of these intra-posture experiments is to study the impacts Of higher granularity postural movements on the on—bOdy routing protocol performance. Comparing the performance in Figure 6.19 with those for inter-posture movements in Figure 6.11, it can be Observed that the relative performance trends across all the six protocols are still maintained for this high granularity intra-posture case. The absolute delay values, however, have been slightly reduced due to a better overall connectivity compared to the inter-posture case. Similar trends were consistently Observed fi'om many more inter- and intra-posture experiments carried out during this work. 148 Figure 6.20: Experiments with different sensor placements 6.5.10 Impacts of Sensor Placements Additional on-body sensor placements, as shown in Figure 6.20, were experimented with for evaluating the validity of the routing results Obtained so far from the sensor placement shown in Figure 6.1. Different source and sink nodes are used in the two placement settings P1 and P2 in Figure 6.20. The inter-posture sequence, described in Section 6.3.2, was followed by the subject and the corresponding packet delay results are presented in Figure 6.21 for the placement settings P1 and P2 in Figure 6.20. Generally, the relative performance trends across all the experimented protocols as Observed for the original sensor placement (in Figure 6.11) remain valid for the new sensor placements P1 and P2 in Figure 6.20. The delay for the placement P1 is larger due to the longer source-tO-destination distance compared to that in P2. 149 Average Delay (s) H PRPLC PROPHET DVRPLC Average Delay (3) PRPLC PROPHET DVRPLC OBSFR UTILITY OPPT Figure 6.21: On-body packet delay for: (a) sensor placement P1, and (b) sensor placement P2 6.6 Offline Simulation with Experimentally Obtained Topology The Objective of this section is to develop an Off-line simulation framework that uses network topology traces Obtained during the on-line experiments described so far. The motivations for such simulation are to: l) validate the correctness of the experimental results, 2) determine a benchmark performance with the minimum possible delay for a given posture/topology sequence, 3) develop a mechanism for Offline experimentation with new protocols, before implementing them online which is significantly more experimentally involving. 150 Real-time Experiment 2 3 with PRPchand Real- time Offline DVRPLC" Topology v dons Export 5'5 ‘ Simulated Source 1 "I PRPLC and I“ 4H5 DVRPLC i 6 6 57 Export Dynamic Topology Comparative Performance Evaluation Experimental /\_/ Performance N —> /\_/ /\_/ Figure 6.22: Experimental topology export for offline simulation In order to keep the results comparable, the simulation is performed on the exact same topology sequence used for the experiments. During the experiments described in Sections 6.3 and 6.4, all seven on-body nodes periodically export their neighbor table to an off-body machine using full transmission power. This external machine then derives the experimental topology sequence by combining the time-series neighbor table information. The Offline simulation is performed on this topology sequence and the results are then compared with those Obtained experimentally. This arrangement is summarized in Figure 6.22. 6.6.1 Delay Benchmark In order to determine the best case end-tO-end delay performance, an Offline route search algorithm, Backward Search for Delay Benchmark Routing (BSDBR) has been developed. As long as the entire topological sequences for a dynamically partitioned network are known a priori, the BSDBR algorithm is able to compute the most delay 151 Optimal end-to-end path for each packet depending on its source, destination, time Of origin, and the complete topological sequence information. BSDBR is designed to be an Offline centralized search algorithm, to be executed in the presence of entire time series topology information. Let to be the time instant at which a packet is generated at node-i and routed towards destination node-d. Given a known topology sequence, the Objective is to find the earliest time instant after t0 at which the packet can be delivered to the destination. Let t1 be the earliest time instant (t1 > to) at which destination node-d comes in contact with any other node-j (j e N, j ¢ d). The minimum possible delivery delay for the packet originated at time t0 can be written as (t1 - to). This minimum delay is possible only if the necessary network links are formed across the network during the time interval [t0 t0 t1] so that the packet could be forwarded multi-hop all the way from the origin node-i to node-j before time t]. The Obj ective of BSDBR search process is to scan the network topology sequence in order to find if such link formations are there so that (t1 - to) can represent the minimum packet delivery delay. If the search process concludes that the packet cannot be delivered by time t], then the next feasible time instant t2 is identified and a similar search is conducted to determine if (t1 - to) can be the minimum delivery delay. The quantity t2 is the earliest time instant after t] (t2 > t1) at which destination node-d comes in contact with any other node-j (j EN, j at d). This BSDBR search process is iteratively continued till a valid minimum delivery delay (tr- to) is found. The time instant tr corresponds to the earliest 152 contact time so that the necessary network links are formed across the network during the time interval [to to tr] so that the packet can be forwarded multi-hop all the way from the origin node-i to destination node-j by the time tr. Note that the expected value Of the packet delay lower bound could have been computed using the Linear Programming formulation as adopted in the full knowledge-based approach in [113]. Instead, we have chosen to implement BSDBR since it allows us to determine the minimum packet delay for each individual packet as Opposed to their average in a statistical sense. Also, the formulation in [113] is more complex than BSDBR since it incorporates the effects Of message queuing which is not studied in our implementation. 6.6.2 Simulated Performance Results The same experimental topology sequence in Section 6.5 is used for the simulation results presented in this section. Packets are routed from node-3 to node-6 with a data rate Of one packet every 4 fiames. Figure 6.23 shows the packet by packet delivery latency of PRPLC and DVRPLC fiom simulation and experiments for a total duration Of 1320 see (or 22 minutes), involving transmissions Of 230 packets for each protocol experiment. Figure 6.24 reports the corresponding Packet Hop Count (PHC) from the same experiment. 153 100 16- 312: E 0 a 3 - a ti fl 4‘ O I I I I I I I T 0 20 40 60 80 100 120 140 160 180 200 220 PacketID 16* lllllllllllllllll — Sim, Avg: 3.39 sec. “““ t, 312 5 PRPLC - Exp. Avg 3.60 sec. 5 5‘ : 0 I a 8 - : 3 l 0 A I l a“: 4‘ g 0 r I I I I i 40 50 6O 70 80 90 PacketID 15 — §IO~ i _g .. g 5 O-t O I I I 0 20 40 60 80 100 120 140 160 180 200 220 PacketID 15 — """" _ . “““““““““““““““ Srm,Avg:2.89sec. ~-__. 3 —Exp, Avg: 3.11 sec. 5 >5 1 7.310 DVRPLC : a s 6 I .34 5 - 8 On 0 I I I f -—'1 I 40 50 60 70 80 90 100 PacketID Figure 6.23: Delivery delay from experiments and simulation 154 A4 U I 3*. E3 0 o i j ‘1 l O I .352 ' O .2 , ll D. II I I V I I I T I 0 20 40 60 80 100 120 140 160 180 200 220 PacketlD 70 PacketID 65 :1: 954 g: §2 % I is? 0 1' I l T I l I l I I I I 0 20 40 60 80 100 120 140 160 180 200 220 PacketID A5 _ _-—- _______________________ g ’ . ~~~~~~~~~~~ 8.54 - DVRPLC Sm AVE 2-3 .. —Exp,A .2.41 5 U 40 50 60 70 80 90 100 Packet ID Figure 6.24: Packet hop counts from experiment and simulation 155 For clarity, delivery latency for the 40th to the 100th packets are zoomed in and shown in both Figure 6.23 and Figure 6.24. As expected, the simulated packet latencies are slightly better (approximately 7%) than the experimental values. However, the overall trends are very similar, indicating that the Operations of the PRPLC and DVRPLC implementations within the prototype on-body network are very similar to the offline simulation as arranged in Figure 6.22. The primary reason for the performance loss in the experiments is the packet drops caused due to the reasons as explained in Section 6.5 and Figure 6.14 and Figure 6.18. For the Offline simulation, 100% packet delivery helps keeping the packet delivery latency slightly higher. The PHC in Figure 6.24 shows a very similar trend in which the simulation average is slightly better than the experimental results. 5.79 sec. NUJ-PIJIO Average Delay (8) H O PRPLC PROPHET DVRPLC BSDBR UTILITY OPPT. Figure 6.25: Simulated average packet delivery delay Figure 6.25 reports the average packet delay of PRPLC and DVRPLC compared with BSDBR, UTILITY, OPPT, and PROPHET (with the constants 13...,2’, and ,8 chosen as in Section 6.5.4 and reported in [74]). For all the protocols, the same topology sequence which was extracted from the on-body experiments is used. Observe that 156 PRPLC and DVRPLC achieve significantly better packet delay compared to that (5.79, 4.05 and 34.8 sec) Of PROPHET, UTILITY and OPPT respectively. This trend agrees with the experimental results reported in Section 6.5 and Figure 6.11. Also note that the packet delay of PRPLC and DVRPLC are close to the best case Offered by the benchmark Obtained using BSDBR. I IN ()1wa O p—d Packet Hop Count (PHC). o 'u: H PRPLC PROPHET DVRPLC BSDBR UTILITY OPPT. Figure 6.26: Simulated average of Packet Hop Count Figure 6.26 shows the corresponding PHC performance. The figure shows that packets in BSDBR take longer routes compared to the other three protocols. As shown in Figure 6.25, the packets in BSDBR enjoy the minimum packet delay. This means that BSDBR routes packets through better quality links, leading to smaller delays, even though it requires more number of hops. These results are very similar tO the experimental results in Section 6.5.5 and Figure 6.12, where the flooding-based protocol OBSFR Offers the best delay, but at the expense Of longer routes. Figure 6.26 also shows that the packets in DVRPLC are delivered using slightly longer routes compared with PRPLC, PROPHET, UTILITY and OPPT. 157 6.7 PRPLC without 2-Hop Assumption As explained in Section 6.4.2, the baseline PRPLC in Figure 6.6 assumes that each on-body node intermittently comes within up to 2-hop contact Of the destination/sink node. While this assumption is generally expected to be true for WBANS which usually have a small network diameter, in theory the assumption may get violated for networks with large diameters. In this section we generalize the link cost logic by using a transitive component [74]. 6.7.1 Transitive Update of Link Likelihood Factor In the generalized case, a node i may forward a packet to node j, event if node-j has never directly visited the sink/destination node-d. A consequence Of this generalization is that the Link Likelihood Factor (LLF) of L13} now can change not only based on the connectivity status of the link, but it can also increase based on the LLF of the intermediate nodes that node i may meet over time. This transitive change Of LLF can be captured by executing the following additional (to Eqn. 6.1) update equation when the link L5,}, is connected. t _ t—l H t t t t BJ—BJ +(1_B,j ) i,k' k,j°a)i,k'wk,j (6-5) The transitive update equation above indicates that if node-k has a high LLF to node-j, then every time node-i meets node-k, the LLF Of link LL} goes up by a factor that depends on the Historical Connectivity Quality (HCQ) Of links L5,]. and Lk,j . With the above addition of LLF update logic, the same logic in Figure 6.6 can be used for packet forwarding. Note that in order to support the above transitive update, each node is 158 required to report the LLF and HCQ information about all its neighbors in its periodic Hello messages. 16 1 Packets with performance difference — NO Transitive, Avg: 3.39 sec. With Transitive, Avg: 3.16 sec. h—i N 1 Packet Delay (3) OO 0 l l I I I ' F 4M. l I 0 20 40 6O 80 100 120 140 160 180 200 220 Packet ID Figure 6.27: The impacts Of transitive updates on delivery delay 6.7.2 Performance with Transitive LLF Update Figure 6.27 and Figure 6.28 show delay and Packet Hop Count (PHC) performance Of PRPLC from simulation experiments conducted with and without transitive LLF updates. For fair comparison, both sets Of experiments were carried out on the same topology sequences. The same experimental settings as in Section 6.6 are used. As shown in Figure 6.27, the inclusion Of transitive LLF update does slightly improve the packet delivery delay (approximately 6%). The packets for which there is an improvement are encircled in the figure. These improvements are caused mainly due to the fact that with transitive update, a node is now able to forward a packet tO the sink through nodes that may never see the sink directly. This also means that for those packets that are delivered with lower delay will have higher hop counts. This explains the higher PHC number in Figure 6.28 for PRPLC with transitive update. For example, in Figure 159 6.27 packets 7, 8, 18, 38, 82 and 106 are delivered with lower latencies, but in Figure 6.28, higher PHC is reported for delivering those packets. a 4 _ —NO Transitive, Avg: 2.08 :1: -- With Transitive, Avg: 2.22 EL 3 _ 5 _ I; 8 l l . . g, 2 l‘ v v a I \ r51 . J \ / '56 Packets with performance difference a O I I I I I I T l I I f 0 20 40 60 80 100 120 140 160 180 200 220 Packet ID Figure 6.28: The impacts Of transitive updates on Packet Hop Counts (PHC) Note that the delay improvements due to the transitive update mechanism remain limited due to the small WBAN diameter as explained in Section 6.4.2. For networks with larger diameter, more number Of intermediate nodes will be available under the with-transitive version Of the protocol, and the resulting delay improvements in those cases will be expected to be much higher. 6.8 Summary and Conclusions Store-and-forward packet routing protocols for wireless body area networks (WBAN) have been developed in this chapter. The concept Of a stochastic link cost was introduced for enabling a probabilistic and a distance vector on-body routing protocol in the presence Of postural mobility Of human body. Performance Of these proposed protocols were evaluated both experimentally and via simulation, and then compared with a generic probabilistic routing protocol and a specialized on-body packet flooding mechanism that provides the routing delay lower-bounds. It was shown that via 160 successful modeling of the spatio-temporal locality of on-body link disconnection patterns, the proposed algorithms can provide better routing performance compared to the existing probabilistic routing protocols in the literature. Ongoing work on this topic includes developing a distance vector routing algorithm using a similar stochastic link cost metric, and developing a Kalman Filter-based body movement prediction model for predictive on-body packet routing. 161 Chapter 7. Modeling On-body DTN Packet Routing Delay This chapter presents a stochastic modeling framework for the store-and-forward packet routing protocols that are presented in Chapter 6 for Wireless Body Area Networks (WBAN) with postural partitioning. Delay modeling techniques for evaluating single-copy on-body DTN routing protocols are developed. End-to-end routing delay for a series of protocols including opportunistic, randomized, and the two proposed mechanisms in Chapter 6 that capture multi-scale topological localities in human postural movements have been evaluated. Performance of the analyzed protocols are then evaluated experimentally and via simulation to compare with the results obtained from the developed model. Finally, a mechanism for evaluating the topological importance of individual on-body sensor nodes is developed. It is shown that such information can be used for selectively reducing the on-body sensor-count without substantially sacrificing the packet delivery delay. 7 .1 Introduction The goal of this chapter is to develop analytical modeling mechanisms for computing packet transfer delay for a series of DTN routing algorithms that can be implemented in an on-body setting. The dominating delay in DTN routing is contributed by packet buffering caused due to topological disconnections, as we discussed in Chapter 6. In the absence of network congestions in low data-rate WBANS, such buffering delays are usually much larger compared to the congestion delay. That is why the congestion delay is not modeled in this chapter. Specific contributions of the chapter are as follows. First, the developed prototype body area network in Chapter 2 is motivated the on-body packet routing problem. The prototype is conducted on-body routing experiments with the DTN 162 routing protocols that are modeled and evaluated in this chapter. Second, a topology trace collection mechanism, as discussed in Chapter 6 is developed for wirelessly extracting network topology, as a function of human postural dynamics, from the on-body sensors to an off-body server. Third, analytical techniques are developed for modeling the end-to-end packet delay for a range of DTN routing algorithms, namely, opportunistic [108],[116],[110] utility-based [108],[110],[109], random [108],[110],[119], PRPLC [120],[121], and DVRPLC [120],[121] . Fourth, the DTN routing delay obtained from the developed model are compared with results from on-body experiments from the prototype WBAN and off-body simulation carried out on network topology traces obtained from the prototype WBAN. Finally, using the model and the topology trace data, a detailed analysis is carried out for identifying non-critical nodes in order to design a minimal WBAN topology from the routing stand point. Modalities: - Blood pressure - Heart rate - Breathing rate . - Diabetes . - Temperature? - Humidity ' ‘ - ECG - Movement - Proximity - Direction l:| Out-of-Body Server Figure 7.1: On-body Mounted Sensor 163 7.2 Topology Trace Collection for Off-Body Routing Simulation A DTN WBAN is constructed as in Figure 7 .1 (also illustrated in Chapter 6), by mounting seven sensor nodes (attached on two upper-arms, two thighs, two ankles and one in the waist area). A remote trace collection mechanism was developed so that real network topology traces from the prototype WBAN can be wirelessly collected and used for routing model development and off-line routing simulation experiments. On-body Experiment Exported Dynamic TOPOIOEY 2 3 a, :- Real-time \é/ 4 Dir-body Topology . 3 Simulation Export ; \_ I“ 4“: is ~I°M0d61iw ..-® , . ? 'g Performance 3 i 6 8 é>7 Comparative Performance Evaluation /\-/ /\-/ Experimental Delay /\_/ Prototype WBAN Performance of DTN /\_/ Routing Protocols 4' Figure 7.2: Topology export for offline and model performance As depicted in Figure 7.2, during the on-body experiments, the state of each link is periodically sent to the off-body server at full transmission power. The server collects the link-state samples (ON or OFF) from all the on-body links and stores them with a time-stamp from its local clock. All these link-state samples, together, form topology traces which are then used for delay model development and off-body routing simulations as presented in Sections 7.3, 7.4 and 7.6. Results from the delay model and off-body simulations are compared with the routing performance from the on-body experiments 164 since all of them use the exact same topology traces, ensuring comparable link state and network partitioning patterns. 7.3 Modeling DTN Routing Protocols The objective of this section is to model the delay of: a) a series of existing single copy DTN routing algorithms applied to on-body settings and, b) two specific routing algorithms that are specifically developed in Chapter :6 to leverage the locality of WBAN topology as function of postural body movements. Definition 1 (Link State): The state of a link between two on-body nodes i and j at the th . . . . . . n discrete time slot 18 represented as Li.j (n) , Wthh IS assrgned the value 1 or O to indicate the state to be connected or disconnected respectively. The time slot here is an observation time slot which corresponds to the Hello interval period for neighbor/link discovery. In our prototype implementation, it was set to be 1.4sec. |i—|—|T‘]fi Time I— Ti’J Off—H Ly-20 Ag], 1 Figure 7.3: Example connectivity of an on-body link Definition 2 {Link Disconnection Probability): The Link Disconnection Probability (LDP) for the link between node-i and node-j is represented as 13,1- (k). The quantityPi (k) represents the probability that after an arbitrarily chosen time slot, the link remains disconnected for k consecutive disconnected time slots. In a sufficiently long 165 . . . k topology trace, spanmng T time slots, if n represents the number of occurrences of such k-slot long disconnections, then the LDP can be expressed as: ,. II; /T, fork 21 321(k): ZL,J(n)/T, fork = o (7.1) n=1 The casek 21 represents situations for which the arbitrarily chosen slot is a part of one of the T of periods (except the last slot on the T oflperiod) or the last slot during one of the T 0,, periods (see Figure 7.3). Similarly, the case k = 0 represents situations for which the arbitrarily chosen slot is a part of one of the T 0,, periods (except the last slot on the T 0,, period) or the last slot during one of the T oflperiods. With above definition of if ,- (k) , we T A have Zho Pi]- (k) = 1 , and its expected value can be represented as: ELDM. = :=Ok13, -(k) (7.2) ,1 where ELDiJ- is the Expected Link Delay, representing the average number of disconnection slots after an arbitrarily chosen slot. In other words, ELDiJ- can be _ i’j ', ' . . . . expressed as ELDi, j — Tofl /2 , where T 03er rs the average disconnection duratron for link i to j. 7.3.1 Opportunistic Routing In DTN Opportunistic routing (OPPT) [108],[110],[ll6], a source node delivers packet to the destination node only when the two nodes come into direct contact. This single copy mechanism offers a simple DTN routing approach for which the delay can be 166 very large, especially in scenarios with low mobility or infrequent link formation between the source and destination. As done in [116], the opportunistic routing is modeled and analyzed in this section for estimating the worst delay performance when complex algorithms need to be avoided for the resource-constrained on-body sensors. Since a source node 3 delivers a packet to destination d only when L3"; = 1 and a packet at node 5 can be generated at any arbitrary time slot, the delivery delay for a packet is ELDM as developed in Eqn. 7.2. This is true only when the packet generation rate is low enough so that no more than one packet is generated during a T of period (see Figure 7 .3). This means that the generated packet can be delivered at the very beginning of the immediately following T 0,, period without any additional wait. However, when the packet generation rate is higher so that multiple packets are generated during a T017 period, the packets need to be delivered one per time slot during the next T 0,, period. This backlog clearance adds an additional delay component that needs to be added in addition to the ELDW from Eqn. 7.2. Let B represent the number of packets generated during the T 017 period. With A being the packet generation rate at the source node 3, B = I1 ' Tofl' . After the subsequent T 0,, period starts, these B packets are flushed one packet per time slot, requiring B time slots. During these B slots, another B .2 packets are generated which are then cleared one per slot. Combining the backlog clearance delay with the Expected Link Delay (ELD), the average delivery delay for the packets generated during the T off period can be written 167 B-l as ELDsd + 2i B . Average delay for the packets generated during the T 0,, period i=1 B 824 . can be written as? + 2’. Therefore, the overall average packet delay for on-body i=1 opportunistic routing can be expressed as: B-l B 31—1 B- ELDsd +Zi +B-l- 3+ 21' i=1 i=1 DOPPT = B+B-l , (7-3) where Expected Link Delay (ELD) can be computed in Eqn. 7.2, and 9d _ . o u o B = A ' To} — 2 ' A ' ELD 3,01 . Note that thlS expressron rs valrd when the system is stable in the sense that on an average, all packets generated during the T 0,, and T017 periods are able to be delivered during the T 0,, period for the link between nodes 3 and (1. 7.3.2 Randomized Routing In a randomized routing protocol (RAND), if a node with a data packet does not have a direct connection with the destination, the node forwards the data packet to a neighbor chosen at random [110],[l 16]. The packet is subsequently forwarded in the same way, till it is received at the destination. Unlike for hot-potato routing [110] in large networks, the delay performance of RAND can often be better than that of opportunistic routing in small body area networks only with few nodes. Smaller topologies have lesser number of end-to-end path combinations, leading to quicker delivery. Also, the network partitioning, as shown in Figure 6.3, helps reducing the path combinations even further. Packet looping, which is inherent in a randomized routing protocol, can be avoided by recording a packet’s traversed path in it incrementally so that a forwarding filtering can be 168 implemented. A packet is never forwarded to a node that is recorded in that packet’s already traversed path. Definition 3 (Forwarding Probability): In RAND forwarding, a node-i forwards a packet uniformly randomly to one of its currently connected neighbors. Therefore, at any time slot n, the probability of node i forwarding a packet to node j is defined as: L. .(n) f _ " BJ (n)— N j ELM (n) j=1 and Pif(n)=0foralljeN, N (7.4) 1' ¢ in at d, ifZL.,,~ (n) ¢ 0 and 1,, (n) = 0 j=1 where N is the number of nodes in the on-body network. Eqn. 7.4 is applicable as long as N node i currently has at least one neighbor l'e° ZLiJ (n) at 0 and none of those j=l neighbors is the destination node d (i-e- [4,3,1(71): 0). In case when node i has destination d as a current neighbor, the packet is forwarded to node d with probability ‘1’. Also, when node i has no current neighbors, it keeps buffering the - f _ . . f _ . . , packet (Le-PL,- (n) — 1 ), resulting mg”,- (n) —- 0, f0r all 1 $1 . Incorporating all these situations, Eqn. 7.4 can be expanded as: 169 L. .(n) Pi£(n)=—Ni—and Pi5(n)=0foralljeN, j¢i,j¢d, 2173101) j=l N if 2L1.) j(n) ¢ 0 and Li", (n) = 0 j=l (7.5) 1351(n)=1, 135(n)=0, 35(n)=0forazlje1v,j¢i,j¢dsz,,d(n)=1 N 135004 and 35(n)=0,fora11jeN,j¢z-,if ZLI-J(n)=0 i=1 Definition 4 (Forwarding Matrix): The forwarding matrix captures the forwarding probabilities at time slot n across all possible links in the network with N nodes and can be represented as: 1: Plfloz) PIQOI) PLC-(n) fime 2: P2{1(n) P2{2(n) P2201) P21: N(n) A(n)= i: Pigln) ago) Fifi“) fig/(n) (7.6) d: 0 O ... 0 ... O _N; Pilot) P15,2(n) P15, j(n) PIMP“), The Forwarding Matrix A(n) has two notable properties. First, the elements in the (1th row are all zeros since the destination node d never forwards a packet. The elements in h . . . the d1 column, however, are either 1 or zero, depending on node d’s instantaneous connectivity with the other nodes as expressed above in Eqn. 7.5. Second, the summation 170 of all elements in a row should be 1. The Forwarding Matrix, which depends on the link states Li, j (n) , can be created afier the forwarding probabilities are computed using Eqn. 7.5 based on the observed link states from the collected WBAN topology traces. . . . th . Consrder a data packet that rs generated at node 3 during the n time slot, and delivered to node d at the (n+k)th time slot, resulting in a delay of k slots. The value of k can vary from O to infinity. Let the probability of the above event (i.e. delivering the packet with a delay of k slots) be represented as the delivery probability [9:0, 0‘) , which can be expressed as: k pgd (k) = [A(n).A(n +1) ..... A(n + 10]“, = H A(n + i) (7]) i=0 s,d which is the [s,d] element of the product matrix. Therefore the expected RAND . th . . forwarding delay for a packet that was generated at the n time slot can be written as: T T k _ n _ ° DRAND “ Zk°ps,d(k) ‘ 2]" HA“ H) (7.8) k=0 k=0 i =0 s,d where T is the length (in number of slots) of the experimental topology traces obtained in Section 7.2. Considering sufficiently long on-body topology traces (i.e. large T), the maximum value of k in Eqn. 7.8 is set to be T instead of infinity. To clarify the above forwarding concept further, let us explore the following example. Consider a 4-node (i.e. N= 4) body sensor network with node-1 as the source and node-3 as the destination. Example forwarding matrixesA(1) , A(2) and A(3), and the 171 corresponding network topologies at time slots 1, 2 and 3, obtained from the topology trace, are given by: 00500.50 0 00010 0 1000 0010 A(l)=0000 ’A(2)=0000 ’ L0010_9 9 050.5009 9 '0010‘ A3_001oo o ()"0000 _0010_9 9 Matrix products [A(l)oA(2)] and [A(l)-A(2)-A(3)] are: '025 0.25 0.5 0‘ o o 0.5 o [A(1)-A(2)]= O 0 0 1 and [A(1)-A(2)-A(3)]= 0 O 1 O 0 0 0 o 0 0 o 0 . _ 0 o 0 0- _0 0 0 0_ Using the above matrixes, the delay probabilities can be computed as: [711,3 (0) = 0, [212,3 (1) = 0.5 and [213,3 (2) = 0.5 using Eqn. 7.7. According to A(l), at time slot 1, node-1 has two neighbors (2 and 4), node-2 has one neighbor (node-l) and node-4 has a direct connection with the destination node-3. Assume that a packet is generated at source (node-1) at time slot 1. Since node-1 has no direct connection with d (i.e. P1,]; = 0 ), the packet will be randomly forwarded to either node 2 or 4 with probability 0.5 each, but the probability of delivering it to the destination node-3 is zero in the current slot-l (out of all possible infinite number of slots in future). This is captured by [)1]; (O) = 0 which is the [1,3] element of matrix A(I). 172 At time slot 2, the packet will be forwarded to 3 through 2 with probability 1, that is if 2 has already received the packet in slot 1. Otherwise (i.e. the packet was forwarded to node 4 in slot 1), the packet will be forwarded to node-l or node-2 by node-4 at slot 2. Therefore, the probability of delivering the packet to the destination node-3 in slot-2 (out of all possible slots) is 0.5. This is captured by [)1]; (1) = 0.5 from the [1,3] element of the product matrix [A(1)- A(2)]. Since Pl,j3 = {3 = P 41:3 =1 in A(3), the packet is guaranteed to be delivered to node-3 in slot-3. Since the probability of delivery in slot-1 was zero, and in slot-2 was 0.5, and the delivery is guaranteed in slot-3 (i.e. if it was not delivered in slot-2), the probability of delivering the packet in slot-3 (out of all possible slots) is 0.5. In other words, the probability of delivery with a delay of 2 slots (i.e. k=2) is 0.5. This is also captured as [9113(2) =05 from the [1,3] element of the product matrix [A(l)-A(2)-A(3)] . Using p113 (0) = 0, p113, (l) = 0.5 and p11} (2) = 0.5 , the expected delay for random forwarding for this example WBAN topology trace is 0x0+1x0.5+2x0.5=1.5time slots. 7.3.3 Utility-based Routing using Link Locality In randomized routing, a node does not consider the locality of its connectivity with other network nodes wile forwarding a packet. In utility-based routing protocols [74],[110],[116],[108],[109] nodes prefer to forward packets to destination through the neighbor with the latest encounter with the destination, thus leveraging the link locality in the form of its age. Each node is assigned a utility value based on the last encounter time 173 with the destination, and a packet is forwarded to a neighbor with the highest utility value. Utility represents how useful (fast) this node might be in delivering a data packet to the destination, and is often implemented using a timer. Let the utility function U ,3 j (n) represent the utility value of node i with respect to node j at the n trme slot. Every trme node 1 comes 1n contact wrth node j, the quantity U i, j (n) is set to a maximum utility value and then for every time slot the node remains out of contact from the destination, the quantity U ,3 j (n) is decreased based on a pre-set utility reduction method [116],[109] as a function of elapsed time. The update rule for U131“) can be written as: U , i L- - n+1 =1 Ui, (n+1): max f "1( ) (7.9) where Umax is the maximum utility value to the destination each node can has. These utility values are exchanged between neighbors within the periodic Hello messages. With the above definition of utility, at the nth time slot node-i will forward a packet (destined to node-d) to node-j only if Ui,d (n) < U jad (n) and U 13d (n) 2 Ukfl (”XV/C E Viol) , where V1,: (72) is the set of all neighbors of node-i during the nth time slot. Note that the above forwarding logic assumes that each on-body node is guaranteed to intermittently come within up to 2-hop contact from the destination node. In other words, a source node is intermittently able to see other nodes that intermittently come in 174 direct contact with the destination node. In our experimental topology this assumption was always found true [121]. In fact for a WBAN topology, it is generally true that depending on the specific postural patterns, all nodes intermittently form direct links with all other nodes in the network. This observation makes the assumption generally applicable for WBANS which usually have a small network diameter [116],[109]. The packet routing delay in utility-based forwarding (UTILITY) can be computed using the same logic as in random forwarding (RAND) except that the forwarding probabilities Bf, (n) in Eqn. 7.5 need to be reformulated for UTILITY. The forwarding probability in this case can be expressed as: 13.502) =1and 13.5.01) = 0, Vj ¢ i e NifUi,d(n) 2 Uj,d(n),Vj awn) 13.5. (n) = 1 and 113.5(1)): 0 if Ui,d(n) < Uj’d(n) and Uj’d(n) 2 Uk,d(n), Vk El/ll-(n) and Vr¢j EN fig(n)=1and g{}(n)=0,Vj¢d eNifd «am-(n) (7.10) where N represents the set of all on-body nodes and where V401) is the set of all neighbors of node-i during the nth time slot. The top line of Eqn. 7.10 represents a srtuatron 1n WhJCh e1ther node-z does not have any nerghbor dunng the n trrne slot, or 1ts own utility to the destination node-d is higher than those of all its current neighbors. Either way, the node buffers the packet with probability 1. The middle line of the equation codes the utility-based forwarding rule as stated after Eqn. 7.10. The bottom line represents the situation in which the destination node-d is a direct neighbor of node-i, causing a direct delivery. 175 Once the forwarding probabilities are computed applying Eqn. 7.10 on the on-body topology traces collected in Section 7.2, the forwarding matrix A(n) and the delivery n probabilities ps,d (k) are computed using the same rules presented in Eqns. 7.6 and 7.7. Finally, the delivery delay is computed using Eqn. 7.8 as T k DUTILITY = 2k- HAM“) k=0 i=0 s,d 7.3.4 Probabilistic Routing with Postural Link Cost (PRPLC) Routing using PRPLC utilizes a Postural Link Cost (PLC) [120] which captures WBAN link localities in multiple time scales. PRPLC routing protocol is discussed in Chapter 6 and Section 6.4.2. We redefrne this protocol in this chapter to construct the overall analytical model of this protocol. For on-body packet forwarding, the PLC is used exactly the same way as for the UTILITY routing; that is by replacing the utility values by the PLCs. The routing mechanism of this routing protocol is summarized in the pseudo-code presented in Figure 6.6. With posture and activity changes of a human subject, the PLC link costs are automatically adjusted such that the packets are forwarded to next-hops which are most likely to provide an end-to-end path with minimum intermediate buffering/storage delays. PLC is defined as ,6”- (n) , (05,3),1- (”)51) , which is similar to the Link Likelihood Factor (LLF) that is defined in Section 6.4.2. It represents the probability of frnding L, I") =1. The update equations for PDC are .1 formulated as in Eqn. 6.1 [121],[120],[122]: 176 fli,j(n)=fl,~,j(n)+(l—fli’jm_1)).w iflink LU (n):1 fli,j(n)= .3“- (n —1)-a) iflink L13} (,1) = 0 (7-11) According to Eqn. 7.11, when the link is connected, the Postural Link Cost (PLC) fli, j (71) increases at a rate determined by the constant a) (0 S a) S 1) , and the difference between the current value of ,6,’ J- (n) and its maximum value, which is 1. As a result, if the link remains connected for a long time, the quantity 161', j (n) asymptotically reaches its maximum value of 1. When the link is disconnected, 161', j (n) asymptotically reaches zero with a rate determined by the constant a). To summarize, for a givena) , 16,-, j(n) responds to the instantaneous connectivity condition of the link Li, j . With time invarianta) , the PLC update rules in Eqn. 7.11 captures the locality in short-term link connectivity in a manner conceptually similar to the age-based utility formulation, as developed in [109],[116]. It is, however, not the same because in the designs in [109],[116], the routing utility of a link is increased incrementally when the link is formed, and is reduced to zero as soon as the link is disconnected. This formulation of utility misses out the fact that even after disconnection, the formation probability of that link may be higher than a currently-connected link. In other words, those definitions of utility fairly differentiate across currently connected links, but not across the currently non-connected links. In the formulation of PLC in Eqn. 7.11, motivated by the logic used in PROPHET [74], we track the short-term locality even when a link is not physically connected. This extended persistency in PLC is expected to 177 improve performance over the existing age-based utility definitions as used in [109],[116]. The next design step is to dimension the parametera) for capturing link localities at a longer time scale. From Eqn. 7.11, the rate of change of the PLC per time slot can be written as: mid-(on (1-fli,,-(n-1))-w iflink L.,,- (n) =1 (7.12) §(,Bi,j(n))=—,Bi,j(n-1)-(1—a)) iflink Lid- (n) = 0 Eqn. 7.12 indicates that for a high a) (e.g. 0.9), ,Bw-(n) increases fast when the link is connected, and decreases slowly when the link is not connected. Conversely, for a lowa) (e.g. 0.1), ,6,”- (n) increases slowly when the link is connected, and decreases fast when the link is not connected. Ideally, it is desirable that for a historically good link (i.e. connected frequently on a longer time-scale), 4.1“) should increase fast and decrease slowly, and for a historically bad link, it should increase slowly and decrease fast. This implies that the parameter a) needs to capture the long-term history of the link; hence it should be link specific and time varying. Based on this observation, we redefine the Historical Connectivity Quality (HCQ) of an on-body link Li, j at time slot n as: n 0),” (n) = Z Li,j (r) T window (7.13) r =""T window The constant T window represents a measurement window (in number of slots) over which the connectivity quality is averaged. The factor 178 (01-d- (n), (0 S (Oz-,1- (n) S 1) indicates the historical link quality as a fraction of time the link was connected during the last T window slots. The parameter T window should be chosen based on the human postural mobility time constants. Experimentally, we found the optimal T window values that work well for a large number of subject individuals and range of postures to be in between 7 sec. and 14 sec. 1 ::::::::A .1 ON "a 1.31 Li,j(n) 0’ 7 HCQ :3 U 0.6 A I 0.4 — 0.2 ~ _ 0 fi vececcettceeeceeY} -; OFF 0 l 0 20 30 40 50 Time Slot Figure 7.4: Evolution of multi-scale locality in terms of PLC and HCQ Figure 7.4 shows the evolution of PLC )6”- (n) and HCQ (1),-J (n) with time. The top graph shows an example link activity (indicated by L,- (n)) with the first half indicating a steadily connected link with a single time slot (1.4 sec.) of disconnection at time slot 10, and the second half indicates a steadily disconnected link with single slot of connection at the 41St slot. The top graph also shows the evolution of 179 50,” (n) according to Eqn. 7.13 with a T window set to 7 time slots. The bottom graph shows the evolution of '61}! (n) with constant a) (i.e. 0.9 and 0.1) and link-specific time varying (0),,- (n) from Eqn. 7.13, indicating the historical link quality. When the link is steadily well connected (during the first half), a high constant a) (i.e. 0.9) responds well to a momentary disconnection by decreasing ,6- (n) slowly, but 1,] recovering quickly when the link becomes reconnected. A low constant a) (i.e. 0.1) responds poorly in this situation by doing just the opposite - that is a fast decrease and slow recovery. Similarly, when the link is steadily disconnected (during the second half), a low constant a) (i.e. 0.1) responds relatively better than a high constant a) (i.e. 0.9) by increasing fli,j(") slowly for a momentary connection, and decreasing fig, 11”) quickly after the link becomes disconnected. The lines for two constant a) values clearly show that a single constant value for a) is not able to handle both good-link and bad-link situations equally effectively. As hypothesized, the link-specific and time-varying ,5}, j (n) , on the other hand, is able to handle both situations well by mimicking the behavior of a) = 0.9 during the historically good-link situation, and that of a) = 0.1 during the historically bad-link situation. These results clearly demonstrate the effectiveness of the HCQ and PLC concepts for designing routing utilities that can capture both short and long term localities of the on-body link dynamics. With this multi-scale approach, the proposed mechanism 180 should be able to outperform both age-based (UTILITY) [109],[116] and probabilistic [74] routing protocols that use only short term locality information. UTILITY Utility function U(0 PLC Computation Model ch Routing Decision M . Short-term locality I Capturing short- and long-term localities Figure 7.5: Capturing link connectivity locality in PRPLC and UTILITY age-based routing. Note that unlike the entities in Figure 6.2 and Figure 6.3 in Chapter 6, the PIC and HCQ in Figure 7.4 show the link connectivity localities which depends on the short and long term history of the link. The localities captures in Eqns. 7.11 and 7.13 are responsible for this memory-based behavior in Figure 7.4 in contrast to the instantaneous link behavior in Figure 6.2 and Figure 6.3. Figure 7.5 summarizes the structural difference between PRPLC [122] and the UTILITY [109],[116] age-based protocol from the link locality capture standpoint. As shown in the figure, while UTILITY extracts only 181 short term locality from the link on-off dynamics, PRPLC extracts an additional long term locality by observing the Historical Connectivity Quality (HCQ) as presented in Eqn. 7.13. The forwarding rule in PRPLC is identical to what stated for UTILITY-based forwarding in Section 7.3.3 with the utility function U i, j (n) replaced by the postural link cost flu (’1). Consequently, the forwarding probabilities Pg]- (n), the forwarding matrix A(n), and the delivery probabilities P: d (k) can be computed using Eqns. 7.6, 7.7 and 7.10 respectively, and finally, the end-to-end packet delay can be computed using T k Eqn. 7.8 as DPRPLC = 2k. HAW”) k=0 i=0 S,d 7.3.5 Distance Vector Routing with Postural Link Costs (DVRPLC) In DVRPLC, nodes maintain end-to-end cumulative path cost estimates to a common sink node, as defined in Chapter 6 and Section 6.4.4. Where the Link Cost Factor (LCF) is defined as Cid- (n), O S CiJ (n) S Cmax which represents the routing cost for the link LU (between nodes i and j) during the discrete time slot 12. The update equations for LCF are formulated as [121],[120],[122]: Ci,j(n)=Ci,J-(n—l)-(1—a)i,j(n)) iflink Li,j (n) =1 , (7.14) Cid. (n)=Ci,j (n — 1) +(Cmax —C,.,J. (n —1))-(1—(ol-’j(n)) iflink Lid- = 0 182 When the link is connected, CM (71) decreases at a rate determined by (1‘60“- (n)) , where wiJ (n) , (0 S a),.,j(n)51) is the Historical Connectivity Quality, as defined in Eqn. 7.13. If the link remains connected for a long time, the quantity C i, j (n) asymptotically reaches its minimum value 0. When the link remains disconnected, C ,3 j (n) increases at a rate determined by the quantity (1 “60,3,- (n)) , and the difference between the current cost C13; (n) and its maximum value 1. This formulation ensures that a link’s routing cost always reflects the likelihood of the existence of the link while capturing its historical connectivity trends. Note that the time evolution of LCF in DVRPLC follows a rationale that is very similar to that of PLC in PRPLC. The main difference is that while the LCF reduces for connected links, the PLC increases in such situations. Similar difference exists when a link remains disconnected. To summarize, like in PRPLC,Ithe cost in DVRPC captures both short and long term link localities for minimum delay packet routing. Let 7,4101) be the minimum end-to-end cumulative cost from node-i to the sink node-d. According to distance vector routing logic, when a node i needs to forward a packet to the sink node d, and it meets a node j, the packet is forwarded to node j only if the condition 713d (71) < 7i.d (n) is found true. In other words, a lower path cost through node j indicates that the latter is more likely to forward the packet to node d than what node i’s chances are. That justifies the packet transfer from node i to j with a goal of minimizing the end-to-end packet routing delay. The forwarding mechanism of this protocol is summarized in the pseudo-code presented in Figure 6.7. 183 Note that the DVRPLC protocol attempts to minimize end-to-end cumulative routing costs. The objective is that due to this end-to-end cost minimization, DVRPLC should be able to outperform (from a delay standpoint) PRPLC which always interprets its PLC only at the link level and not in an end-to-end cumulative manner. To execute DVRPLC, each on-body sensor node-i uses the periodic Hello mechanism, in order to gradually develop the C ,3 J- (n) values with all other nodes in the network. It also iteratively updates the quantity 7,3,1 (’1) using the computed CL} (11) values with respect to all its neighbors. The node then uses the Hello mechanism to send the quantity 7M (n) , its end-to-end cumulative path cost to the common destination node-d (e. g. node 6 in Figure 7.1), to all other nodes that are currently connected to node—i. This way, each node gets updated about the path costs of all of its direct neighbors’ to the common destination node-d. The update equation for 7,3,, (11) : r.,.(n)=min(r.,.(n), r.,.(n)+C.,.(n>) (7.15) where node-k has the minimum 719d (’1) among all the current neighbors of node-i. Because of its end-to-end nature, the forwarding rule in DVRPLC is based on the end-to-end cost 7,3,1 (n) as opposed to based on local parameters U i, J- (n) or ,3,, j (n) as used in UTILITY and PRPLC both of which do not rely on end-to-end cost. The distance vector forwarding rule for a packet from node-i to destination node-d can be formalized as follows. If node-i is a direct neighbor of node-d, forward the packet. Otherwise find node-k such that node—k has the minimum 71,401) among all the current neighbors of 184 node-i. Then forward the packet to node-k only if 7”, (n) < 7,3,, (n); otherwise, continue buffering the node as node-i. With this forwarding rule, the forwarding probabilities Bf,- (n) can be expressed as: Pif;,(n)=1and 115(n)=0,vj° ¢i,d e NifLLd(n)=1 13.5,(n)=1 and 13f;(n)=o,v)° ¢i,k eNij’Li,d(n)¢1and 7k,d(")<7i,d(") andyk,d(n) S 7r,d,Vr e 911,-(n),r ¢ i,d,k e N (7.16) fl§(n)=land 133(n)=0,Vjad,ieNthi’d(n)¢1and 7k,d(") 2 7i,d(") andykfl (n) S yr,d,Vr e wi(n),r at i,d,k e N where N represents the set of all on—body nodes and where W11") is the set of all neighbors of node-i during the nth time slot. The forwarding matrix A(n), and the delivery probabilities p: d (k) can be computed using Eqns. 7.6 and 7.7 respectively, and finally, the end-to-end packet delay can be computed using Eqn. 7.8 as r k DDVRPLC = Zk{HA(n+i)] . .gd k=0 i=0 7 .4 Routing Delay Benchmark In order to determine the best case end-to-end delay performance, an offline route search algorithm, Backward Search for Delay Benchmark Routing (BSDBR) has been used, which is same delay benchmark routing used in Chapter 6. As long as the entire topological sequences for a dynamically partitioned network are known a priori, the BSDBR algorithm is able to compute the most delay optimal end-to-end path for each packet depending on its source, destination, time of origin, and the complete topological 185 sequence information. BSDBR is designed to be an offline centralized search algorithm, to be executed in the presence of entire time series topology information. Let t0 be the time instant at which a packet is generated at node-i and routed towards destination node-d. Given a known topology sequence, the objective is to find the earliest time instant afler to at which the packet can be delivered to the destination. Let t] be the earliest time instant (t1 > to) at which destination node-d comes in contact with any other node-j (j e N, j 7* d ). The minimum possible delivery delay for the packet originated at time t0 can be written as (t1 - to). This minimum delay is possible only if the necessary network links are formed across the network during the time interval [to to t1] so that the packet could be forwarded multi-hop all the way from the origin node-i to node-j before time t]. The objective of BSDBR search process is to scan the network topology sequence in order to find if such link formations are there so that (t1 - to) can represent the minimum packet delivery delay. If the search process concludes that the packet cannot be delivered by time t’, then the next feasible time instant t2 is identified and a similar search is conducted to determine if (t1 - to) can be the minimum delivery delay. The quantity t2 is the earliest time instant afier tl ((2 > t!) at which destination node-d comes in contact with any other node-j (j EN, j at d). This BSDBR search process is iteratively continued till a valid minimum delivery delay (tr- to) is found. The time instant tr corresponds to the earliest contact time so that the necessary network links are formed across the network during 186 ,4 the time interval [to to tr] so that the packet can be forwarded multi-hop all the way from the origin node-i to destination node-j by the time tr. Note that the expected value of the packet delay lower bound could have been computed using the Linear Programming formulation as adopted in the full knowledge-based approach in [113]. Instead, we have chosen to implement BSDBR since it allows us to determine the minimum packet delay for each individual packet as opposed to their average in a statistical sense, as we discussed in Chapter 6. Also, the formulation in [113] is more complex than BSDBR since it incorporates the effects of message queuing which is not studied in our implementation. 7.5 Performance Evaluation The same seven-sensor laboratory prototype network, as shown in Figure 7.1, was used for the on-body experimental evaluation of all the analyzed routing protocols. Packets originated from all sensors were routed to the common destination node-6, attached on the right ankle. Unless stated otherwise, results correspond to packets originated fiom node-3, representing the longest hop (i.e. also worst case) packet routing scenario in most of the body postures. Results are also presented from off-body simulation experiments, carried out on network topology traces collected during the actual on-body experiments so that the simulation results can be compared with the experimental data for the exact same topology traces. Those traces are also used to create the forwarding matrix in Eqn. 7.6 for computing the analytical packet delay numbers for all the analyzed routing protocols. In order to avoid the CSMA MAC collisions inherent to Mic2Dot’s TinyOS networking stack, we have implemented a higher layer polling access strategy managed 187 by one on-body node similar to the polling mechanism that is described in Section 6.5.1. This polling node polls the other six sensor nodes in a round-robin fashion, so that a regular node forwards packets (both data and Hello) only when it is polled by the polling node and given access to the channel. A polling time frame of 1.4 sec. is used which is divided into 7 time slots, one for each of the seven on-body nodes. Note that the polling node itself also needs to send Hello packets etc. for link cost formulation as described in Section 6.3. Although the data packets and the Hello messages from the nodes are transmitted at software power adjusted transmission range of 0.3m-0.6m, the polling packets are transmitted by the polling node at full power so that all on—body nodes receive such packets. If a node misses a polling packet in a frame due to channel error, it misses transmission opportunity only in that frame. 7.5.1 Performance Metrics The primary performance index is the end-to-end Packet Delay (PD), which is modeled in this chapter and is attempted to be explicitly minimized by the UTILITY, PRPLC and DVRPLC protocols as presented in Sections 7.3.3, 7.3.4 and 7.3.5. Unlike in conventional un-partitioned networks, the PD in partitioned on-body networks depends mainly on the storage delay at the intermediate nodes. Two secondary metrics, namely, Packet Hop Count (PHC), and Packet Delivery Ratio (PDR) are also recorded for a more complete understanding. The index PHC captures the number of transmissions per packet forwarding, indicating the energy expenditure; it does not indicate the packet delay since the PD in this context depends more on the buffering/ storage than the hop-count. 7.5.2 Traffic Generation and Data Collection A chosen source node is programmed to generate data packets at the rate of 1 packet every 4 discrete time slots (each slot is 1.4 see), with a packet size of 46 bytes. As in 188 '1"- Chapter 6, all on-body network nodes are slot-level time-synchronized by the sink node (i.e. node-6 in Figure 7.1) using periodic synchronization packet broadcast at a high transmission power [120]. By stamping a packet with the transmission time slot-id by the source node and subtracting it fiom the reception time slot-id at the sink node, it is possible to compute the single—trip packet delay (PD) at the sink node. On its way to the sink node, a data packet collects the entire route information in the form of a list of the intermediate node-IDs. This allows the extraction and analysis of route information including the PHC values. 41.22\ -.—-/42.56 43.2 12 / u—n O Average Delay (3) 4} 0) 00 N O OPPT. RAND. UTILITY PRPLC DVRPLC BSDBR Figure 7.6: On-body packet delivery delay for different DTN routing protocols 7.5.3 Packet Delay (PD) End-to-end packet delivery delays for a packet from the source node-3 on left upper arm to the sink node-6 on right ankle for all routing protocols analyzed in Section 7.3 are reported in Figure 7.6. For each of these protocols, a separate experiment was run for 1320 sec. (i.e. 22 minutes), sending 230 packets, and spanning 6 different body postures and activities (SIT, SIT-RECLINING, LYING-DOWN, STAND, WALK and RUN), each lasting for 20 sec. Figure 7.6 reports the average of packet delay computed from the 189 analytical model, on-body experiment, and off-body simulation using network topology traces collected during the on-body experiments. The figure also shows the delay lower-bound obtained by applying the BSDBR benchmark algorithm (presented in Section 7.4) on the topology traced collected from on-body experiments. The following observations are be made in Figure 7.6. First, the experimental, simulation, and model-generated analytical results closely matched across all protocols. Second, as a general trend the delay performance improves with the amount of knowledge leveraged on topological locality. Both PRPLC and DVRPLC achieve significantly better delay compared to the other protocols and very close to BSDBR benchmark delay, because they are able to capture multi-scale topological localities in human postural movements using the cost parameters 161.1 (n) and C,j (n) , as explained in Sections 7.3.4 and 7.3.5. The age-based approach UTILITY uses only the short-term locality, which explains its larger delay compared to PRPLC and DVRPLC, but smaller delay than OPPT and RAND, both of which do not leverage any topological locality information and responds based solely on instantaneous link conditions. Randomized forwarding provides slightly better delay since in a typically small WBAN, there are only few possible end-to-end path combinations, leading to quicker delivery than the Opportunistic mode in which a delivery is possible only when the source directly meets the destination. 7.5.4 Packet Hop Count (PHC) Figure 7 .7 shows the average PHC which serves as an indirect measure for communication energy expenditure (i.e. for transmission and reception) for the on-body sensors. The large number for RAND explains the impacts of random forwarding 190 compared to all other protocols. The protocols DVRPLC and BSDBR take slightly longer routes compared to the other protocols, although those two offer better packet delays. This means that they route packets through better quality links, leading to smaller delays, even though it requires more number of end-to-end hops. Since with the opportunistic routing (OPPT) packets are delivered only when a source comes in direct contact of the destination, all packets are delivered with PHC l. 4.15 Packet Hop Count (PHC) OPPT. RAND. UTILITY PRPLC DVRPLC BSDBR Figure 7.7: Average Packet Hop Count 7.5.5 Packet Delivery Ratio Since no link layer packet retransmissions are deployed, the system is not able to recover from the packet drops observed due to the following reason. Due to postural mobility, there are transient blackout periods during which a neighbor may appear to be connected in a node’s neighbor table, when in fact it is no longer connected. These blackout periods are created during a node’s neighbor time-out period, which was chosen to be two polling frames or 2.8 sec, as reported in Section 6.3.2. Packet transmissions during such blackout periods end up in packet drops since no link layer reliability is used. 191 All five evaluated protocols suffer from such packet losses, which are captured in the Packet Delivery Ratio (PDR) as reported below. 90% 89% ratio 85% ry OO ‘3 e\ Packet Delive 75% 71% 0 70 /° OPPT. RAND. UTILITY PRPLC DVRPLC Figure 7.8: Packet drops observed for different protocols In Figure 7.8, the poor PDR for the OPPT protocol is caused due to a very unreliable link between the source and the destination nodes (i.e. nodes 3 and 6 in Figure 7.1) which are physically situated at two extremes of the subject’s body. Since the OPPT protocol relies on direct source-destination contact for packet delivery, the source-destination link quality affects this protocol most. For RAND, since the hop count is large (see Figure 7 .7), it is more likely for a packet to encounter the transient blackout period during its end-to-end trajectory, thus leading to higher drops and low PDs. Lower h0p-counts (see Figure 7.7) for the locality-based protocols, namely, UTILITY, PRPML, and DVRPLC, suffers from fewer drops due to the relatively lower occurrences of the transient blackouts. Note that the concept of such drops does not apply for the Benchmark case, and that is why there is no entry for BSDBR in Figure 7.8. 192 7.5.6 Routing Packets from and to Different Body Segments Delivery delay computed using the developed model and from on-body experiment for packets from different body segments to the sink node placed on the right ankle (i.e. node 6 in Figure 7.1) are shown in Figure 7.9. As shown in the figure, the experimental and model-generated analytical results closely match across all protocols. Observe that as the physical distance between a source and the destination increases, the average packet delivery delays for all the protocols increase. Relatively though, all the experimented routing protocols maintain the same trend for the packet delay as observed in Section 7.5.3. The average packet hop-counts from source nodes 5, 1, and 3 were experimentally logged in the range of 1.25, 1.5, and 2.3 respectively. I OPPT. Online 43.2\.. /41 .22 Ir. y}; a DVRPLC Online 1 5 _ ca OPPT. Model sass » a RAND. Online 3% 1:31;: ’t'o‘ _ In RAND. Model 53351 it? v 12 as has >. : 11111.er Online ,, 2’s: 2 are :\ o 9 _ 121 UTILITY Model gas; :9: e E1 PRPLC Online get) $135 mi!» ,\’§\‘ 5,? [ll PRPLC Model 4% g < ,. E DVRPLC Model ”gem:- _.' ,' 3 . 3:3:1 :-:w._ '-'-': ‘-— W‘s“ .-..:’4= :::: '.-.'I’= iii; '.'..':"= /:::: _ . 5:23:53; 5 iii? :-:'§$i§ flags Src= 5(LeftThigh) =1(Waist) (Up perLeftArm) Figure 7.9: Delivery delay for packets from thigh, waist and arm to right ankle Delivery delay for packets fiom the upper left arm (i.e. node 3) to different body segments are shown in Figure 7.10. It should be noted that although the absolute delay values are different, the overall trend in packet delay follows the same pattern for all the sink nodes that we have experimented with. 193 I OPPT. Online 15 _ OPPT. Model B RAND. Online 1!] RAND. Model E UTILITY Online E UTILITY Model E PRPLC Online ’. y "’I‘w' 111‘ 1 Average Delay (5). \O u PRPLC Model fig 6 - :1 DVRPLC Online iifi§ 1:11 DVRPLC Model K§ _ :3??? if? Sink = 2 (Upper Right Arm) Sink = 5 (Left Thigh ) Sink = 6 (Right Ankle) Figure 7.10: Delivery delay for packets to arm, thigh and ankle from the upper left arm (i.e. node 3 in Figure 7.1) 7.5.7 Impacts of Postural Stability For all the experiments so far, each individual physical posture was made to last for 20 sec. In order to study the impacts of variable postural stability on the routing performance, the subject was instructed to repeat the same sequence of postures as in Section 6.3, but with different posture durations ranging from 10 sec. to 40 sec. 18 s OPK »; RAND. -~ 50,5). 5* 14 ~ g) S 40:13 no . 1 1 an 2 0 E U‘l‘lLlTi _, 302 E 1—3 o . 4.3 6 — __ “r O s #gmkfl’fl 20% . m—«~—~ 2 ‘" \DVRPDC 10 10 20 Posture Duration (3) 30 40 + DVRPLC Online + DVRPIJC Model + PRPLC Online + PRPIII Model “'9" UTILITY Online 7—9" UTILITY Model —B- RAND. Online ‘43— RAND. Model + OPPT. Online ‘79— OPPT. Model Figure 7.11: Impacts of posture duration on packet delay 194 Figure 7.11 shows the impacts of posture duration on average packet delay for all five protocols. Due to its significantly higher values, the packet delays for the OPPT protocol are plotted as a separate axis in Figure 7 .1 1. Observe that the packet delays for all the protocols generally increase with higher posture durations. This is because longer posture duration implies that a connected link remains connected for longer duration and also a disconnected link remains disconnected longer. As a result, a packet that is buffered in a node due to network partitioning remains buffered for longer duration, leading to higher end-to-end delay. In a relative sense, all the experimented protocols maintain the same performance trend for packet delay as observed in Section 7.5.3, Figure 7.6. Figure 7.12: Experiments with different sensor placements 195 (a) 16 E g Online g 12 IModel Q go 8 ’12 < 4 0 OPPT. RAND. UTILITY PRPLC DVRPLC 26.44\ : /24.91 16 b 3 ( ) EOnline g,» 12 IModel g 8 0 3’ ’9 < 4 0 OPPT. RAND. UTILITY PRPLC DVRPLC Figure 7.13: On-body packet delay for: (a) sensor placement P 1 , and (b) sensor placement P2. 7.5.8 Impacts of Sensor Placements Additional on-body sensor placements, as shown in Figure 7.12, were experimented with for evaluating the validity of the routing results obtained so far fi'om the sensor placement shown in Figure 7.1. Different source and sink nodes are used in the two placement settings P1 and P2 in Figure 7.12. The inter-posture sequence, described in Section 6.3.2, was followed by a subject and the corresponding packet delay results are presented in Figure 7.13 for the placement settings P1 and P2 in Figure 7.12. Generally, the relative performance trends across all the experimented protocols as observed for the original sensor placement (in Figure 7.6) remain valid for the new sensor placements P1 196 and P2 in Figure 7.12. The delay for placement P1 is larger due to the longer source-to-destination distance compared to that in P2. 7.6 Evaluation of Node Criticality The objective of this section is to evaluate the topological criticality of the individual WBAN sensor nodes. Once identified, such criticality information can be used for selectively reducing the on-body sensor-count without substantially sacrificing the packet delivery delay. The mechanism for such analysis is to first remove all links attached to a given sensor S from the collected topology trace (see Section 7.2), and then run off-line routing simulation experiments to evaluate the new delay on this reduced network. Comparison between the delays from the original trace and this reduced trace would indicate the topological criticality of the target node S from a routing standpoint. The above mechanism is applied to the 7-node WBAN with node-3 as the source and node-6 as the destination as shown in Figure 7.1. Figure 7.14 shows the resulting end-to-end packet delay characteristics when a specific node (chosen from the set 1, 2, 4, 5, and 7) is selectively removed from the network under different routing protocols. Figure 7.14:3 shows the new delay after a node is removed, and Figure 7.14:b shows the difference between the new delay and delay obtained from the complete topology without any node removed. The latter indicates the topological criticality of the removed node from a routing standpoint. A positive low difference in Figure 7.14:b would indicate that the removed node is not particularly critical for the corresponding routing protocol. Conversely, a positive high difference would indicate that the removed node is critical. A negative difference actually means that the routing performance has improved after the node is removed. Meaning, the corresponding routing protocol was non-optimally 197 choosing the node after removing which the routing protocol actually. found a better route, leading to lower delay. Results for all the analyzed protocols except opportunistic routing (OPPT) are presented in Figure 7.14. Since OPPT relies on direct source-destination contact for packet delivery, removal of any intermediate node from the topology does not impact the delivery delay, which is why it is not included. 16 GRAND. QUTILITY EPRPLC .DVRPLC [DBSDBR 1—1 h u—ot—i ON Average Delay (5) ONhONOO All nodes n-l remvd. n-2 remvd. n-4 remvd. n-5 remvd. n-7 remvd. |IRAND.EIU'111r1Y EPRPLC IDVRPLC IrBSDBfl (b) t" 5° 9° .1: 4> A l l 1 Delay Difference (s). .O b l -0.6 ‘ All nodes n-l remvd. n-2 remvd. n-4 remvd. n-S remvd. n-7 remvd. Figure 7.14: Node criticality in terms of: (a) Packet delay, and (b) Packet delay difference Observe in Figure 7.14:b that removing a node from the network creates different amount of delay difference depending on the specific routing protocol. Note that for the 198 age-based UTILITY-based routing the delay difference is negative, although small, when any of the nodes 1 or 2 is removed. This indicates that UTILITY was non-optimally choosing those two nodes and by removing any of them is forcing the protocol to choose a better route, resulting in negative difference. This inaccuracy is introduced by the short-term-only connectivity locality in the protocol. On the other hand, by leveraging both short and long term connectivity locality, as introduced in Sections 7.3.4 and 7.3.5, the protocols PRPLC and DVRPLC completely eliminates the negative differences, meaning they always choose an optimal route through nodes removing which actually worsens the delay. Similarly, in Figure 7.14:b the BSDBR algorithm with benchmark delay also demonstrates optimal routes indicated by no negative differences. Finally, observe that the node dependencies of the RAND is generally more than all other protocols mainly because with randomized forwarding any node in WBAN can be in a packet’s path as described in Section 7.3.2. From the above specific analysis and the results in Figure 7.14:b, the following conclusions can be made. First, if PRPLC or DVRPLC (these two provides the best end-to-end delay as shown in Figure 7.6) is deployed, one node from the set 1, 2, and 7 can be easily removed without sacrificing packet delay. Second, generally, nodes 4 and 5 are topologically more critical than all other nodes (in the context of source 3 and destination 6) primary because of their physical proximity to the destination and physical placement with respect to possible routes from node-3 to node-6. Note that the analysis in his section shows what happens if only one node is removed from the topology. In order to find the impacts of removing multiple nodes, similar analysis is needed by removing different combinations of the nodes and then by measuring the delay differences. Also, 199 removal of a node will be feasible only if the primary purpose of the node is routing and not sensing. 20 ES RAND. (a) A m 1117le £316 a PRPLC E DVRPLC a 12 m Bmark D g0 8 13' > <1 4 0 All 1.2 1.4 1.5 1.7 2.4 2.5 2.7 4.5 4.7 5.7 rs RAND. 10 15 UTILITY (b) r; a PRPLC E 7 DVRPLC 8 ll] Bmark ‘5 4 a Q 1 32‘ a-Z -5 All 1.2 1.4 1.5 1.7 2.4 2.5 2.7 4.5 4.7 5.7 Figure 7.15: Two node criticality in terms of: (a) Packet delay, and (b) Packet delay difference Figure 7.15 shows the resulting end-to—end packet delay characteristics when two nodes (chosen from the set 1, 2, 4, 5, and 7) are selectively removed at a time. Figure 7.15:a shows the new delay and Figure 7.15:b shows the difference between the delays new delay and delay obtained from the complete topology without any two nodes removed. As in Figure 7.14:b, Figure 7.15:b indicates the topological criticality of the removed two nodes fiom a routing standpoint. For example, with PRPLC or DVRPLC routing in place, removal of any of the node pairs {1, 2}, {1, 4}, {1, 7}, {2, 4}, {2, 7} at a time will have insignificant impacts on the routing delay. With a target of topology size reduction by two nodes, a specific pair can be chosen depending on the sensing criticality 200 of the individual nodes from an application perspective. Similar analysis can be performed with other routing protocols. Also note that similar criticality analysis can be performed for combination of higher number of nodes. 7.7 Summary and Conclusions This chapter develops a delay modeling fiamework for store-and-forward packet routing in Wireless Body Area Networks (WBAN). Using a prototype WBAN for experimentally characterizing and capturing on-body topology traces, an analytical delay modeling technique was developed for evaluating single-copy DTN routing protocols. End-to-end routing delay for a series of protocols including opportunistic, randomized, and two other mechanisms that capture multi-scale topological localities in human postural movements have been evaluated. Performance was evaluated experimentally, via simulation, and using the developed models. It was shown that via multi-scale modeling of the spatio-temporal locality of on-body link disconnection patterns, it is possible to attain better delay performance compared to opportunistic, randomized and utility-based DTN routing protocols in the literature. Finally, a mechanism for evaluating the topological importance of individual on-body sensor nodes is developed. It is shown that such information can be used for selectively reducing the on-body sensor-count without substantially sacrificing the packet delivery delay. Future work on this topic includes developing a Kalman Filter-based body movement prediction model for predictive on—body packet routing with lower delay objectives. 201 Chapter 8. Summary and Future Work 8.1 Contributions In this thesis, a framework for network integrated sensing and energy-aware protocols to address the resource constraints inherent to Wireless Body Area Networks (WBANS) were investigated. Available energy, processing, and form factor constraints of a body-mounted or -implanted sensor can severely limit its abilities for sensing, and the power and range of radio transmission for communication purposes. In this thesis we have investigated sensing, processing, and protocol solutions to address these system constraints. Chapter 3 has developed a novel network-integrated sensing modality, namely, inter-sensor relative proximity, which is inferred from the measured Received Signal Strength Indicator (RSSI) of the Radio Frequency (RF) signal between each pair of WBAN sensors. By using this new sensing modality, non activity-intensive postures can be detected without having to add extra components and the associated energy overheads. An experimental system was developed for integrating the proximity data with other traditional modalities, such as, acceleration and orientation. This multi-modal data was then processed using a stochastic processing framework Hidden Markov Model (HMM) for accurate posture identification in a subj ect-independent manner. Data transaction across on-body sensors can be point-to-point or multi-point-to-point depending on specific applications. The optimal transmission power required for an on-body wireless link between two sensors depends on the physical distance of the link and its instantaneous channel condition. The distance can vary with mobility driven by human postures, and the channel condition can change due to unpredictable RF 202 attenuation caused by a slew of factors including antenna orientation, clothing, and physical stature of specific subject individuals. An on-body link’s postural position can be highly dynamic due to the reasons listed above. As a result, static pre-defined transmission power is not able to provide continuous link connectivity while ensuring minimum required transmission power consumption. Therefore, a dynamic link power assignment mechanism for optimal energy management is needed. In Chapter 4, three different on-body link transmission power assignment mechanisms, namely, Linear, Binary and Dynamic Postural Position Inference (DPPI), were proposed. In these approaches, the receiver/ control node computes a new desirable transmission power level for the transmitter node by incrementing or decrementing the current power level based on the received RSSI values with respect an RSSI threshold range. No changes are needed when the RSSI falls within the range. This closed-loop control logic ensures that, for a given postural position, this process eventually achieves a desirable transmission power level so that the RSSI at the receiver falls within the preset threshold range. The proposed transmission power control mechanism was then enhanced in Chapter 5 by modeling human body movement as a stochastic linear system and a quantized Linear Quadratic Gaussian control with an Integrator (LQGI). The objective was to develop a model-based power control framework in which RF signal strength was predicted and regulated at a reference value to enhance the overall energy performance of an on-body wireless sensor. Chapter 6 and Chapter 7 of this thesis focused on on-body packet routing in the presence of topological partitioning caused due to ultra-short wireless range and postural 203 body movements. Short transmission range is a common constraint for low-power RF transceivers designed for embedded applications with limited energy, often supplied by harvested operations. Such situations are particularly pertinent for implantable body sensors. Low RF transmission ranges also mean that postural body movements can give rise to frequent partitioning or disconnection in WBAN topologies, resulting in a body area Delay Tolerant Network (DTN). Such topological partitioning can often get aggravated by the unpredictable RF attenuation caused due to signal blockage by clothing material and body segments. Topological partitioning necessitates store-and-forward routing protocols with performance goals of low end-to-end packet delay, packet loss, and transmission energy consumption. Chapter 6 explored and developed on-body store-and-forward packet routing algorithms in the presence of network partitioning. The objective was to minimize end-to-end packet delay by dynamically choosing routes on which the storage/buffering delays are low. While ensuring low storage delay, the algorithms also attempt to minimize the end-to-end hop-count so that the transmission energy drainage is minimized, thus leading to long network operating durations. Using a prototype WBAN, a topology characterization mechanism has been developed in Section 6.3 in order to demonstrate the network partitioning caused due to human postural mobility. Then, an on-body packet routing framework was developed in Section 6.4 using a stochastic link cost formulation, reflecting the body postural trends. The performance of the proposed protocols was evaluated experimentally and through simulation using the prototype WBAN. The performance of the routing protocols were 204 ‘1 then compared with the existing single copy DTN routing protocols, and a specialized flooding-based benchmark algorithm that provides routing delay lower-bounds. In Chapter 7, analytical techniques for modeling end-to-end packet delay for the proposed single copy DTN routing algorithms were developed. DTN routing delay obtained from the developed model were then compared with results from on-body experiments from the prototype WBAN and off-body simulation carried out with network topology traces obtained from the prototype WBAN. Using the model and the topology trace data, a detailed analysis was then carried out in Section 7.6 for identifying non-critical links in order to design a minimal WBAN topology from the routing stand point. 8.2 Future Work In Chapter 6 and Chapter 7, it was assumed that the sensor nodes have infinite and continuous source of energy. But in reality, this may not be true for the implanted sensors. Instead, the energy for the implanted WBAN sensors are likely to come from harvested energy sources such as piezoelectric, magnetic, and thermo-electric generators [3 8-43]. While the energy-harvesting sources can vary widely [123],[124],[58],[125-127], energy harvesting using vibration of piezoelectric sensors [38],[40-43],[51],[53-56],[127-136] are particularly relevant for the WBANS. Since the piezoelectric energy harvesting depends on movements [38],[42], the amount of energy harvested at a specific on-body sensor node will depend on the movement pattern of the body part that the node is attached to. As a result, the specific energy generation profile at the WBAN nodes does depend on the postural body movement patterns over time. 205 This dynamic energy generation profile provides an additional layer of constraints on the routing problem that was discussed in Chapter 6. To deal with this new constraint, an energy-aware [137-147],[75] store-and-forward packet routing protocol is necessary in the presence of network partitioning and harvested energy [88],[138],[139],[l48-156]. The goal will be to minimize end-to-end packet delay, packet loss, and transmission energy. The objective is to minimize end-to-end packet delays by dynamically choosing routes on which the storage/buffering delays are low. While ensuring low storage delay, the algorithm should also attempt to minimize the variance of the delay across all packets generated at different nodes, because low-harvested nodes may have tendency of buffering packets for too long. In addition, the algorithm should also work to: o Minimize the average per node down time. o Minimize the variance of downtime across all nodes. 0 Minimize average packet loss and the variance across all sources. 0 Minimize the end-to-end hop-count so that the transmission energy drainage is minimized, thus leading to long network operating durations. We will develop energy-aware on-body routing mechanisms for incorporating the above objectives. 206 [1] [2] [3] [4] [5] [6] [7] [8] [9] References E. Jovanov, A. Milenkovic, C. Otto, P. De Groen, B. Johnson, S. Warren, and G Taibi, “A WBAN System for Ambulatory Monitoring of Physical Activity and Health Status: Applications and Challenges,” Engineering in Medicine and Biology Society, 2005. IEEE-EMBS 2005. 27th Annual International Conference of the, 2005, pp. 3810-3813. E. Jovanov, A. Milenkovic, C. Otto, and P.C.D. Groen, “A Wireless Body Area Network of Intelligent Motion Sensors for Computer Assisted Physical Rehabilitation,” Journal NeuroEng. and Rehab, vol. 2, Mar. 2005, p. 6. R. Bartalesi, F. Lorussi, M. Tesconi, A. Tognetti, G Zupone, and D. De Rossi, “Wearable kinesthetic system for capturing and classifying upper limb gesture,” Eurohaptics Conference, 2005 and Symposium on Haptic Interfaces for Virtual Environment and Teleoperator Systems, 2005. World Haptics 2005. First Joint, 2005, pp. 535-536. Yun Liang, Abhik Roychoudhury, and Tulika Mitra, “Timing Analysis of Body Area Network Applications,” Dec. 2008. D. Simic, A. Jordan, Rui Tao, N. Gungl, J. Simic, M. Lang, Luong Van Ngo, and V. Brankovic, “Impulse UWB Radio System Architecture for Body Area Networks,” Mobile and Wireless Communications Summit, 2007. 16th 1ST, 2007, pp. 1-5. R. Istepanian, E. J ovanov, and Y. Zhang, “Guest Editorial Introduction to the Special Section on M-Health: Beyond Seamless Mobility and Global Wireless Health-Care Connectivity,” Information Technology in Biomedicine, IEEE Transactions on, vol. 8, 2004, pp. 405-414. M. Martinez-Espronceda, L. Serrano, I. Martinez, J. Escayola, S. Led, J. Trigo, and J. Garcia, “Implementing ISO/IEEE 11073: proposal of two different strategic approaches,” Conference Proceedings: Annual International Conference of the IEEE Engineering in Medicine and Biology Society. IEEE Engineering in Medicine and Biology Society. Conference, vol. 2008, 2008, pp. 1805-1808. L. Schmitt, T. Falck, F. Wartena, and D. Simons, “Novel ISO/IEEE 11073 Standards for Personal Telehealth Systems Interoperability,” Proceedings of the 2007 Joint Workshop on High Confidence Medical Devices, Software, and Systems and Medical Device Plug-and-Play Interoperability, IEEE Computer Society, 2007, pp. 146-148. J. Yao and S. Warren, “Applying the ISO/IEEE 11073 Standards to Wearable Home Health Monitoring Systems,” Journal of Clinical Monitoring and Computing, vol. 19, 2006, pp. 427-436. 207 [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] J. Yao and S. Warren, “Applying the ISO/IEEE 11073 Standards to Wearable Home Health Monitoring Systems,” Journal of Clinical Monitoring and Computing, vol. 19, 2006, pp. 427-436. ISO - International Organization for Standardization and ISO - International Organization for Standardization, “ISO - International Organization for Standardization.” Shu-Di Bao, Yuan-ng Zhang, and Lian—Feng Shen, “Physiological Signal Based Entity Authentication for Body Area Sensor Networks and Mobile Healthcare Systems,” Engineering in Medicine and Biology Society, 2005. IEEE-EMBS 2005. 27th Annual International Conference of the, 2005, pp. 2455-2458. B. Lo, S. Thiemjarus, R. King, and G. Yang, “Body Sensor Network — A Wireless Sensor Platform for Pervasive Healthcare Monitoring,” Proceddings of the 3rd International Conference on Pervasive Computing (PERVASIVE 2005), May. 2005, pp. 77-80. C. Otto, A. Milenkovic, C. Sanders, and E. Jovanov, “System Architecture of a Wireless Body Area Sensor Network for Ubiquitous Health Monitoring,” Journal of Mobile Multimedia, vol. 1, 2006, pp. 307-326. M. Moh, B. Culpepper, Lan Dung, Teng-Sheng Moh, T. Harnada, and Ching-Fong Su, “On data gathering protocols for in-body biomedical sensor networks,” Global Telecommunications Conference, 2005. GLOBECOM '05. IEEE, 2005, pp. 6 pp=2996. A. Milenkovic, C. Otto, and E. Jovanov, “Wireless Sensor Networks for Personal Health Monitoring: Issues and an Implementation,” Special issue: Wireless Sensor Networks: Performance, Reliability, Security, and Beyond, 2006. A. Milenkovic, C. Otto, and E. Jovanov, “Wireless sensor networks for personal health monitoring: Issues and an implementation,” Computer Communications, vol. 29, 2006, pp. 2521—2533. R.R. Pate, K.A. Pfeiffer, S.G Trost, P. Ziegler, and M. Dowda, “Physical Activity Among Children Attending Preschools,” Pediatrics, vol. 114, Nov. 2004, pp. 1258-1263. K. Chen and DJ. Bassett, “The Technology of Accelerometry-based Activity Monitors: Current and Future,” Med Sci Sports Exerc, vol. 37, 2005, pp. 490-500. J. Brusey, R. Rednic, E.I. Gaura, J. Kemp, and N. Poole, “Postural activity monitoring for increasing safety in bomb disposal missions,” Measurement Science and Technologi, vol. 20, 2009, p. 075204. M.J.C. Almeida, K.L. Mclver, K.A. Pfeiffer, M. Dowda, and RR. Pate, “Validation 208 [221 [231 [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] and Calibration of the Actical Accelerometer in Preschool Children.” S.G Trost, K.L. Mclver, and RR. Pate, “Conducting accelerometer-based activity assessments in field-based research,” Medicine and Science in Sports and Exercise, vol. 37, Nov. 2005, pp. S531-543. G.J. Welk, “Principles of design and analyses for the calibration of accelerometry-based activity monitors,” Medicine and Science in Sports and Exercise, vol. 37, Nov. 2005, pp. 8501-511. S. Biswas and M. Quwaider, “Remote Monitoring of Soldier Safety through Body Posture Identification using Wearable Sensor Networks,” SPIE Defense and Security Symposium, Multisensor; Multisource Information Fusion: Architectures, Algorithms, and Applications, 2008, pp. 1-14. K. Venkatasubramanian, A. Banerjee, and S. Gupta, “Plethysmogram—based secure inter-sensor communication in Body Area Networks,” Military Communications Conference, 2008. MILCOM 2008. IEEE, 2008, pp. 1-7. E. Jovanov, D. Raskovic, J. Price, J. Chapman, A. Moore, and A. Krishnamurthy, “Patient monitoring using personal area networks of wireless intelligent sensors,” Biomedical Sciences Instrumentation, vol. 37, 2001, pp. 373-378. K. Yazdandoost and R. Kohno, “UWB antenna for wireless body area network,” Microwave Conference, 2006. APMC 2006. Asia-Pacific, 2006, pp. 1647-1652. C. Cordeiro and M. Patel, “Body area networking standardization: present and future directions,” Proceedings of the ICST 2nd international conference on Body area networks, Florence, Italy: ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2007, pp. 1-2. K. Lorincz, D.J. Malan, T.R.F. Fulford-Jones, A. Nawoj, A. Clavel, V. Shnayder, G Mainland, M. Welsh, and S. Moulton, “Sensor networks for emergency response: Challenges and opportunities,” IEEE Pervasive Computing, vol. 3, 2004, pp. 16-23. GZ. Yang and M. Yacoub, Body sensor networks, Springer-Verlag New York Inc, 2006. B. Lo and GZ. Yang, “Key technical challenges and current implementations of body sensor networks,” IEE Proceedings of the 2nd International Workshop on Body Sensor Networks (BSN 2005), 2005, pp. 1-5. B. Gyselinclcx, J. Penders, and R. Vullers, “Potential and challenges of body area networks for cardiac monitoring,” Journal of Electrocardiology, vol. 40, 2007, pp. 165-168. A. Ylisaukko-oja, E. Vildjiounaite, and J. Mantyjarvi, “Five-point acceleration 209 [34] [351 [36] [371 [38] [39] [40] [41] [421 [43] [441 sensing wireless body area network - design and practical experiences,” Wearable Computers, 2004. IS WC 2004. Eighth International Symposium on, 2004, pp. 184-185. E. Farella, A. Pieracci, L. Benini, and A. Acquaviva, “A Wireless Body Area Sensor Network for Posture Detection,” Computers and Communications, 2006. ISCC '06. Proceedings. 11th IEEE Symposium on, 2006, pp. 454-459. Seon-Woo Lee and K. Mase, “Activity and location recognition using wearable sensors,” Pervasive Computing, IEEE, vol. 1, 2002, pp. 24-32. A. Krause, D. Siewiorek, A. Smailagic, and J. Farringdon, “Unsupervised, dynamic identification of physiological and activity context in wearable computing,” Wearable Computers, 2003. Proceedings. Seventh IEEE International Symposium on, 2003, pp. 88-97. N. Ravi, N. Dandekar, P. Mysore, and ML. Littman, “Activity recognition from accelerometer data,” PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005, p. 1541. E. Minazara, D. Vasic, and F. Costa, “Piezoelectric Generator Harvesting Bike Vibrations Energy to Supply Portable Devices.” M.P. Rothney, M. Neumann, A. Beziat, and KY Chen, “An artificial neural network model of energy expenditure using nonintegrated acceleration signals,” J Appl Physiol, vol. 103, Oct. 2007, pp. 1419-1427. L. Mateu and F. Moll, “System-Level Simulation of a Self-Powered Sensor with Piezoelectric Energy Harvesting,” Sensor Technologies and Applications, 2007. SensorComm 2007. International Conference on, 2007, pp. 399-404. S. Priya, R. Taneja, R. Myers, and R. Islam, “Piezoelectric Energy Harvesting using Bulk Transducers,” Piezoelectric and Acoustic Materials for Transducer Applications, 2008, pp. 373-388. E. Minazara, D. Vasic, F. Costa, and G Poulin, “Piezoelectric diaphragm for vibration energy harvesting,” Ultrasonics, vol. 44, Dec. 2006, pp. e699-e703. Q. Zheng and Y. Xu, “Asymmetric air-spaced cantilevers for vibration energy harvesting,” Smart Materials and Structures, vol. 17, 2008, p. 055009. Sungdae Choi, Seong-Jun Song, Kyomin Sohn, Hyejung Kim, Jooyoung Kim, J. Yoo, and Hoi-Jun Yoo, “A Low-power Star-topology Body Area Network Controller for Periodic Data Monitoring Around and Inside the Human Body,” Wearable Computers, 2006 10th IEEE International Symposium on, ISWC, 2006, pp. 139-140. 210 [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [551 M. Hanson, H. Powell, A. Barth, K. Ringgenberg, B. Calhoun, J. Aylor, and J. Lach, “Body Area Sensor Networks: Challenges and Opportunities,” Computer, vol. 42, 2009, pp. 58-65. Y. Lin, B. Veeravalli, and S. Viswanathan, “Critical-Path based Low-Energy Scheduling Algorithms for Body Area Network Systems,” RT CSA '07: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, IEEE Computer Society, 2007, pp. 308, 301. M. Walsh, M. Hayes, and J. Nelson, “Robust performance for an energy sensitive wireless body area network — an anti-windup approach,” International Journal of Control, vol. 82, 2009, p. 59. I. Lamprinos, A. Prentza, E. Sakka, and D. Koutsouris, “Energy-efficient MAC Protocol for Patient Personal Area Networks,” Engineering in Medicine and Biology Society, 2005. IEEE-EMBS 2005. 2 7th Annual International Conference of the, 2005, pp. 3799-3802. T. Norgall, “Body Area Network — a Key Infiastructure Element for Patient-Centric Health Services,” ISO TC215 / WG7 / IEEE 1073 Meeting Berlin, 2005, pp. 9-11. I. Culpepper, Lan Dung, and M. Moh, “Hybrid indirect transmissions (HIT) for data gathering in wireless micro sensor networks with biomedical applications,” Computer Communications, 2003. CC W 2003. Proceedings. 2003 IEEE 18th Annual Workshop on, 2003, pp. 124-133. J. Ajitsaria, S.Y. Choe, D. Shen, and DJ. Kim, “Modeling and analysis of a bimorph piezoelectric cantilever beam for voltage generation,” Smart Materials and Structures, vol. 16, 2007, pp. 447-454. V.R. Challa, M.G. Prasad, Y. Shi, and ET. Fisher, “A vibration energy harvesting device with bidirectional resonance frequency tunability,” Smart Materials and Structures, vol. 17, 2008, p. 015035. H. Fang, J. Liu, Z. Xu, L. Dong, L. Wang, D. Chen, B. Cai, and Y. Liu, “Fabrication and performance of MEMS-based piezoelectric power generator for vibration energy harvesting,” Microelectron. J., vol. 37, 2006, pp. 1280-1284. M. Ferrari, D. Marioli, and A. Taroni, “Modeling, Fabrication and Performance Measurements of a Piezoelectric Energy Converter for Power Harvesting in Autonomous Microsystems,” Instrumentation and Measurement, IEEE Transactions on, vol. 55, 2006, pp. 2096-2101. S. Jiang, X. Li, S. Guo, Y. Hu, J. Yang, and Q. Jiang, “Performance of a piezoelectric bimorph for scavenging vibration energy,” Smart Materials and Structures, vol. 14, 2005, pp. 774, 769. 211 [56] [57] [581 [59] [60] [61] [62] [63] [64] [65] [66] S. Roundy and P. Wright, “A piezoelectric vibration based generator for wireless electronics,” Smart Materials and Structures, vol. 13, 2004, pp. 1142, 1131. D. Shen, J. Park, J. Ajitsaria, S. Choe, H.C.W. III, and D. Kim, “The design, fabrication and evaluation of a MEMS PZT cantilever with an integrated Si proof mass for vibration energy harvesting,” Journal of Micromechanics and Microengineering, vol. 18, 2008, p. 055017. S.P. Beeby, M.J. Tudor, and NM. White, “Energy harvesting vibration sources for microsystems applications,” Measurement science and technology, vol. 17, 2006, p. 175. “WebPage of Department of Health and Human Services,” wwwgrantsZ.nih.gov/grants/guide/pa-files/PA-07-354.htrnl. M. Quwaider and S. Biswas, “Physical Context Detection using Multi-modal Sensing using Wearable Wireless Networks,” Journal of Communication Software and Systems (JCOMSS ’08), Special Issue on Medical Applications for WSN, vol. 4, 2008, pp. 191-202. M. Quwaider and S. Biswas, “Body posture identification using hidden Markov model with a wearable sensor network,” Proceedings of the ICST 3rd international conference on Body area networks, Tempe, Arizona: ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2008, pp. 1-8. S. Lin, J. Zhang, G. Zhou, L. Gu, J. Stankovic, and T. He, “ATPC: adaptive transmission power control for wireless sensor networks,” SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems, ACM Press, 2006, pp. 236, 223. G Zhou, T. He, S. Krishnamurthy, and J. Stankovic, “Impact of radio irregularity on wireless sensor networks,” MobiSys '04: Proceedings of the 2nd international conference on Mobile systems, applications, and services, ACM Press, 2004, pp. 138, 125. S. Xiao, V. Sivaraman, and A. Burdett, “Adapting radio transmit power in wireless body area sensor networks,” Proceedings of the ICST 3rd international conference on Body area networks, Tempe, Arizona: ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering), 2008, pp. 18 S. Mikarni, T. Matsuno, M. Miyama, M. Yoshimoto, and H. Ono, “A Wireless-Interface SoC Powered by Energy Harvesting for Short-range Data Communication,” Asian Solid-State Circuits Conference, 2005, 2005, pp. 241-244. D. Sagan, “RF Integrated Circuits for Medical Applications: Meeting the Challenge of Ultra Low Power Communication,” Ultra-Low-Power Communications Division, Zarlink Semiconductor, 2005. 212 [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [781 [79] [80] [81] E. Strommer, M. Hillukkala, and A. Ylisaukkooja, “Ultra-low Power Sensors with Near Field Communication for Mobile Applications,” International Conference on Wireless Network, 1C WN’07, 2007, pp. 1-12. T. Falck, H. Baldus, J. Espina, and K. Klabunde, “Plug 'n Play Simplicity for Wireless Medical Body Sensors,” Pervasive Health Conference and Workshops, 2006, 2006, pp. 1-5. E. Jones and P. Ward, “Routing strategies for delay-tolerant networks,” ACM Computer Communication (CCR), 2006. Hui Guo, Jiang Li, Yi Qian, and Ye Tian, “A practical routing strategy in Delay Tolerant Networks using multiple pigeons,” Military Communications Conference, 2008. MILCOM 2008. IEEE, 2008, pp. l-7. J. Leguay_afi1 n2, T. Friedman, and V. Conan, “Evaluating MobySpace-based routing strategies in delay-tolerant networks: Research Articles,” Wirel. Commun. Mob. Comput., vol. 7, 2007, pp. 1171-1182. V. Conan, J. Leguay, and T. Friedman, “Fixed point opportunistic routing in delay tolerant networks,” Selected Areas in Communications, IEEE Journal on, vol. 26, 2008, pp. 773-782. J. Leguay, T. Friedman, and V. Conan, “Evaluating Mobility Pattern Space Routing for DTNs,” INF OCOM 2006. 25th IEEE International Conference on Computer Communications. Proceedings, 2006, pp. 1-10. A. Lindgren, A. Doria, and O. Schelén, “Probabilistic routing in intermittently connected networks,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 7, 2003, pp. 19-27. “Link to Cipcon SmartRF CC1000 Datasheet,” http://www. chipcon. com/fi les/C C 1 000_Data_Sheet_2_I .pdf. “Link to chipcon.com/,” http://www. chipcon.com/. “Webpage of TinyOS Technology,” http://www. tinyos.net/. “Crossbow Technology, Inc.,” http://wwwxbow. com. L. Bao and S. Intille, “Activity Recognition from User-Annotated Acceleration Data,” Pervasive 2004, Apr. 2004, pp. 17, 1. “Link to posture detection videoz,” http://www. egr: msu. edu/~sbiswas/Research/Wearable. mpg. L. Liporace, “Maximum likelihood estimation for multivariate observations of Markov sources,” Information Theory, IEEE Transactions on, vol. 28, 1982, pp. 213 [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] 729-734. B.H. Juang, “Maximum-likelihood estimation for mixture multivariate stochastic observation of Markov chains,” AT & T TECH. J., vol. 64, 1985, pp. 1235-1250. L. Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition,” Proceedings of the IEEE, vol. 77, 1989, pp. 257-286. L. Wang, M. Mehrabi, and EL Kannatey-Asibu, “Hidden Markov Model-based Tool Wear Monitoring in Turning,” Manufacturing Science and Engineering, vol. 124, 2002, pp. 651-658. J. Allanach, Haiying Tu, S. Singh, P. Willett, and K. Pattipati, “Detecting, tracking, and counteracting terrorist networks via hidden Markov models,” Aerospace Conference, 2004. Proceedings. 2004 IEEE, 2004, p. 3257 Vol.5. V.N. James and J. Clark, “Automated Visual Surveillance Using Hidden Markov Models,” International Conference on Vision Interface, 2002, pp. 88-93. 0. Brdiczka, J. Maisonnasse, and P. Reignier, “Automatic detection of interaction groups,” Proceedings of the 7th international conference on Multimodal interfaces, Torento, Italy: ACM, 2005, pp. 32-36. T. Lim and G Mohan, “Energy aware geographical routing and topology control to improve network lifetime in wireless sensor networks,” Broadband Networks, 2005. BroadNets 2005. 2nd International Conference on, 2005, pp. 771-773 Vol. 2. Guoliang Xing, Chenyang Lu, and R. Pless, “Localized and Configurable Topology Control in Lossy Wireless Sensor Networ ,” Computer Communications and Networks, 2007. ICCCN 2007. Proceedings of 16th International Conference on, 2007, pp. 75-80. J. Liu and B. Li, “Distributed topology control in wireless sensor networks with ’ asymmetric links,” Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE, 2003, pp. 1257-1262 vol.3. U. Klee, T. Gehrig, and J. McDonough, “Kalman filters for time delay of arrival-based source localization,” EURASIP J. Appl. Signal Process, vol. 2006, 2006, pp. 167-167. P. Nar and E. Cayirci, “PCSMAC: a power controlled sensor-MAC protocol for wireless sensor networks,” Wireless Sensor Networks, 2005. Proceeedings of the Second European Workshop on, 2005, pp. 81-92. Daji Qiao, Sunghyun Choi, Amit Jain, and K. Shin, “Adaptive transmit power control in IEEE 802.11a wireless LANS,” Vehicular Technology Conference, 2003. VTC 2003-Spring. The 57th IEEE Semiannual, 2003, pp. 433-437 VOL]. 214 [94] S.A. Srikanth, S. Agarwal, S.V. Krishnamurthy, R.H. Katz, and SK. Dao, “Distributed Power Control in Ad-hoc Wrreless Networks,” IEEE International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), vol. 2, 2001, pp. 59--66. [95] E. Lopez-Aguilera and J. Casademont, “A transmit power control proposal for IEEE 802.11 cellular networks,” 6th International Workshop on on Applications and Services in Wireless Networks, New York: Institute of Electrical and Electronics Engineers, 2006, pp. 235-242. [96] H. Saghaei and A. Neyestanak, “Variable Step Closed-Loop Power Control in Cellular Wireless CDMA Systems under Multipath Fading,” Communications, Computers and Signal Processing, 2007. PacRim 2007. IEEE Pacific Rim Conference on, 2007, p. 157-160. [97] M. Rintamaki, H. Koivo, and I. Hartirno, “Adaptive closed-loop power control algorithms for CDMA cellular communication systems,” Vehicular Technology, IEEE Transactions on, vol. 53, 2004, pp. 1756-1768. [98] Rintamaki, “Power control in CDMA cellular communication, systems,” Wiley Encyclopedia of Telecommunications, J. G Proakis, 2002. [99] K. Srinivasan, P. Dutta, A. Tavakoli, and P. Levis, “Understanding the causes of packet delivery success and failure in dense wireless sensor networks,” SenSys '06: Proceedings of the 4th international conference on Embedded networked sensor systems, Boulder, Colorado, USA: ACM, 2006, pp. 420, 419. [100] N. Dankwa, “An Evaluation of Transmit Power Levels for Node Localization on the Mica2 Sensor Node,” signal, vol. 5, 2004, p. 03. [101] J. Kim, S. Chang, and Y. Kwon, “ODTPC: On-demand Transmission Power Control for Wireless Sensor Networks,” Information Networking, 2008. [COIN 2008. International Conference on, 2008, pp. 5, l. [102] J. Choi, R Morales, Y. Zhao, and A. Majurndar, “Design and Control of a Thermal Stabilizing System for a MEMS Optomechanical Uncooled Infrared Imaging Camera,” Elsevier Sensors and Actuators, vol. 203, 2003, pp. 132-142. [103] M. Athans, “The role and use of the stochastic linear-quadratic-Gaussian problem in control system design,” Automatic Control, IEEE Transactions on, vol. 16, 1971, pp. 529-552. [104] K. Zhou, J. Doyle, and K. Glover, Robust and Optimal Control, Prentice Hall Upper Saddle River, NJ, 1996. [105] A. Maddi, A. Guessoum, and D. Berkani, “Using Linear Quadratic Gaussian Optimal Control for Lateral Motion of Aircraft,” World Academy of Science, Engineering And Technology, vol. 37, 2009. 215 [106] E. Maneri and W. Gawronski, “Linear Quadratic Gaussian Controller Design Using a Graphical User Interface: Application to the Beam-Waveguide Antennas,” Oct. 1999. [107] DP. Looze, “Linear—quadratic-Gaussian control for adaptive optics systems using a hybrid model,” Journal of the Optical Society of America A, vol. 26, Jan. 2009, pp. 1-9. [108] T. Spyropoulos, K. Psounis, and CS. Raghavendra, “Efficient routing in intermittently connected mobile networks: The multiple-copy case,” IEEE/A CM Transactions on Networking (TON), vol. 16, 2008, pp. 77—90. [109] H. Dubois-ferriere, M. Grossglauser, and M. Vetterli, “Age matters: Efficient route discovery in mobile ad hoc networks using encounter ages,” 2003. [110] J. Leguay, T. Friedman, and V. Conan, “DTN routing in a mobility pattern space,” Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, Philadelphia, Pennsylvania, USA: ACM, 2005, pp. 276-283. [111] B. Braem, B. Latre, I. Moerman, C. Blondia, and P. Demeester, “The Wireless Autonomous Spanning tree Protocol for Multihop Wireless Body Area Networ ,” Mobile and Ubiquitous Systems - Workshops, 2006. 3rd Annual International Conference on, 2006, pp. 1-8. [112] B. Latre, B. Braem, I. Moerman, C. Blondia, E. Reusens, W. Joseph, and P. Demeester, “A Low-delay Protocol for Multihop Wireless Body Area Networks,” Mobile and Ubiquitous Systems: Networking & Services, 2007. MobiQuitous 2007. Fourth Annual International Conference on, 2007, pp. 1-8. [113] S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, 2004, pp. 145—158. [114] A. Jindal and K. Psounis, “Performance analysis of epidemic routing under contention,” Proceedings of the 2006 international conference on Wireless communications and mobile computing, Vancouver, British Columbia, Canada: ACM, 2006, pp. 539-544. [115] A. Vahdat and D. Becker, “Epidemic Routing for Partially Connected Ad Hoc Networks,” Technical Report CS-200006, Duke University, 2000. [116] T. Spyropoulos, K. Psounis, and C. Raghavendra, “Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case,” Networking, IEEE/ACM Transactions on, vol. 16, 2008, pp. 63-76. [117] S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, K. Scott, and H. Weiss, “Delay-tolerant networking: an approach to interplanetary Internet,” Communications Magazine, IEEE, vol. 41, 2003, pp. 128-136. 216 [118] D. Thakore and S. Biswas, “Routing with persistent link modeling in intermittently connected wireless networks,” Military Communications Conference, 2005. MILCOM 2005. IEEE, 2005, pp. 461-467 Vol. 1. [119] M. Shin, S. Hong, and l. Rhee, “DTN routing strategies using optimal search patterns,” Proceedings of the third ACM workshop on Challenged networks, San Francisco, California, USA: ACM, 2008, pp. 27-32. [120] M. Quwaider and S. Biswas, “Disruption Tolerant Network Routing in Body Sensor Networks with Dynamic Postural Partitioning,” In Press, To Appear; Elsevier Ad Hoc Networks, 2010. [121] M. Quwaider and S. Biswas, “Probabilistic routing in on-body sensor networks with postural disconnections,” Proceedings of the 7th ACM international symposium on Mobility management and wireless access, Tenerife, Canary Islands, Spain: ACM, 2009, pp. 149-158. [122] M. Quwaider and S. Biswas, “On-body Packet Routing Algorithms for Body Sensor Networks,” NE T COM '09. First International Conference on Networks and Communications, Dec. 2009, pp. 171-177. [123] SP. Beeby, M.J. Tudor, and NM. White, “Energy harvesting vibration sources for microsystems applications,” Dec. 2006. [124] G Park, T. Rosing, M.D. Todd, C.R. Farrar, and W. Hodgkiss, “Energy harvesting for structural health monitoring sensor networks,” Journal of Infiastructure Systems, vol. 14, 2008, p. 64. [125] NE. Bharatula, S. Ossevoort, M. Stager, and G Troster, “Towards wearable autonomous microsystems,” Pervasive computing: second international conference, Pervasive 2004, Linz/Vienna, Austria, April 18-23, 2004: proceedings, 2004,p.225. [126] A. Hande, T. Polk, W. Walker, and D. Bhatia, “Self-Powered Wireless Sensor Networks for Remote Patient Monitoring in Hospitals,” Sensors, vol. 6, 2006, pp. 1102—1117. [127] NS. Shenck and J.A. Paradiso, “Energy scavenging with shoe-mounted piezoelectrics,” IEEE MICRO, 2001, pp. 30—42. [128] GK. Ottrnan, H.F. Hofinann, A.C. Bhatt, and GA. Lesieutre, “Adaptive piezoelectric energy harvesting circuit for wireless remote power supply,” IEEE Transactions on Power Electronics, vol. 17, 2002, pp. 669—676. [129] B. Yang, C. Lee, W. Xiang, J. Xie, J .H. He, R.K. Kotlanka, S.P. Low, and H. Feng, “Electromagnetic energy harvesting from vibrations of multiple fiequencies,” Journal of Micromechanics and Microengineering, vol. 19, 2009, p. 035001. 217 [130] HA. Sodano, D.J. Inman, and G Park, “Comparison of piezoelectric energy harvesting devices for recharging batteries,” Journal of Intelligent Material Systems and Structures, vol. 16, 2005, p. 799. [131] GA. Lesieutre, GK. Ottman, and HF. Hofmann, “Damping as a result of piezoelectric energy harvesting,” Journal of Sound and Vibration, vol. 269, 2004, pp. 991—1001. [132] GK. Ottman, H.F. Hofmann, and GA. Lesieutre, “Optimized piezoelectric energy harvesting circuit using step-down converter in discontinuous conduction mode,” IEEE Transactions on Power Electronics, vol. 18, 2003, pp. 696—703. [133] E. Lefeuvre, A. Bade], C. Richard, and D. Guyomar, “Piezoelectric energy harvesting device optimization by synchronous electric charge extraction,” Journal of Intelligent Material Systems and Structures, vol. 16, 2005, p. 865. [134] M.J. Ramsay and W.W. Clark, “Piezoelectric energy harvesting for bio-MEMS applications,” Proceedings of SPIE, 2001, p. 429. [135] S. Kim, W.W. Clark, and Q.M. Wang, “Piezoelectric energy harvesting with a clamped circular plate: analysis,” Journal of intelligent material systems and structures, vol. 16, 2005, p. 847. [136] L. Mateu and F. Moll, “System-Level Simulation of a Self-Powered Sensor with Piezoelectric Energy Harvesting,” Sensor Technologies and Applications, 2007. SensorComm 2007. International Conference on, 2007, pp. 399—404. [137] K. Akkaya and M. Younis, “An energy-aware QoS routing protocol for wireless sensor networks,” Distributed Computing Systems Workshops, 2003. Proceedings. 23rd International Conference on, 2003, pp. 710-715. [138] B. Guo, Z. Li, and D. Li, “Energy-Aware Improved Directed Diffusion Algorithm for Area Event Monitoring in Wireless Sensor Network,” Lecture notes in computer science, Third international conference, ICDCIT, 2006, pp. 20-23. [139] A. Pourkabirian and A. Haghighat, “Energy-aware, delay-constrained routing in wireless sensor networks through genetic algorithm,” Software, Telecommunications and Computer Networks, 2007. SoftCOM 2007. 15th International Conference on, 2007, pp. 1-5. [140] AB. Mohanoor, S. Radhakrishnan, and V. Sarangan, “Online energy aware routing in wireless networks,” Ad Hoc Netw., vol. 7, 2009, pp. 918-931. [141] AB. Mohanoor, S. Radhakrishnan, and V. Sarangan, “On energy aware routing in wireless networks,” Broadband Communications, Networks and Systems, 200 7. BROADNET S 2007. Fourth International Conference on, 2007, pp. 690-697. [142] Zhi Ang Eu, Hwee-Pink Tan, and W. Seah, “Routing and Relay Node Placement in 218 Wireless Sensor Networks Powered by Ambient Energy Harvesting,” Wireless Communications and Networking Conference, 2009. WCNC 2009. IEEE, 2009, pp. 1-6. [143] B. Wenning, D. Pesch, A. Timm-Giel, and C. Gorg, “Environmental Monitoring Aware Routing in Wireless Sensor Networks,” Wireless and Mobile Networking, 2008, pp. 5-16. [144] M. Rahimi, H. Shah, G Sukhatme, J. Heideman, and D. Estrin, “Studying the feasibility of energy harvesting in a mobile sensor network,” Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on, 2003, pp. 19-24 vol.l. [145] A. Kansal, J. Hsu, S. Zahedi, and MB. Srivastava, “Power management in energy harvesting sensor networks,” ACM Trans. Embed. Comput. Syst., vol. 6, 2007, p. 32. [146] A. Mahapatra, K. Anand, and DP. Agrawal, “QoS and energy aware routing for real-time traffic in wireless sensor networks,” Computer Communications, vol. 29, Feb. 2006, pp. 437-445. [147] H. Kwon, D. Noh, J. Kim, J. Lee, D. Lee, and H. Shin, “Low-Latency Routing for Energy-Harvesting Sensor Networks,” Ubiquitous Intelligence and Computing, 2007, pp. 422-433. [148] G Schaefer, F. Ingelrest, and M. Vetterli, “Potentials of Opportunistic Routing in Energy-Constrained Wireless Sensor Networks,” E WSN '09: Proceedings of the 6th European Conference on Wireless Sensor Networks, Cork, Ireland: Springer-Verlag, 2009, pp. 133, 118. [149] M. Jakobsen, “Energy Harvesting Aware Routing and Scheduling in Wireless Sensor Networks,” Master Thesis, Department of Informatics and Mathematical Modeling, Technical University of Denmark DTU Informatics, 2008. [150] Yongchang Yu and Gang Wei, “Energy Aware Routing Algorithm for Target Region Monitoring in Wireless Sensor Network,” Wireless Communications, Networking and Mobile Computing, 2007. WzCom 2007. International Conference on, 2007, pp. 2617-2620. [151] R. Shah and J. Rabaey, “Energy aware routing for low energy ad hoc sensor networ ,” Wireless Communications and Networking Conference, 2002. WCNC2002. 2002 IEEE, 2002, pp. 350-355 vol]. [152] K. Zeng, K. Ren, W. Lou, and RI. Moran, “Energy-aware geographic routing in lossy wireless sensor networks with environmental energy supply,” Proceedings of the 3rd international conference on Quality of service in heterogeneous wired/wireless networks, Waterloo, Ontario, Canada: ACM, 2006, p. 8. 219 [153] Nilanjan Banerjee, Jacob Sorber, Mark D. Corner, Sami Rollins, and Deepak Ganesan, “Triage: Balancing Energy and Quality of Service in a Microserver,” 2007. [154] N. Banerjee, M. Corner, and B. Levine, “An Energy-Efficient Architecture for DTN Throwboxes,” INF OCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE, 2007, pp. 776-784. [155] Liming He, “Delay-Minimum Energy-Aware Routing Protocol (DERP) for Wireless Sensor Networks,” Jul. 2007. [156] C. Intanagonwiwat, R. Govindan, D. Estrin, J. Heidemann, and F. Silva, “Directed difl‘usion for wireless sensor networking,” Networking, IEEE/A CM Transactions on, vol. 11, 2003, pp. 2-16. 220 ll lllll ll” Ill”- I" Ill “ m l u E “l Ill I.|.. N H A m nlU ”ll H I 31293 03063 6017