Mitigating the Effect of PropagationImpairments on Higher Layer Protocolsand Algorithms in Wireless SensorNetworksbyPooyan AbouzarB.Sc., University of Tehran, 2006M.Sc., Chalmers University of Technology, 2008A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFDOCTOR OF PHILOSOPHYinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2016c© Pooyan Abouzar 2016AbstractWireless sensor networks (WSNs) range from body area networks (BANs) that involve arelatively small number of nodes, short paths and frequent update rates to precision agri-culture wireless sensor networks (PAWSNs) that involve a relatively large number of nodes,long paths and infrequent update rates. They are distinguished from wireless access net-works by: 1) their mesh architecture and reliance on higher layer protocols and algorithmsto perform routing, scheduling, localization, and node placement, 2) their need to operatefor long periods of time with only limited access to battery or scavenged power.Energy conservation has long been an important goal for developers of WSNs and thepotential for reducing energy consumption in such networks by reducing the strength and/orfrequency of transmission has long been recognized. Although the impact of propagationimpairments on the physical and media access control layers of WSNs has long been con-sidered, few previous studies have sought to assess their impact on higher layer protocolsand algorithms and devise schemes for mitigating or accounting for such impacts. Here, wepresent four case studies that demonstrate how higher layer protocols and algorithms can bedevised to achieve greater energy efficiency by accounting for the nature of the propagationimpairments experienced.In the first two case studies, we focus on BANs and: 1) propose a routing protocolthat uses linear programming techniques to ensure that all nodes expend energy at a similarrate and thereby maximize network lifetime and 2) propose a scheduling algorithm thataccounts for the periodic shadowing observed over many BAN links and thereby reduce thetransmit power required to transfer information and thereby maximize network lifetime. Inthe second two case studies, we focus on PAWSNs and 3) propose an efficient localizationalgorithm based on the Bayesian model for information aggregation and 4) demonstratethat path loss directionality observed in sites such as high density apple orchards greatlyaffects WSN connectivity and, therefore, energy consumption and must be considered whendesigning node placement in agricultural fields.iiPrefacePortions of Chapter 2 were presented at the IEEE VTC 2012-Spring [P. Abouzar, K. Shafiee,D. G. Michelson, and V. Leung, "Effects of relaying on network lifetime in 2.4 GHz IEEE802.15.4 based body area networks," in Proc. IEEE VTC 2012 Spring, May 2012, pp. 1-5]. I was the lead investigator, responsible for all major areas of concept formation, datacollection and analysis, as well as the majority of manuscript composition. V.C.M. Leungand K. Shafiee contributed to the organization of the work presented in Chapter 2. D.G. Michelson was the supervisory author on this project and was involved throughout theproject in concept formation and manuscript edits. K. Shafiee served as the test subjectduring the measurement campaign.Portions of Chapter 3 were presented at the IEEE PIMRC 2011 [P. Abouzar, K. Shafiee,D. G. Michelson, and V. Leung, "Action-based scheduling technique for 802.15. 4/ZigBeewireless body area networks," in Proc. IEEE PIMRC 2011, Sep. 2011, pp. 2188-2192]. I wasthe lead investigator, responsible for all major areas of concept formation, data collection andanalysis, as well as the majority of manuscript composition. V.C.M. Leung and K. Shafieewere involved in the early stages of concept formation and contributed to manuscript edits.D. G. Michelson was the supervisory author on this project and was involved throughoutthe project in concept formation and manuscript edits. K. Shafiee served as the test subjectduring the measurement campaign.A version of Chapter 4 has been accepted for publication by IEEE Transactions onWireless Communications [P. Abouzar, D. G. Michelson, and M. Hamdi, "RSSI-based dis-tributed self-localization for wireless sensor networks used in precision agriculture," acceptedat IEEE Trans. Wireless Commun., Jun. 2016]. Portions of the work were presented atthe IEEE APS/URSI 2015 [P. Abouzar, D. G. Michelson, and M. Hamdi, "Localization ofwireless devices in agricultural fields," in Proc. USNC-URSI 2015, Jul. 2015, pp. 218-218].I was the lead investigator, responsible for all major areas of concept formation, data col-lection and analysis, as well as the majority of manuscript composition. M. Hamdi assistedwith parts of the problem formulation and Bayesian inference analysis of the results. D.iiiPrefaceG. Michelson was the supervisory author on this project and was involved throughout theproject in concept formation and manuscript edits.Portions of Chapter 5 were presented at the IEEE APS/URSI 2014 [P. Abouzar andD. G. Michelson, "Characterization of wireless mesh network performance in agriculturalenvironments," in Proc. USNC-URSI 2014, Jul. 2014, pp. 125-125]. I was the lead inves-tigator, responsible for all major areas of concept formation, data collection and analysis,as well as the majority of manuscript composition. D. G. Michelson was the supervisoryauthor on this project and was involved throughout the project in concept formation andmanuscript edits.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ixList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Significance of Higher Layer Algorithms in Wireless Sensor Networks . . . . . 31.2 Review of Recent Developments in Wireless Sensor Network Technology . . . 41.2.1 Key Advances and Enabling Technologies . . . . . . . . . . . . . . . . 41.2.2 Key Limitations of Previous Work . . . . . . . . . . . . . . . . . . . . 81.3 Objectives of This Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 A Routing Protocol for Maximizing the Lifetime of Body Area Networks 162.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.1 System Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 22vTable of Contents2.3 Solution of the Lifetime Maximization Problem . . . . . . . . . . . . . . . . . 252.3.1 Transmit Power Adjustment Algorithm . . . . . . . . . . . . . . . . . 252.3.2 LP Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3.3 Implementation Considerations and Routing Algorithm . . . . . . . . 292.3.4 Measurement Campaign and Simulation Setup . . . . . . . . . . . . . 302.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423 Periodic Connectivity in Body Area Networks and Its Implications forScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.2 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2.1 Periodic Actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473.2.2 Connectivity, Periodicity and Link Classification . . . . . . . . . . . . 473.2.3 Scheduling for Periodic Actions . . . . . . . . . . . . . . . . . . . . . . 473.2.4 Action Recognition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.2.5 Energy Consumption Lower Bound . . . . . . . . . . . . . . . . . . . 493.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503.3.1 Proposed Scheduling Technique . . . . . . . . . . . . . . . . . . . . . 513.3.2 Measurement Campaign and Simulation Setup . . . . . . . . . . . . . 523.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 RSSI-based Distributed Self-Localization for Wireless Sensor Networks inPrecision Agriculture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.2 The Localization Problem and Path Loss Likelihood Function . . . . . . . . . 644.2.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.2.2 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.2.3 A Representative Path Loss Model for Orchard Environments . . . . 684.2.4 Path Loss Likelihood Function . . . . . . . . . . . . . . . . . . . . . . 734.3 Localization Algorithm for Precision Agriculture Applications . . . . . . . . . 734.3.1 General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744.3.2 Localization Algorithm Compatible with Wireless Sensor Networks . . 764.4 Performance Evaluation of The Localization Algorithm . . . . . . . . . . . . 79viTable of Contents4.4.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 804.4.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 884.6 Acknowledgement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895 Directional Path Loss and Its Implications for Node Placement and Net-work Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 905.2 Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925.2.1 Review of Conventional Node Placement Strategies for WSNs . . . . 925.2.2 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.2.3 AODV Routing and Its Performance Under Directional Path Loss . . 955.2.4 Alternative Node Placement Strategies . . . . . . . . . . . . . . . . . 975.3 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985.3.1 Observations of Directional Path Loss in Precision Agriculture . . . . 985.3.2 Representative Path Loss Model and Directivity Degree . . . . . . . . 1015.3.3 Deployment Scenarios and Performance Metrics . . . . . . . . . . . . 1025.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045.4.1 Observation of Directional Path Loss in Precision Agriculture . . . . . 1045.4.2 Effect of Directional Path Loss on Node Connectivity . . . . . . . . . 1065.4.3 Mitigation Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1096 Conclusions and Recommendations . . . . . . . . . . . . . . . . . . . . . . . 1116.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1116.2 Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116viiList of Tables2.1 micaZ Radio+CPU power consumption . . . . . . . . . . . . . . . . . . . . . 322.2 Monitoring wireless body area network . . . . . . . . . . . . . . . . . . . . . . 342.3 Benchmark of different link-state and cluster-based routing protocols in termsof networking metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382.4 Lifetime comparison between the proposed probabilistic routing protocol andcluster-based algorithms with 100 J energy available for each sensor . . . . . . 393.1 Actions of interest and periodic links . . . . . . . . . . . . . . . . . . . . . . . 544.1 (R2,RMSE) for different variants of MED models, modified MED modelsbased on [166] to take the canopy and ground reflection into account as well. . 714.2 Path Loss Model characteristics for above and below canopy level modes . . . 714.3 Average shadowing correlation for pairs of links that are extended with specificangles with respect to each other . . . . . . . . . . . . . . . . . . . . . . . . . 714.4 Deployment Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 814.5 Analytical comparison of the proposed technique with state-of-the-art dis-tributed non-Bayesian techniques . . . . . . . . . . . . . . . . . . . . . . . . . 874.6 Numerical comparison of the proposed technique with state-of-the-art dis-tributed non-Bayesian techniques . . . . . . . . . . . . . . . . . . . . . . . . . 885.1 Parameters for different tessellations corresponding to a WSN with N nodesand inter-node distance d0 deployed in a field with Area A . . . . . . . . . . . 935.2 Performance of the AODV protocol under two different scenarios for the sim-ple network connectivity graph illustrated in Figure 5.2 . . . . . . . . . . . . . 975.3 Simulation Parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1045.4 Path loss characteristics along different directions in the Dawson apple orchards1065.5 (R2,RMSE) for different variants of MED models, modified MED modelsbased on [166] to take the canopy and ground reflection into account as well. . 106viiiList of Figures1.1 A WSN and its main components . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Commercial enabling networking technologies for WSNs . . . . . . . . . . . . 51.3 The applicability space and market share for different PHY, MAC specifications 62.1 Superframe structure of IEEE802.15.4 MAC layer protocol . . . . . . . . . . . 202.2 Packet transfer round and transmit power update window structure . . . . . . 242.3 PDR with respect to RSSI collected from measurements with micaZ motes . . 272.4 On-body sensor placement in our studied scenario . . . . . . . . . . . . . . . . 282.5 The relationship between integrality gap (IG), Mopt, Mround and Mreal . . . . 282.6 Mobility model and Markov graph of transition probabilities between actions 332.7 RSSI and EWMA over waist-chest and waist-wrist links for four actions . . . 352.8 RSSI variation over limb-limb and limb-torso links during change of actions . 352.9 PER with respect to transmit power level for different on-body links andfitness activities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.10 IG with respect to remaining energy in the sensors . . . . . . . . . . . . . . . 372.11 Performance of the proposed link-state routing protocol in terms of commu-nication overhead and balanced energy depletion . . . . . . . . . . . . . . . . 382.12 Spanning trees resulted from LP during running activity . . . . . . . . . . . . 392.13 General spanning tree topologies for classic cluster-based routing protocols . . 402.14 Applicability range of the proposed link-state routing protocol . . . . . . . . . 423.1 Received power over waist-wrist link with PTx = −25 dBm . . . . . . . . . . . 543.2 Received power over waist-ankle link with PTx = −20 dBm . . . . . . . . . . 543.3 Action recognition accuracy with respect to classification energy to aggregateenergy consumption ratio for r = 1kB/s with two actions done in a row . . . 553.4 Per packet energy consumption comparison between proposed scheduling andlower bound on periodic links . . . . . . . . . . . . . . . . . . . . . . . . . . . 55ixList of Figures3.5 Per packet energy consumption comparison between proposed scheduling andlower bound on non-periodic links . . . . . . . . . . . . . . . . . . . . . . . . . 563.6 Approximate applicability range of the proposed scheduling algorithm . . . . 564.1 Measurement campaign scenarios inside the Dawson orchards . . . . . . . . . 704.2 Grid structure of the agricultural field . . . . . . . . . . . . . . . . . . . . . . 724.3 Collected Path loss samples for below and above canopy propagation modes . 724.4 Discretization of the path loss likelihood function . . . . . . . . . . . . . . . . 744.5 Two landmark arrangements with different line of sight degrees . . . . . . . . 814.6 Location heat map for 6 and 8 landmarks in the field . . . . . . . . . . . . . . 824.7 Effect of landmark and unknown node degree on 2DRMS in addition to effecttransmit power on node degree . . . . . . . . . . . . . . . . . . . . . . . . . . 824.8 2DRMS for different node densities and landmark arrangements . . . . . . . . 834.9 2DRMS variation for different transmit power level and number of landmarks 845.1 Different regular topologies; square, triangular and hexagonal networks . . . . 935.2 Connectivity graph of a simple network . . . . . . . . . . . . . . . . . . . . . 975.3 Measurement campaign scenarios for characterization of directional path loss 1005.4 No shadowing transmission range, r0, for different directional path loss scenarios1025.5 Effect of path loss directivity degree on node connectivity . . . . . . . . . . . 1035.6 Path loss comparison between along, cross, 30◦, 45◦, and 60◦ directions . . . . 1055.7 Connectivity for different types of directional links . . . . . . . . . . . . . . . 1055.8 Behaviour of mean hop count with respect to mean node connectivity . . . . 1065.9 Behaviour of network lifetime with respect to mean node connectivity resultedfrom various path loss directivity degrees is shown. . . . . . . . . . . . . . . . 1075.10 Behaviour of mean node connectivity with respect to directivity degree . . . . 1085.11 Behaviour of network performance metrics with respect to elongation index . 1085.12 Approximate applicability range of the proposed mitigation strategy . . . . . 109xList of Abbreviations2DRMS Twice distance root mean squareADMM Alternating direction method of multipliersAOA Angle of arrivalAODV Ad hoc on-demand distance vectorBC British ColumbiaBI Beacon intervalBP Belief propagationBS Base stationCAP Contention access periodCFP Contention free periodCH Cluster headCI Confidence intervalCICADA Controlling access with distributed slot assignmentCIR Channel impulse responseCOTS Commercial off-the-shelfCSMA Carrier sense multiple accessCTS Clear to sendDIY Do it yourselfDSDV Destination-sequenced distance vectorDSR Dynamic source routingE-LEACH Energy-LEACHECG ElectrocardiographyEEG ElectroencephalographyEMG ElectromyographyEWMA Expected weighted moving averageGA Genetic algorithmGPS Global positioning systemxiList of AbbreviationsGTS Guaranteed time slotHCF HART communications foundationHDD High directivity degreeHIT Hybrid indirect transmissionHMM Hidden Markov ModelHSA Handheld spectrum analyzerIG Integrality gapIMU Inertial measurement unitIP Internet protocolIoT Internet of thingsJJ Jumping jacksK-S Kolmogorov-SmirnovLDD Low directivity degreeLEACH Low energy adaptive clustering hierarchyLLF Link likelihood factorLOS Line of sightLP Linear programmingLPD Lateral pulldownsLS Least squareM-LEACH Multihop-LEACHMAC Media Access ControlMAP Maximum a posterioriMED Modified exponential decayMILP Mixed integer linear programmingML Maximum likelihoodMMSE Minimum mean square errorMRF Markov random fieldNBP Nonparametric belief propagationOLSR Optimized link state routingPAWSN Precision agriculture wireless sensor networkPDA Personal digital assistantPDR Packet delivery ratioPEGASIS Power efficient gathering in sensor information systemsPER Packet error ratexiiList of AbbreviationsPHY Physical layerPRPLC Probabilistic routing with postural link costsQoS Quality of ServiceRFID Radio-frequency identificationRMSE Root-mean-square errorRN RunningRREP Route replyRREQ Route requestRSSI Received signal strength indicationRTS Request to sendRW RowingRx ReceiverSD Superframe durationSDP Semidefinite programmingSGO Sequential greedy optimizationSO Superframe orderSOCP Second-order cone programmingSPA Sum product algorithmTDMA Time division multiple accessTICOSS Timezone coordinated sleep schedulingTOA Time of arrivalTPA Transmit power adaptationTx TransmitterUDG Unit disc graphUHF Ultra-high frequencyUWB Ultra wide bandVHF Very high frequencyVSG Vector signal generatorWASP Wireless autonomous spanning tree protocolWBAN Wireless body area networkWLAN Wireless local area networkWSN Wireless sensor networkZC ZigBee coordinatorZR ZigBee routerxiiiAcknowledgementsThere are so many individuals without whose help, I would definitely not have succeeded tocomplete the PhD program. First of all, I would like to thank my advisor, Prof. Michelson,for the productive meeting sessions we had throughout the entire program. His suggestionsduring write up and outlining of manuscripts were without doubt a blessing. Such washis influence, that at times I got the impression of grasping a concept when I myself wasexplaining the problem and state-of-the-art to him. I would also like to thank Prof. VictorLeung, my proposal committee member, for his productive suggestions particularly on thefirst part of thesis which is devoted to wireless body area networks. His hints greatly helpedtowards clarification and presentation of some major concepts in first and second chapters ofthe thesis. Besides Victor Leung, Prof. Shahriar Mirabbasi and Prof. Jane Wang were theother proposal committee members who made very useful suggestions for future directionof my program. Many thanks to them.I would like to thank Maziyar Hamdi and Kaveh Shafiee for their invaluable contribu-tions during different stages of my program. Further, Maziyar was always supportive withhis math skills when it came down to mathematical formulations. The on and off-topicarguments we had kept my mind fresh. On the other hand, Kaveh helped with body areanetwork measurement campaigns and thorough proofread of chapters 2 and 5 of the thesis.My collaborations with these two fellows played a key role towards enhanced readability andpresentation of the thesis in many aspects.Many thanks to Radio Science Lab 2012 and 2013 summer students who toleratedextremely harsh conditions in Similkameen, British Columbia to accelerate and facilitateour measurement campaigns and data analysis. I also appreciate SemiosBio, a startupcompany in Vancouver, who funded and supported our precision agriculture measurementcampaigns and granted us access to apple orchards in Keremeos. Last but not least I wouldlike to thank Pedram Ataee, Arghavan Emami, Sina Mashayekhi and Robert White for theirsupport and kindness throughout the struggles and their presence during good times andlaughters.xivDedicationTo my beloved parents and brother who made a lotof sacrifices to help me pursue my dreamsxvChapter 1IntroductionWireless sensor networks (WSNs), as illustrated in Figure 1.1, are generally defined as a setof sensors with wireless links between them which are scattered in an environment to coop-eratively sense one or several features and forward them to a gateway or a computer so thata decision is made [1–4]. These networks are distinguished from wireless access networks by:1) their mesh architecture and reliance on higher layer protocols and algorithms to performrouting, scheduling, localization, and node placement, 2) their need to operate for long pe-riods of time with only limited access to battery or scavenged power. Moreover researchershave proposed higher layer techniques in order to meet various requirements in the network.Many different routing, scheduling and media access control (MAC) algorithms have beensuggested to meet quality of service (QoS) requirements in terms of latency, connectivity,fairness and energy efficiency [5–7]. Deterministic and random node placement techniquesare proposed to meet area coverage, network connectivity, network lifetime and data fidelity[8]. Various cooperative localization techniques have also been devised to address differentscenarios in terms of number of nodes, mobility model, and presence or absence of landmarksin the network [9].Energy conservation has long been an important goal for WSN developers becauseWSNs are battery operated and batteries are hard to access for recharging or battery re-placement. Moreover, rise of WSNs over the past two decades and considering that almost80% of the WSN energy is spent on communication [10], lots of higher layer algorithmsand enabling technologies have emerged in order to facilitate communication between WSNcomponents. The potential for reducing energy consumption in such networks by reducingthe strength and/or frequency of transmission and increasing the duration of sleeping timehas long been recognized. In other words, IEEE802.15.1, IEEE802.15.4 MAC and physicallayer (PHY) specifications [11, 12] in addition to radio-frequency identification (RFID) wereproposed and frequently modified to address short range communication in wireless personalarea networks (WPANs). WSNs have revolutionized our lives in many aspects varying fromhealthcare and fitness to home automation, industrial and military applications [13, 14].1Chapter 1. Introduction(a) A WSN is composed of a set of distributedsensors and a gateway(b) Sensor nodes are composed of different entitiesand modulesFigure 1.1: A WSN is composed of a set of sensors for monitoring and a gateway which isresponsible for data collection. A sensor node is composed of different components with radiobeing accountable for communicationThe impact of WSNs on various industrial, military, and consumer applications has beenincreasingly growing over the past two decades. Particularly in body area networks, a widerange of applications varying from athlete performance monitoring in indoor and outdoorsports fields to elderly monitoring applications in clinics and homes have emerged [15, 16].Also in precision agriculture, a wide variety of applications such as automated irrigation,fruit growth, soil health monitoring, and pest management has increased the profitability ofagricultural fields [17].A recent survey by IDTechEx [18] shows that the WSN market will grow from $0.45 bil-lion in 2012 to $1.8 billion in 2024, whereas a different market study by Frost & Sullivan,anticipates the earned revenues to grow from $1.2 billion in 2014 to $3.26 billion in 2020[19]. Particularly in healthcare industry, there will be 18.2 million health WSN systemsworldwide, whereas wearable/implantable WSNs will increase by a 75% compound annualgrowth rate over the next five years [20]. Wireless healthcare solutions will increase by21.1. Significance of Higher Layer Algorithms in Wireless Sensor Networks1600% over the next 5 years [20] as the elderly population (people of age 60 years and over)in the world which was 759 million in 2010 will reach 1,198 million in 2025 and this groupwill occupy 15% of the world population [21]. As a different application, agriculture indus-try, increasingly growing world population which will reach 9 billion by the middle of thecentury [22], along with thinning land, water and resources raises the importance of WSNsdeployment to help precision agriculture for resource and crop management. The precisionagriculture market, as one of WSNs applications, will be worth $4.8 billion by 2020 [23].1.1 Significance of Higher Layer Algorithms in WirelessSensor NetworksThe impact of propagation impairments on the PHY and to the lesser extent on the MAClayer of WSNs has long been considered. Further, adjustment of PHY layer parametersdirectly depends on channel propagation. In MAC layer studies, even though retransmissionsare attributed to collisions, the effect of fading and path loss on packet drops and MAC layerperformance in general has been taken into account. Moreover, impact of realistic channelassumptions on throughput and power consumption of MAC protocols, e.g., IEEE802.15.4,is proved to be significant [24]. In IEEE802.11 contention-based MAC protocol, features suchas handshaking which work based on request to send (RTS)/clear to send (CTS) messagesto address the hidden terminal problem are affected by directional path loss and asymmetriclinks. Furthermore, carrier sensing which is used to access the channel is affected by thesephenomena [25].On the other hand, few previous studies have sought to assess the impact of propa-gation impairments on higher layer protocols and algorithms or have devised schemes formitigating such impacts. Even though impact of unrealistic channel propagation assump-tions such as circular radio transmission area, i.e., unit disc graph (UDG), link symmetryand power-law attenuation model has been recognized [25, 26], little attention has beenpaid to effect of these impairments on the design of higher layer techniques, e.g., routing,scheduling, localization and node placement. Further, mitigation strategies that increaseenergy efficiency and network lifetime in the presence of such impairments have not beenstudied adequately. In the remainder of this chapter, we present recent developments inWSNs higher layer algorithms and proceed to present their limitations and the manner inwhich we might address them.31.2. Review of Recent Developments in Wireless Sensor Network Technology1.2 Review of Recent Developments in Wireless SensorNetwork TechnologyIn this section, we first briefly define wireless body area networks (WBANs), precisionagriculture wireless sensor networks (PAWSNs) and proceed with state-of-the-art enablingtechnologies, their limitations and our objectives in order to address them.Wireless Body Area Networks: WBANs are defined as a set of invasive or non-invasiveminiaturized sensors responsible to monitor functions of the human body or environment[16, 27, 28]. WBANs support a wide range of applications in different industries such asmilitary, healthcare, gaming, entertainment and sports.Precision Agriculture Wireless Sensor Networks: Several definitions are suggestedfor precision agriculture [29–31], however in general it is defined as management strategy thattakes advantage of information technologies to enhance resource utilization and increase thebenefits resulted from crop management in agricultural fields. The most critical requirementin precision agriculture is a reliable decision support system so that number of correctdecisions per unit area of land linked with net benefits rises [30]. Some of the precisionagriculture applications are irrigation, pest management, fruit growth and soil monitoring.PAWSNs serve as the technology to bring data from the agricultural field to the base station(BS) by means of sensors and wireless technology so that such benefit making decisions aremade.1.2.1 Key Advances and Enabling TechnologiesWith IEEE802.15.4 becoming more popular, different alliances and groups of companieswere formed to propose network protocols running on IEEE802.15.4 and to address differenttypes of applications [32]. ZigBee Alliance proposed ZigBee networking protocol for a widerange of applications varying from patient monitoring in healthcare to environment monitor-ing in precision agriculture. Z-Wave Alliance which, as of today, is composed of more than350 companies, suggested Z-wave communication standard for home automation applica-tions [33]. HART communications foundation (HCF), comprised of 37 companies, providedWirelessHART for automation in process industry [34]. With the rise of internet of things(IoT), interoperability between Internet Protocol (IP)-based networking and IEEE802.15.4compatible devices gained significant importance [35]. This led to IPv6 over Low power41.2. Review of Recent Developments in Wireless Sensor Network TechnologyWPANs (6LoWPAN) being proposed by a working group in the internet area of InternetEngineering Task Force (IETF) so that nodes in the WSN are connected to the internet.The enabling underlying and networking technologies for WSNs along with their features areshown in Figures 1.2 and 1.3. These standards are important from the perspective that theyare deployed on commercial off-the-shelf (COTS) chipsets that are available in the marketand are shipped to relevant third party companies in large quantities.Figure 1.2: Commercial enabling networking technologies for WSNs; The table is extracted from[36].In addition to these industrial and commercial technologies, a large number of under-lying MAC and higher layer networking protocols are proposed by research groups and labs.Here, we will discuss state-of-the-art enabling technologies that appear in the literature andwill proceed with the missing part which will be addressed in this dissertation. We will bemore focused on two specific applications of WSNs which are the main focus of this work;WBANs and PAWSNs. Even though throughput, latency, reliability are WSN performancemeasures, power consumption is the main concern in the way of WSNs deployment. There-fore, network reliability, latency and other QoS metrics are often compromised in favour ofenergy efficiency. Methods adopted in order to mitigate energy consumption are dividedinto PHY, MAC and network layer techniques. In PHY, transmission bit rate, frequencyband, modulation scheme and transmit power level are adjusted in order to meet the chan-51.2. Review of Recent Developments in Wireless Sensor Network Technologynel propagation characteristics. On the other hand MAC protocols aim to minimize idlelistening, collisions, amount of control packets and overhearing which are major reasons ofpower consumption in MAC layer [7]. On the other hand, a suitable network layer techniqueis required to be energy efficient in terms of setup (route discovery), route maintenance anddata communication phases.(a) Underlying PHY and MAC specificationsproposed for different applications extracted from[37](b) Market share for IEEE802.15.4-basednetworking technologies extracted from [38]Figure 1.3: The applicability space for different PHY and MAC specifications in addition tomarket share for networking protocols which are built upon IEEE802.15.4Many MAC and routing protocols which specifically aim to address WBAN and PAWSNapplications are proposed in the literature. The contribution of these in-house developedMAC algorithms mostly originates from the synchronization mechanism that reduces MACoverhead energy consumption. Further, time division multiple access (TDMA)-based MACprotocols, e.g., BodyMAC [39], MedMAC [40] and WiseMAC [41] are specifically proposedfor deployment in WBANs. As far as routing is concerned and particularly for WBANs,literature is more extensive. Here, we summarize these routing protocols and proceed topresent higher layer techniques in precision agriculture.Routing and Scheduling in WBANs: Even though in the general WSN context,routing protocols are divided into three categories, including hierarchical, location-basedand data-centric [5], in the WBAN literature they mostly fall into hierarchical [42–44],temperature-based [45], cross layer [46–48] and link-state [49–53] routing protocols each of61.2. Review of Recent Developments in Wireless Sensor Network Technologywhich aiming to address a specific set of requirements. In link-state routing protocols, acost function which incorporates link connectivity, remaining energy of the sensors or bothis assigned to links so that the routing tables are updated in a way that energy depletionin sensors is balanced and reliable routes are formed. Hierarchical routing protocols areinspired by classic Low Energy Adaptive Clustering Hierarchy (LEACH) [54] and Power-Efficient Gathering in Sensor Information Systems (PEGASIS) [55] protocols, and mostlywork based on forming clusters or chains of nodes and conducting data aggregation overthem. After forming clusters or chains of sensors, one head is designated to collect packetsfrom other sensors in the cluster or chain and forward them to the BS. In temperature-based routing protocols, traffic flow in the network is distributed so that temperature ofbody organs for intrusive WBANs and limbs for non-intrusive WBANs does not exceed athreshold. Cross layer studies in WBANs, mostly focus on integration of MAC, routing andapplication layer than taking channel propagation into account. Further, several schedulingtechniques have been proposed for WBANs as well which can work in conjunction withMAC and routing protocols. Ruzelli et al. [46], have proposed timezone coordinated sleepscheduling (TICOSS) which is a scheduling algorithm built upon IEEE802.15.4 MAC layer.TICOSS is based on dividing network to different time zones where sensors belonging to thesame time zone, simultaneously transmit their data to the nodes belonging to contiguouszone, while nodes in other zones are sleeping.Latre et al. [47], have proposed wireless autonomous spanning tree protocol (WASP)and Cascading Information retrieval by Controlling Access with Distributed slot Assignment(CICADA) [48] where a spanning tree is set up in a distributed manner and data is forwardedto the sink based on a distributed scheduling. The focus of WASP and CICADA is to providethe desirable end-to-end delay in the network. Store and forward scheduling techniques[56, 57], increase likelihood of a packet reaching its destination by storing the packet atmultiple hops, while opportunistic scheduling techniques [58–60] are designed to maximizeresource utilization in the network while providing fairness among users by allocating thechannel to the user with a more suitable channel state. In these studies, the transmissionpower is adjusted to the condition of the underlying fading channel for achieving a desirabledata rate. However, the continuous link assessment make these techniques incompatiblewith WBANs where nodes ideally turn their radio off until it is their turn to transmit, as anenergy-saving measure. Another class of WBAN scheduling techniques focus on adaptive oroptimized guaranteed time slot (GTS) allocation in IEEE802.15.4 WBANs in order to meetlatency and fairness requirements or to make best use of bandwidth [61, 62].71.2. Review of Recent Developments in Wireless Sensor Network TechnologyHigher Layer Techniques in PAWSNs: The literature for higher layer techniques inPAWSNs is less extensive compared to WBANs. Most routing protocols proposed for preci-sion agriculture applications are cluster-based with one or multiple gateways placed at thecorners of the agricultural field [63, 64]. Even though IEEE802.15.4 is the most commonshort range scheme used for monitoring applications [65], a few MAC protocols have alsobeen specifically proposed for deployment in PAWSNs [66, 67]. Focus of these works is thesame as in general WSN context where energy saving is achieved by keeping nodes in sleepingmode for longer durations. Further, in [66], a Genetic Algorithm (GA) based MAC proto-col in which GA decides which nodes in the field should stay active or should be assignedcluster-heads is proposed. The proposed work in [67, 68], Ping-Drowsy MAC (PD-MAC)protocol, is more sophisticated and works based on having multiple transmit power levelsand sensitivity levels for sensing. PD-MAC is inspired by more classic contention-basedMAC protocols; S-MAC [69] and T-MAC [70]. In [71], a light-weight Carrier Sense MultipleAccess (CSMA)-based MAC protocol is proposed, while Baggio et al. have deployed T-MACas the underlying MAC protocol [72]. In terms of node placement techniques, square grid isthe most common deployment technique used in literature [73–76], however effects of otherdeterministic node placement techniques, triangular and hexagonal patterns, in terms ofconnectivity and coverage have been discussed under isotropic power-law attenuation modelin the field [76].1.2.2 Key Limitations of Previous WorkAs discussed in Section 1.1, significance of channel impairments and their impact on theperformance of WSNs has been recognized for a long time [25, 26]. Even though Impactof channel propagation on MAC layer algorithms such as IEEE802.15.4 [24] and classicrouting protocols such as ad hoc on-demand distance vector (AODV) and Dynamic sourcerouting (DSR) [25] has been recognized to some extent [25], little attention has been paid toincorporation of channel propagation into design of routing and other higher layer techniques.Most state-of-the-art WBAN higher layer protocols are either implemented on IEEE802.15.4compliant COTS or have been simulated with network simulators such as OMNeT++. Eventhough WBAN performance has been studied in these simulated or implemented practices,either implications of channel propagation on design of these algorithms have been dismissedor integration of realistic models in the simulation environment has not been considered. Onthe other hand, most PAWSN implementations are field trials in vineyards and orchards.Moreover, channel characteristics that can degrade performance of these networks is not81.2. Review of Recent Developments in Wireless Sensor Network Technologystudied.Most WSN routing protocols are composed of setup, data communication and routemaintenance phases which are all affected by channel propagation assumptions. The setupphase in on-demand routing protocols relies on path-reversal technique which fails underlink asymmetry, fast and shadow fading circumstances. Link asymmetry particularly dis-rupts setup phase in location-based and data-centric routing protocols. Further, setup andneighbour discovery phase in location-based routing protocols is based on sufficient nodedensity in the network, accurate localization and high link reliability [77]. Seada et al. [77]have discussed the effect of realistic link packet error rate (PER) models on message over-head, and excessive power consumption in traditional location-based routing protocols thatwork based on greedy forwarding algorithm. In data-centric protocols [78], localized flood-ing occurs in order to create the routing table based on reverse route discovery techniqueswhich rely on link symmetry assumption. Data communication phase works based on circu-lar radio range where path loss is a simple function of distance, i.e., power-law attenuationmodel. Particularly, power efficiency of hierarchical routing protocols such as LEACH [54],PEGASIS [55] and other inspired protocols relies heavily on this path loss model. Routemaintenance phase to recover from broken links which imposes message overhead and con-sequently excessive power consumption, is also hugely affected by fast fading channels. Onthe other hand, in cross layer techniques, a lot of attention has been paid to making use ofthe information from higher layers, i.e., network and application layer, to design MAC layer[79], however channel propagation has not been taken into account.Opportunistic scheduling techniques use spatial and temporal diversity of channel toallocate bandwidth to the user that benefits from better channel state. Even though thesetechniques increase bandwidth utilization, they suffer from communication overhead asso-ciated with idle listening caused by sensing the channel. Only a few of the opportunisticscheduling studies consider the power constraints in the design of their algorithms [80, 81].Transmit power control strategies [52] that work along with most of the scheduling tech-niques still result in high overhead due to frequent link assessments associated with transmitpower adjustment. On the other hand, store and forward techniques achieve desired end-to-end connectivity with low transmit power levels at the expense of multi hop routing andexchange of control packets which result in excessive energy consumption. Moreover, mostexisting scheduling techniques aim to improve connectivity, fairness or dynamic allocationof bandwidth based on traffic. Therefore, they are not energy efficient due to high commu-nication overhead or the fact that they follow different objectives than energy efficiency.91.3. Objectives of This WorkIn terms of cooperative localization techniques, a lot of work has been done on Bayesianand non-Bayesian techniques [82, 83]. The state-of-the-art Bayesian and non-Bayesian tech-niques are not suitable for deployment on IEEE802.15.4 COTS due to the slow or lack ofconvergence, in addition to the the high number of messages that must be exchanged and alsothe computation burden that is imposed on COTS with low memory and processing power.Moreover, existing Bayesian distributed techniques suffer from the communication overheadrequired for setup phase in order to form loop-free graphs. Whereas non-Bayesian techniquesare burdened with excessive communication overhead and computational complexity to solveoptimization problems at each iteration, and therefore suffer from slow convergence. In theseworks, features of channel propagation observed in real world environments and their effecton the performance of these protocols in terms of energy consumption and convergence isdismissed. Further, connectivity among nodes and their cooperation outcome strongly de-pends on underlying channel propagation models, therefore incorporation of these featuresinto design of energy efficient cooperative techniques is of great merit.The literature on node placement techniques is extensive as well, however path lossmodel is not the centre of attention and most efforts are centred around meeting criteria suchas connectivity, coverage, network lifetime and data fidelity [8], while isotropic power-lawattenuation model forms the underlying channel propagation and path loss model. Particu-larly in precision agriculture, more focus has been put on the effects of application on nodeplacement. Furthermore placing the nodes so that better variogram, i.e., independence ofdata points, is achieved has been of more interest while little attention is paid to realisticunderlying path loss model in the agricultural field.1.3 Objectives of This WorkEven though different techniques for node placement, PHY, MAC, and network layers havebeen proposed to make communications in WSNs more energy efficient, channel propaga-tion characteristics must be taken into account in order to achieve more energy efficiency.Further, a lot of work has been done to integrate higher layers such as transport and appli-cation layers into the network layer and routing techniques, however the impact of channelpropagation on design and performance of higher layer protocols is not much explored. Here,we focus on proposing higher layer methods which take channel propagation into accountin order to reduce energy consumption in two radically different WSNs in terms of channelpropagation; WBANs and PAWSNs. Further, we propose higher layer techniques such as101.3. Objectives of This Workrouting, scheduling, localization and node placement that work based on channel propaga-tion implications in specific environments so that energy efficiency and network lifetime areimproved.Deep fades cause WBAN on-demand routing protocols [51, 84] to fail because routingtables will not be valid short after they are established. Scheduling and transmit powercontrol techniques also require excessive amount of beacon exchanges in order to conductlink assessments. These necessitate design of cross layer scheduling and routing protocolsthat work based on appropriate channel propagation assumptions so that energy efficiencyis achieved. On the other hand, large network dimensions in PAWSNs along with differ-ent propagation mechanisms, e.g., ground and canopy reflection, result in directional radiorange which affects higher layer techniques. For example, cluster formation in cluster-basedrouting protocols is significantly influenced by directional path loss and on-demand routingprotocols are affected by link asymmetry in farm environment since long links suffer fromlink asymmetry more than shorter links [85]. It is well known that propagation model affectsconnectivity of the links and routes which consequently has impact on performance of reac-tive routing protocols such as AODV, DSR, optimized link state routing protocol (OLSR)and Destination-Sequenced Distance-Vector (DSDV) [86–89]. However, effects of directionalpath loss observed in realistic environments on such algorithms is dismissed. Particularly,AODV-based protocols are fundamental since they form basis for multi-hop networkingdeployed on IEEE802.15.4 COTS in WSNs. Therefore, node placement techniques thatconsider directional path loss and take distance dependence of path loss in the 2.45 GHzindustrial, scientific and medical (ISM) band into account are critical. This is particularlyimportant since path loss in orchard environment at 2.45 GHz is dramatically different fromhigh frequency (HF)/ very high frequency (VHF) bands [90]. It is worth mentioning thatmost of the proposed path loss models in ultra-high frequency (UHF) band or higher onlytarget excessive path loss through foliage propagation and are very site specific [91, 92].Therefore, these models do not take different propagation mechanisms and directions, forexample along or across the tree rows into account.Here, we present four case studies that demonstrate how higher layer protocols andalgorithms can be devised in order to achieve greater energy efficiency by accounting for thenature of the propagation impairments involved. WBANs and PAWSNs are extreme in termsof channel propagation behaviour and design considerations for higher layer algorithms. Theway channel propagation impairments disrupt the performance of higher layer techniques,particularly routing protocols, is different in these two WSNs [86–89]. In on-body WBANs,111.4. Contributionssevere shadowing is the dominant propagation mechanism and imposes deep fast fades overon-body links while distance is not an important feature. Whereas in PAWSNs, distanceand direction are decisive factors while temporal variations are very small. In addition topropagation environment, these two networks are different in terms of number of sensors,node placement, application, and network lifetime definition. Further, in WBANs, a smallnumber of sensors with heterogeneous applications are scattered on body, constrained tospecific locations and decision making in terms of higher layer algorithms is centralized. Onthe other hand, in PAWSNs, deterministic node placement is the most common approach,while distributed higher layer algorithms are recommended due to high number of nodesin the field. Network lifetime definition is also different in these two types of networks.Moreover, in WBANs each node is responsible for observing a different feature thereforefailure of each of these nodes disrupts performance of the network while in PAWSNs, alarge number of sensors monitor a single parameter therefore failure of large number ofthese nodes is still tolerable. In this work we propose routing, scheduling, localization andnode placement techniques that work based on channel propagation implications in specificenvironments so that energy efficiency and network lifetime are improved. To this end, thethesis is broken down to two parts each of which devoted to a different environment.1.4 ContributionsIn the first WBAN case study, we propose a routing protocol that uses linear programming(LP) techniques to ensure that network lifetime is maximized and all nodes in a WBANexpend energy at a similar rate during stationary human actions. Even though single-hopstar networks are the most frequently implemented practice, they may not be efficient interms of achieving connectivity or network lifetime. Further, whether multi hop or singlehop communication needs to be used depends on many criteria [93]. On the other hand, themain limitation of the existing state-of-the-art routing protocols proposed for WBANs is theamount of control message overhead nodes use to estimate reliability of the links in additionto remaining energy in the sensors so that balanced energy depletion and high connectiv-ity are achieved. In order to address this limitation, we propose a link-state probabilisticrouting protocol based on IEEE802.15.4 MAC and PHY which enhances WBAN lifetime forstationary actions by: 1) conducting link assessment and transmit power level adjustmentonly when action variations are tracked, 2) using LP techniques to assign link likelihoods inorder to ensure that balanced energy depletion is achieved, therefore lifetime is maximized.121.4. ContributionsIn the second WBAN case study, we propose a scheduling algorithm that accounts forthe periodic shadowing which may be observed over many WBAN links and thereby reducethe transmit power required to transfer information and thereby maximize energy efficiencyat the expense of latency. A scheduling technique that achieves the desired end-to-endconnectivity with low transmit power level and hop count at the expense of latency helpssave energy for delay-tolerant WBAN applications such as ambient assisted living in which,latency can be tolerated since data analysis would be carried out in an offline manner.We use measurements to show that periodic prolonged actions, e.g., fitness activities,cause on-body links, particularly extremity-torso links, to undergo periodic predictable con-nectivity sessions that can be exploited for low transmit power single-hop communications.The proposed technique could work in conjunction with routing protocols, e.g., the proba-bilistic routing protocol suggested in the first WBAN case study, to lower transmit powerover periodic links over which, delay tolerant WBAN applications are running. Beside peri-odicity that is used for energy efficient communication, diversity of received signal strengthindication (RSSI) samples over such links provide us with features, e.g., mean and standarddeviation which makes simple real-time action recognition based on naive Bayes classificationpossible.In the second pair of case studies, we focus on PAWSNs; In the first case, we proposean energy efficient localization algorithm based on the Bayesian model for information ag-gregation which is well-suited to run seamlessly on IEEE802.15.4 COTS. Further, in theroute discovery phase of AODV, which forms the basis for routing in IEEE802.15.4 compli-ant modules, the node that is set to send its data to the gateway, originates a route request(RREQ) packet that will be multicast by every receiving node so that ID of the nodes thatform the shortest path from the originating node to the gateway is logged. Consequently,gateway sends a route reply (RREP) packet over the shortest path to make the nodes awareof their next hop. Therefore, a cooperative localization algorithm in which, outgoing mes-sage by each node fits inside a IEEE802.15.4 packet, has a low computational burden thatcan be solved in COTS with low processing power and runs in parallel is significantly im-portant. The algorithm is very beneficial since the cost associated with global positioningsystem (GPS) or time and labour associated with manual localization will grow significantlyfor large WSNs deployed in large fields.The proposed algorithm, uses a Bayesian model for information aggregation and in-dependence of shadowing over long links in agricultural fields to achieve energy efficiencyand scalability. Scalable communication and computational complexity with respect to the131.5. Outlinenumber of nodes are achieved at the expense of accuracy while requirements for precisionagriculture applications such as pest management are still met. The scalable RSSI-basedalgorithm proposed in this work, overcomes these limitations by: 1) using only local distanceestimates with respect to neighbouring nodes, and 2) using a message passing schedule whichbenefits from a fixed size outgoing message that does not grow with number of neighbouringnodes, and 3) low computational complexity where computations only grow with field sizeand only involves summations and multiplications as opposed to non-Bayesian techniqueswhere optimization problems need to be solved.In the second case, we address the limitations of previous work in terms of char-acterizing anisotropic path loss in realistic environments and discuss implications of thisphenomenon on node placement, and performance of routing protocols. Moreover, first weuse measurements in a high density apple orchard to demonstrate that directional path lossis a real phenomenon in real world man-made and row-like environments such as agricul-tural fields, warehouse and libraries. We proceed to show that its impacts on performancemetrics, i.e., network lifetime and latency of routing protocols such as AODV is measur-able. Consequently, as a mitigation strategy, we suggest elongated grid deployment, i.e.,decreasing internode distances along impaired directions in order to make node connectivityalong various directions more uniform, therefore improving network lifetime and latency.This technique in fact mimics behaviour of isotropic, i.e., non-directional, path loss by dis-tributing neighbouring nodes in a more uniform way along different directions which helpsnetwork achieve higher lifetime as a result of higher time it takes network graph to becomedisconnected.1.5 OutlineThis dissertation is divided into two parts that focus on WBANs and PAWSNs respectively.Chapter 2 proposes a link-state probabilistic routing protocol for maximizing lifetime inWBANs, while in Chapter 3, we propose a scheduling technique for periodic actions whichis in complementary with the routing technique proposed in Chapter 2.In Chapter 4, we propose a novel localization algorithm based on Bayesian model forinformation aggregation which is well suited to pest management application in agriculturalfields. In Chapter 5, we demonstrate that directional path loss exists in the apple orchardsand propose node placement strategies to mitigate the effects of this phenomenon on theperformance of AODV-based routing protocols in similar environments. In Chapter 6, we141.5. Outlineconclude the thesis with conclusions regarding the effectiveness of our proposed schemes, thelimitations of our algorithm and the implications for current research practice in additionto recommendations for the future research.15Chapter 2A Routing Protocol for Maximizingthe Lifetime of Body Area Networks2.1 IntroductionThe use of link-state routing techniques to improve lifetime and connectivity of WBANshas been proposed in the past. The aim is to assign cost metrics or link likelihood factorsthat cause nodes with lower remaining energy, unreliable links or both to be avoided. Here,we utilize a novel transmit power control algorithm to meet connectivity requirements withminimum communication overhead and LP techniques to assign link likelihoods, i.e., the as-signment probabilities of next hops, so that WBAN lifetime is maximized. Further, transmitpower levels and link likelihoods are updated only once major change in actions or posturesis tracked. The algorithm is well-suited to WBAN monitoring applications with stationaryactions and postures, the duration of which is significant compared to the packet transferdelay defined by QoS requirements, e.g., 250 msec. To the best of our knowledge, this is thefirst work that analytically formulates lifetime maximization for routing in IEEE802.15.4WBANs. Further, LP which is used to calculate link likelihood factors for lifetime maxi-mization and balanced energy depletion works in conjunction with transmit power controlwhich significantly lowers communication overhead in order to achieve maximum WBANlifetime.Design of energy efficient routing protocols that improve network lifetime is one of themajor challenges in WBANs since energy resource constraints are more severe compared toother conventional types of WSNs and also due to limited access to batteries [94]. Further,as opposed to conventional WSNs, scalability is less of an issue for WBANs than energyconsumption because most of these networks consist of relatively low number of sensors andactuators that perform a variety of functions [51]. These characteristics cause most WBANrouting techniques to be case specific since there is no straightforward design in terms ofmulti-hop networking that could encompass all applications and situations [93]. In general,162.1. Introductionhowever these protocols are classified into temperature-based, cluster-based, and link-staterouting protocols with the latter two being more focused on energy efficiency, therefore morerelevant to our work.Cluster-based routing protocols aim to increase lifetime by decreasing inter-clustertransmission distances and switching CHs to guarantee balanced energy depletion amongnodes. The CHs are responsible for aggregating data from cluster nodes and send it to aBS [42–44, 54, 55]. The energy efficiency of these protocols mostly lies in the assumptionsregarding channel and transceiver characteristics. Further, the power-law attenuation modelmakes these hierarchical routing protocols suitable mostly for static WSNs deployed in largeenvironments rather than WBANs with small number of sensors which experience verydynamic link behaviour.The majority of networking techniques that aim to address energy efficiency in WBANsare link-state routing protocols. In these protocols, a cost function that incorporates linkconnectivity, the remaining energy of the nodes, or both, is assigned to the links so that rout-ing tables are updated in a way that energy depletion in sensors is balanced. A probabilisticrouting protocol, PROPHET, proposed for WSNs [95] has inspired several WBAN link-stateprotocols published afterwards [49–51, 96, 97]. In PROPHET, a metric called delivery pre-dictability is updated based on the frequency at which neighbouring nodes encounter eachother and consequently messages are forwarded on paths with higher destination connectiv-ity. In [49], Quwaider et al. defined link likelihood factor (LLF) and proposed probabilisticrouting with postural link costs (PRPLC) which takes history of the links and therefore thelocality of neighbours, into account as well. An extension of PRPLC which integrates inertialmeasurement unit (IMU) sensors for better locality recognition is proposed in [50]. Later,Maskooki et al. proposed opportunistic routing which is based on store and forward routingwith nodes storing data and waiting for neighbours with better connectivity to BS to be-come available [51]. The aforementioned works are more suited to intermittently connectedand delay tolerant networks with ultra-short range RF transceivers where the network con-nectivity graph is constantly changing. Even though these techniques yield an acceptablePDR, energy consumption and delay are sacrificed due to high number of transmissions andpacket storing nature of protocol respectively.There are a number of link-state routing protocols that incorporate transmit powercontrol as well [52, 98, 99]. Nabi et al. devised a similar approach to [51] except that transmitpower adaptation (TPA) is integrated [52]. Further, the nodes keep track of neighbours andutilize transmit power control to consume minimal transmission power while maintaining a172.1. Introductionpredetermined link quality. In [53], a centralized link-state routing protocol along with TPAis proposed. In every cycle, nodes measure received signal strength indication (RSSI) overthe connected links, merge it into their remaining energy and forward it to a host. The hostmakes decision on transmit power level and routing table of each node based on updatedlink costs and Dijkstra’s algorithm. The problem with this work and similar approaches isthe excessive control message overhead required for link quality assessment at the end ofeach transfer round, i.e., duration after which sensors will have one round of data deliveredto the sink, and also for sensors to transmit the control data to the BS. In addition to this,the computational complexity involved with running Dijkstra’s algorithm in the beginningof every transfer round takes a toll on access point battery which is usually a personal digitalassistant (PDA) or a cellphone. Therefore, a routing protocol that could achieve maximumlifetime without remarkable communication overhead and frequent link cost assignment iscritical for low data rate, class 0, WBAN monitoring applications.In this work, we introduce a suboptimal probabilistic link-state routing protocol withtransmit power control that is well-positioned to maximize WBAN lifetime, i.e., the timespan before the first sensor in the network dies. In the proposed protocol, based on assignedtransmit power levels and remaining energy in the sensors, sink solves a LP problem toderive a traffic flow distribution matrix with its elements representing link likelihoods, i.e.,the probability that each node would be assigned as next hop to the other node. To bemore specific, our work is close to [49] from the LLF assignment stand of view, however asopposed to [49] where the objective is better end-to-end connectivity, in our work likelihoodsare derived so that network lifetime is maximized. To the best of our knowledge, this is thefirst work that formulates lifetime maximization problem as a LP with MAC layer andtransceiver radio characteristics integrated into formulation. The algorithm is particularlyuseful for realistic mobility scenarios with subject person doing an action or holding onto aposture for long amount of time compared to transfer round duration, i.e., stationary actions.This is a realistic mobility model for many daily activities since most postures and actionsinvolved in WBAN monitoring context, e.g., fitness or patient monitoring are stationary,i.e., last relatively long and follow a repetitive pattern as well. Despite low communicationoverhead, the proposed algorithm achieves lifetime maximization by:• engaging in new transmit power selection only when significant variations in expectedweighted moving average (EWMA) of path loss samples over limb-torso links is de-tected,• updating traffic flow distribution matrix only when transmit power levels are updated.182.2. ConceptsWe call the duration between the transmit power level and traffic flow distribution updates,the transmit power update window. Moreover, based on data collected during our measure-ment campaigns, we learned that the EWMA of path loss samples over limb-torso links is astrong measure of change of action or posture and starting the new transmit power updatewindow, whereas the variations over limb-limb or torso-torso links is a lot milder.The remainder of this chapter is organized as follows; In Section 2.2, we present a briefbackground on system model including IEEE802.15.4 MAC layer specifications, a radiomodel for RF transceivers and data delivery model for WBAN applications, afterwardsproceed with lifetime maximization problem formulation. In Section 2.3, we present thesteps that lead up to the algorithm which solves the problem formulation derived in Section2.2. Evaluation of our algorithm for a specific monitoring WBAN consisting of pulse, bloodflow, respiration, electrocardiography (ECG), temperature and glucose sensors during fitnessactivities is conducted in Section 2.4. We finish the paper in Section 2.5 with conclusionsregarding effectiveness of the proposed algorithm and its limitations.2.2 ConceptsWe present our system model in Section 2.2.1 which forms the basis for the WBAN lifetimemaximization problem formulation derived in Section 2.2.2.2.2.1 System ModelIn this section, we present the system model in terms of MAC layer and radio characteristics,data delivery model and QoS requirements. These features play a key role in problemformulation and the proposed routing algorithm.IEEE802.15.4 MAC Layer: IEEE802.15.4 defines the physical and MAC layer specifi-cation for low data rate WSNs [12]. MAC layer in IEEE802.15.4 is defined within beacon-enabled and non-beacon-enabled modes. In non-beacon-enabled mode, the nodes in thenetwork compete based on non-slotted carrier sense multiple access with collision avoidance(CSMA/CA), whereas in beacon-enabled mode, they operate based on superframe struc-tures which are bound within beacon packets. Time division multiple access (TDMA) andcontention-based communication are supported via contention free period (CFP) and con-tention access period (CAP) respectively. Beacon-enabled mode allows adaptation of lowduty cycle frames, i.e., nodes can sleep during inactive period for energy conservation. The192.2. Conceptssuperframe structure of beacon-enabled mode is illustrated in Figure 2.1. Considering theperiodic nature of the WBAN monitoring applications and the fact that the size of suchnetworks are relatively small, we adopt the beacon-enabled mode of the MAC layer so thatTDMA feature of the specification with GTS is supported [15]. Beacon interval (BI) and1 2 76543 8CAP CFPBeacon BeaconInactive Period9 10 11 12 13 14 15Superframe Duration (SD)Beacon Interval (BI)GTSFigure 2.1: Superframe structure of IEEE802.15.4 MAC layer protocolsuperframe duration (SD) are adjusted using beacon order (BO) and superframe order (SO)respectively, whereBI = BaseSuperFrameDurationBO,SD = BaseSuperFrameDuration× 2SO,BaseSuperframeDuration = BaseSlotDuration×NumSuperframeSlots,(2.1)and 0 ≤ SO ≤ BO ≤ 14, and BaseSlotDuration=15.36 msec. Therefore, superframe dura-tion and beacon interval could vary between 15.36 msec. and 251.7 sec. based on applicationand networking requirements. Note that BI is adjusted based on the WBAN transfer roundwhich was introduced in Section 2.1 and is determined based on QoS requirements that willbe explained later in this section.Radio Model: The transmitter and receiver power consumption model plays a key rolein energy expenditure of the nodes and consequently network lifetime. Wang et al. [100]have proposed a power consumption model for CC2420 modules, that are widely used inIEEE802.15.4 studies. The transmitter power consumption, Pt(d), denotes power consump-tion of the transmitter’s radio in order to meet the desired Signal-to-noise ratio (SNR)at distance d while Pr is the receiver’s radio power consumption. These parameters are202.2. Conceptsmodelled byPt(d) = Pelec + Pa(d),Pr = const,(2.2)where Pelec is a constant term representing the power dissipated in the electronic circuit ofthe module. The power consumed at power amplifier is denoted by Pa(d) and is a functionof transmit power shown by Ptx(d) that represents required transmit power in order to meetthe desired SNR at distance d,Pa(d) = Ptx(d)/η, (2.3)where, η denotes power amplifier efficiency.Data Delivery Model: Depending on the application, the data delivery model for WSNscan be continuous, event-driven, query-driven or hybrid [5]. WBAN monitoring applicationswork based on continuous data delivery model since sensors send data to the sink at adetermined rate and in a continuous manner. In terms of data rate, WBAN applicationsare divided into three groups [40];• Class 0: Low grade data; applications such as temperature monitoring, respiratory,and pulse,• Class 1: Medium grade data; applications such as ECG, electroencephalography (EEG)and blood pressure, and,• Class 2: High grade data; applications such as medical imaging, video, and electromyo-graphy (EMG).This work is focused on Class 0 and low data rate Class 1 applications with continuous datadelivery model.Quality of Service: WBANs are very diverse with different applications having differentQoS requirements in terms of latency, throughput and PER. In this work, our focus is onWBAN monitoring applications for Class 0 data rates. According to the relevant literature,PER = 0.01 and packet transfer delay of 250 msec meet the QoS requirements [101], whilethroughput is different for each WBAN application. The throughput required for the appli-cations studied in this work are tabulated in Table 2.2. In the next section, we formulatethe lifetime maximization problem.212.2. Concepts2.2.2 Problem FormulationIn this section, we formulate WSN lifetime maximization as a mixed integer linear program-ming (MILP) problem. Further, based on the selected transmit power level and remainingenergy in the sensors, our objective is to derive the data flow distribution, i.e., the matrixconsisting of link likelihood elements, so that WSN lifetime will be maximized. Variousnetwork lifetime definitions have been proposed in the WSN context [102]. In this work,we define network lifetime as the duration until the first sensor dies, as this is most con-sistent with the requirements of WBAN applications. Moreover, as stated in Section 2.1,in contrast to more conventional WSNs where a large number of sensors are sampling thesame feature, in WBAN monitoring applications, each sensor is responsible for observing adifferent parameter, e.g., pH, pulse and respiration [51]. Therefore, failure of any of thesesensors will disrupt performance of the entire network.Formulation of lifetime maximization problem is influenced by two specific featuresof IEEE802.15.4 MAC layer for TDMA-based communication. First, the transmitting nodestays on during the whole allocated time slot, GTS, even after completion of packet transmis-sion except that it starts to only consume the circuitry power Pelec rather than Pelec+Ptx/η.Second, the receiving node stays on during the whole allocated GTS and keeps consumingPr even after completion of packet reception.Now, let us assume a network consisting of N on-body nodes including N − 1 sensornodes and one sink node represented by S = {S1, . . . SN−1} and SN respectively. Ourobjective is to derive link likelihoods in a way that the duration until the first node diesis maximized. Let P(i,j)t denote the transmit power consumption in the i-th node whentransmit power level P(i,j)tx is adopted for communication between i-th and j-th nodes. Lett(i,j)l correspond to communication duration between i-th and j-th nodes during l-th transferround, and E(i,j)tr,l denote the random variable associated with transmit energy consumptionof i-th node when communicating with the j-th node, i.e.,E(i,j)tr,l = P(i,j)t t(i,j)l + I i,jl Pelec(Ts − t(i,j)l ),Ii,j =1 t(i,j)l 6= 0,0 t(i,j)l = 0 ·(2.4)In (2.4), Ts represents the duration of each time slot. Electronic circuit energy Pelec(Ts−t(i,j)l )is only consumed when the l-th time slot is allocated to communication between i-th andj-th nodes. Otherwise t(i,j)l = 0, E(i,j)tr,l = 0 because the i-th node is turned off for energy222.2. Conceptsconservation. The second term in the right hand side of (2.4) is associated with IEEE802.15.4MAC layer characteristics that are explained in the beginning of this section. Similarly,the receive power consumption of the i-th node when listening to k-th node is given byE(k,i)r,l = Ik,il PrTs which implies that the i-th node listens during the whole GTS durationTs in case the slot is allocated to the communication between i-th and k-th nodes.The total transmit energy expended by the i-th node to communicate with the j-thnode over the network lifetime of n transfer rounds is given by E(i,j)tr,Tot =∑nl=1E(i,j)tr,l andis calculated by E(i,j)tr,Tot = (P(i,j)t − Pelec)T (i,j) + ni,jPelecTs, where ni,j is the total numberof transfer rounds, i-th node spends forwarding its aggregated data to j-th node and T (i,j)represents the total time i-th node spends forwarding packets to j-th node. Similarly totalreceive energy consumption in i-th node to receive packets from k-th node is given byEk,ir,Tot = nk,iPrTs, where nk,i denotes the total number of transfer rounds i-th node spendslistening to k-th node. Therefore total energy consumption of i-th node after n transferrounds is calculated byEi,T ot =∑j∈{1,...N}\i[(P(i,j)t − Pelec)T (i,j) + ni,jPelecTs] +∑k∈{1,...N−1}\ink,iPrTs. (2.5)The MILP formulation of the lifetime maximization problem ismaximizeT (i,j),ni,ji∈{1,...N−1}n,subject to Ei,T ot ≤ E(i)init,∑j∈{1,...N}\i[T (i,j) − ni,jh]−NiQi =N∑k=1[T (k,i) − nk,ih],nαi≤∑j∈{1,...N}\ini,j ≤ n,T (i,j) ≤ ni,jTs,(2.6)where the first constraint ensures that all nodes still have energy left after n transfer rounds.In fact (2.6) translates to the duration after which the first node dies. The second constraintis the flow conservation in which Ni is number of transfer rounds during which, i-th nodehas generated data whereas h is a fixed term accounting for duration of the footer andheader that is merged with each data packet and Qi denotes duration of the data i-th sensorgenerates after a specific number of transfer rounds. The third constraint ensures that232.2. Conceptsaggregate number of transfer rounds allocated to a node to forward data does not exceedthe network lifetime. Moreover high data rate sensors generate data at every transfer roundwhereas low data rate sensors generate data periodically after a fixed number of transferrounds. Therefore, for high data rate sensors αi = 1 and∑j∈{1,...N}\ini,j = n since eachsensor has at least its own generated data to transfer in each transfer round. On the otherhand, low data rate sensors may forward data of other sensors even during transfer roundsthey have not generated that of their own. Fourth constraint guarantees that the amountof time assigned to data transmission from i-th to j-th node does not exceed Ts. Due tocombination of discrete and continuous variables, (2.6) is a MILP problem. In Section 2.3,we explain our methodology to solve the lifetime maximization problem derived in (2.6).In the next section, we explain transmit power adjustment algorithm in order to meetQoS requirements in terms of PDR. This in fact yields new P(i,j)t coefficients in (2.5), andresults in a new MILP which is to be solved based on new coefficients. Therefore, next hopsand inter-node communication durations are reassigned every time new transmit power levelsare adopted. The structure of the transmit power update window is illustrated in Figure2.2. In the beginning of each update window, transmit power levels and consequently linklikelihoods are reassigned.Figure 2.2: Transmit power update window: each transmit power update window is made up ofseveral transfer rounds. In each transfer round, one round of data delivery to the sink iscompleted. Each round contains time slots which are allocated to nodes for data transmission. Thestructure of a transfer round is illustrated in Figure 2.1. Every node is allocated at most one timeslot in each transfer round.242.3. Solution of the Lifetime Maximization Problem2.3 Solution of the Lifetime Maximization ProblemIn this section, we explain the procedure to solve the lifetime maximization problem givenin (2.6). As explained in Section 2.2.1, in WBAN monitoring applications, PER ≈ 1% is re-quired to meet QoS requirements. Therefore, transmit power levels in (2.5) and consequentlythe lifetime maximization problem in (2.6) must be adjusted so that the requirements interms of PDR are met.2.3.1 Transmit Power Adjustment AlgorithmSeveral works have discussed power management techniques in WBANs [52, 53] based onadapting the level of transmission power to the variable nature of the channel caused byshadowing and node movements by exploiting real-time link assessment. However, the fastand abrupt nature of fitness activities make the real time link assessment overwhelming interms of communication overhead. In order to avoid the communication overhead involvedin real-time link assessment and transmit power control, we suggest to update the requiredtransmit power levels only when major variations over EWMA of RSSI samples over limb-torso links are observed. Further, as will be explained in Section 2.3.3, our measurementsshow that this feature is a suitable measure for action or posture variation in WBANs.The purpose from power management is to assign required transmit power level P(i,j)tx,l+1 forcommunication between i-th and j-th sensor nodes during the upcoming, (l+1)-th, updatewindow, Wl+1, so that specific PER requirements are met. Once the required transmitpower levels are updated, the traffic flow distribution matrix is renewed based on (2.6).Each update window consists of multiple transfer rounds. During each round, one set ofdata is delivered to the sink. Accordingly, the proposed transmit power control algorithm iscomposed of two entities: action variation recognition and transmit power selection.Action Variation Recognition: The goal of this entity is to determine whether transmitpower levels need to be updated, and new update window to start thereof. As stated inprevious sections and as will be seen in Section 2.4, our measurements show that EWMA ofpath loss variation over limb-torso links during change of actions is remarkably larger thanthat of limb-limb or torso-torso links. Further, we introduce the EWMA for tracking RSSIlarge fluctuations that result from action variations so that the transmit power levels wouldbe reassigned. Let r(i,j)l,m and r(i,j)l,m−1 denote EWMA of RSSI at the j-th node in the m-thand (m − 1)-th transfer rounds, respectively, when i-th node is transmitting, while rss(i,j)l,m252.3. Solution of the Lifetime Maximization Problemdenotes the observed RSSI value during m-th transfer round and l-th update window; andα is a real weighting factor between 0 and 1. The EWMA update of RSSI is represented byr(i,j)l,m = (1− α).r(i,j)l,m−1 + α.rss(i,j)l,m . (2.7)The purpose of this procedure is to end the window Wl and reassign transmit power levelswhen EWMA function drops or spikes more than a predetermined threshold, e.g., 5 dB.Note that smaller α causes more delay in recognition of variations while less importanceis given to spontaneous path loss variations which happen very frequently even for fixedactions and postures. Therefore, a small weighting factor amount, e.g., α = 0.05, allows usto ignore posture variations of short duration. Moreover, as stated in Section 2.1, our focusis to capture the stationary actions which continue for a large amount of time compared totransfer round size duration. The performance of this action variation recognition strategyon real collected data will be described in Section 2.4.Transmit Power Level Selection Strategy: Once change of actions or postures isrecognized, the transmit power levels required to support communication over each linkneeds to be updated. Furthermore, transmit power levels P(i,j)tx,l+1 corresponding to the (l+1)-th update window are selected based on path loss instances experienced over the precedinglink assessment window W(test)l which is conducted at the end of the current update windowWl. The transmit power is selected so that the average probability of a packet drop basedon path loss values observed over this link assessment window is below a specific threshold,hence PDR remains above the threshold PDRth allowed by QoS requirements, e.g., PDRth=99%. The implementation considerations of this phase is explained in Section 2.3.3 andAlgorithm 1.Let link assessment window W(test)l contain w(test)l RSSI samples, and P(i,j)tx,l+1 denotethe assigned transmit power for communication between i-th and j-th nodes over Wl+1which remains fixed over the entire upcoming window. Let pl(i,j)l,n denote the n-th path losssample in W(test)l . Based on Figure 2.3, assuming that L(r) denotes packet loss probabilitywhen RSSI = r, we select P(i,j)tx,l+1 so thatP(i,j)tx,l+1 = argminPtx 1w(test)lw(test)l∑n=1L(Ptx − pl(i,j)l,n ) < 1− PDRth,pl(i,j)l,n = P(i,j)tx,l − rss(i,j)l,n .(2.8)262.3. Solution of the Lifetime Maximization ProblemIn (2.8), rss(i,j)l,n represents the n-th RSSI sample in l-th link assessment window W(test)l .Note that in (2.8), the transmit power Ptx is selected so that mean packet loss would haveremained below the threshold over the past test window in case Ptx was selected.Figure 2.3 presents the measurements and shows PDR as a function of RSSI for micaZCC2420 motes. The experiment involved more than 40,000 packets, 44 bytes long each,sent from the different pairs of sensors illustrated in Figure 2.4 with 8 transmit power levelsbetween -25 dBm and 0 dBm. The results are consistent with [103] which reports PDR=85% for RSSI=-87 dBm.−90 −85 −80 −75 −70 −65 −60 −550.40.60.81Packet delivery ratio with respect to RSSIRSSI [dBm]Packet delivery ratio (%)Figure 2.3: PDR with respect to RSSI [dBm]; PER=1% is achieved for RSSI=-78 dBm with userdoing different actions and transmit power level taking 8 different levels between -25 dBm and0 dBm2.3.2 LP RelaxationAs explained in Section 2.2.2, because MILP problems are NP-complete, we apply LP re-laxation in order to cause the discrete variables nij adopt real values. Afterwards, derivedtransfer round values nij are rounded to make the problem P-complete and therefore solv-able in polynomial time. Let Mopt and Mreal represent the solution to MILP and relaxedLP problem respectively. In an integer LP maximization problem, the integrality gap withminimum value of 1, is a measure of the efficiency of the LP approximation and is definedas the ratio between the optimum and the relaxed derived maximum values, IG = MrealMopt.Considering that the rounding algorithm uses solution of the relaxation to achieve Mround,the MrealMroundratio, upper bounds the IG. The relationship between Mreal, Mopt and Mround272.3. Solution of the Lifetime Maximization ProblemPulseBlood flowRespirationECGTemperatureGlucoseSink1234567Figure 2.4: On-body sensor placement; 1st, 2nd, 3rd and 4th sensors must be mounted at specificlocations. The 5th and 6th sensors are not restricted and have been placed close to the sink forrelaying purposesis depicted in Figure 2.5. In Section 2.4, we apply LP relaxation to (2.6) so that discretevariables are allowed to take on real values. The optimal value of this LP relaxation yieldsan upper bound to the optimal value of the MILP model. We will see that suboptimalMILP solution that results from rounding the variables in LP relaxation is fairly close tothis achieved upper bound, therefore close to MILP optimal solution.Figure 2.5: The relationship between integrality gap (IG), Mopt, Mround and Mreal is illustrated.MrealMroundprovides an upper bound to IG = MrealMopt·282.3. Solution of the Lifetime Maximization Problem2.3.3 Implementation Considerations and Routing AlgorithmAs explained in Section 2.3.1, each transmit power update window consists of two phases;the transmit power selection and data transmission. Here, we explain the mechanism of eachphase.Transmit Power SelectionAs described in Section 2.3.1, when a transmit power update window starts, the nodesattempt to update the required transmit power level for a reliable communication with othernodes in the WBAN. Since link assessment starts in the beginning of each update window,sink broadcasts a beacon and allocates GTS to nodes for transmission and reception of testpackets. Each recipient node adds the RSSI of the received packet to the array which isdesignated for link assessment over the link between the two corresponding nodes. Thehidden terminal problem is not an issue because all nodes hear each other at maximumtransmit power level. Due to energy efficiency and latency considerations, a set of nodesdenoted by St, engage in transmission of link assessment packets. We pursue this approachbecause: 1) channel symmetry in terms of required transmit power over a specific link whichis different from symmetry in terms of RSSI. Moreover, considering transmit power updatein (2.8) channel symmetry of our interest translates to P(i,j)tx,l+1 = P(j,i)tx,l+1 and 2) requiredtransmit power to meet PER requirements between pairs of nodes whose distance and line-of-sight (LOS) degree are fixed with respect to each other, is not sensitive to the type ofactivity. For example, minimum transmit power level, -25 dBm, always suffices to meetPER=1% over links between 1st-2nd, 4th-5th, 4th-6th, and other similar pairs in Figure2.4.The procedure continues for a predetermined duration before nodes stop broadcastinglink assessment packets to each other. At this point, nodes broadcast packets consisting ofRSSI arrays so that they are collected by the sink. The sink calculates transmit power levelsbased on (2.8) and consequently derives the traffic flow distribution matrix M(l)dist accordingto the solution to (2.6). Based on ni,j values derived in l-th update window, the sink makesa traffic flow distribution matrix M(l)dist whose elements mij represent the probability thatthe i-th node is assigned as next hop to the j-th node,∑i∈{1,...N}\jmij = 1. Consequently,in the beginning of every transfer round, along with the beacon packet which is broadcastfor synchronization purposes, the next hop for every sensor is randomly selected based onM(l)dist and is transmitted along with the beacon. The distribution matrix is used until the292.3. Solution of the Lifetime Maximization Problemnext update window starts, transmit power levels are updated and the new flow distributionmatrix M(l+1)dist is derived.The sink thereafter broadcasts calculated transmit power levels which are used by nodesover the data transmission phase of the update window. During the transmit power selectionperiod, nodes still transmit their main data packets in allocated GTS slots. However, thisis done in single-hop manner because maximum transmit power level, Ptx=0 dBm, sufficesfor PDR=99% for all the nodes considered in this study, whereas data end-to-end transferdelay is 250 msec.Data TransmissionThis phase starts once the sink calculates the transmit power levels and the correspondinglifetime maximizing link likelihoods. At this stage, beacons broadcast by the sink in thebeginning of each beacon interval (transfer round) are used for synchronization purpose andrandom assignment of the next hops to each sensor based on likelihood elements mij inM(l)dist. Pseudocode of the proposed algorithm is presented in Algorithm 1.2.3.4 Measurement Campaign and Simulation SetupIn this section, we first summarize the essential aspects of our data collection tool andmeasurement campaign to collect path loss samples over on-body links for specific activities,i.e., running, jumping jack, lateral pull downs and rowing. The collected data is used tosimulate different components of the proposed algorithm. Further, the action recognitionvariation explained in Section 2.3.1 in addition to power adjustment which results fromFigure 2.3 and our discussion in Section 2.3.1, are simulated based on real collected data.Afterwards we proceed with simulation setup and scenarios that are going to be simulatedin Section 2.4.micaZ Motes: One of the very commonly used transceivers for IEEE802.15.4 WBANmonitoring applications is the micaZ mote developed by Crossbow Technology. The motecontains two major sources of power consumption, the CC2420 transceiver and the MSP430CPU. The amount of current drawn in different radio modes is given in Table 2.1 [104]. Inthe next part, we explain the measurement campaign which underlies the evaluation of ourproposed algorithm.302.3. Solution of the Lifetime Maximization ProblemAlgorithm 1 Pseudocode of the proposed probabilistic link-state routing protocolBI=250 msec, SD=50 msecPhase 1: Transmit power selection;• link assessmentPacket length=17 bytes, Ptx=0 dBmFor each GTS, sink chooses a transmitter from St, whereas nodes S \ St listen∀Si ∈ St, t ≤ Tphase1– Nodes Si broadcasts link assessment packets in the allocated GTS– ∀Sj ∈ S \ St, Sj adds RSSIij to the corresponding RSSI array• power selection– ∀Si ∈ S \ St, Si forwards RSSI arrays to the sink– Sink applies (2.8), calculates vector P(i,j)tx,l ∀j ≤ N, j 6= iPhase 2: Data communication;packet length=85 bytes, Transmit power levels P(i,j)tx,lAfter LP relaxation, sink solves the MILP in (2.6) and derives M(l)dist.Based on link likelihood elements mij inM(l)dist, sink assigns next hops and allocates timeslots for the upcoming transfer roundCommunication startsRSSI EWMA is monitored over limb-torso links1. If∣∣∣r(i,j)l,m − r(i,j)l,m−1∣∣∣ > 5 dB go back to Phase 12. else go back to line 2 in Phase 2Measurement Campaign: Here, we describe the measurement campaign used to char-acterize the path loss between different pairs of nodes during different actions. The mea-surement campaign has two goals;1. Derive path loss samples between pairs of nodes in Figure 2.4 during doing five actionsand postures of study; jumping jack, running, lateral pulldowns, sit-ups and stand-ing still. These samples will be used to simulate the routing algorithm explained inSection 2.2.2.2. Derive PDR for different RSSI levels as illustrated in Figure 2.3. This function helps312.3. Solution of the Lifetime Maximization ProblemTable 2.1: micaZ Radio+CPU power consumptionTransceiver mode Drawn current (Radio+CPU) Drawn current (Radio)RX 22.8 mA 18.8 mATX, Ptx= 0 dBm 21.7 mA 17.4 mATX, Ptx=-1 dBm 20.3 mA 16.5 mATX, Ptx=-3 dBm 19 mA 15.2 mATX, Ptx=-5 dBm 17.3 mA 13.9 mATX, Ptx=-7 dBm 16.3 mA 12.5 mATX, Ptx=-10 dBm 14.9 mA 11.2 mATX, Ptx=-15 dBm 13.6 mA 9.9 mATX, Ptx=-25 dBm 12.1 mA 8.5 mAus carry out the transmit power control strategy in (2.8).As illustrated in Figure 2.6, the study is done for specific activities, including running onthe treadmill, jumping jacks, lateral pulldowns, standing still and sit-ups. At the timeof data collection, the subject who is the second author of this paper, was a 30-year-oldmale with an athletic build, 178 cm height and 78 kg weight. Measurements were done withCC2420 RF modules in a middle size fitness room sparsely filled with fitness equipment. Thelinks between every pair of nodes illustrated in Figure 2.4 in addition to a mote mountedon ankle, were tested with 8 different transmit power level shown in Table 2.1 and for2 minutes allocated to each action. The motes were set to transmit 44 byte packets with27 bytes allocated to payload and 17 bytes to the header as in [105]. The test repeats foreach link, with transmit power levels taking turn in a round-robin manner, and RSSI valuesbeing recorded at a maximum frequency of 200 sample/sec with PER values calculated fromthe logged data.Sensor Placement and Simulation Setup: Despite conventional WSNs, in WBANmonitoring applications most sensors are constrained to be mounted on specific humanbody points because some vital features need to be collected from certain points at torso orlimbs. In this study, we consider six sensors; ECG, pulse, respiration, glucose, blood flowand temperature which are frequently used in WBAN monitoring applications. As explainedearler, apart from temperature and glucose, other four sensors are placed on certain pointsas illustrated and tabulated in Figure 2.4 and Table 2.2 respectively. Lack of placementconstraint for temperature and glucose sensors and the fact that their required sampling rateis well below other sensors help us utilize them as intermediate relays to increase lifetime,322.3. Solution of the Lifetime Maximization Problemas seen in Figure 2.4.The sink is a ZigBee Coordinator (ZC) whereas every other node is a ZigBee Router(ZR), i.e, is capable of aggregating and relaying data of other sensors. The energy consumedfor computation, sensing, generating and aggregating data is not significant compared tothe energy consumed by receiver and transmitter radio circuits [106]. For every specificfitness activity, the i-th sensor node adopts a fixed transmit power level, P(i,j)tx,l , through theprocedure explained in Section 2.2.2 to communicate with the j-th sensor node which isthe power required to achieve PER < 1%. In order to accommodate latency requirements,the beacon interval is chosen to be 250 msec which is the duration taken by the sensors tocomplete one round of data delivery to the sink. In the next section, we explain the resultsregarding on-body link path loss studies from our measurement campaigns and proceed withnumerical study of Algorithm 1 in addition to comparison with existing routing algorithms.Figure 2.6: Mobility model for simulations; Markov graph of transition probabilities betweenactions is illustrated. Higher p values translate to shorter duration for a specific action. The casep = 0.004 which translates to average duration of 1 minute for each action is considered as arealistic case for patient or fitness monitoring applications332.4. ResultsTable 2.2: Monitoring wireless body area networkSensor number Sensor type Placement Sampling rate (per second)1 Pulse palm 12 Blood flow middle arm 203 Respiration neck 804 3-lead ECG chest 2005 Temperature upper torso 0.16 Glucose lower torso 0.012.4 ResultsIn this section, we begin by studying the link behaviours observed during our measure-ment campaign and proceed to evaluate a case of monitoring application introduced inSection 2.3.4 where sensors with different sampling rates are mounted on the upper humanbody; a WBAN consisting of pulse, blood flow, respiration, ECG, temperature and glucosesensors is shown in Table 2.2. For the sake of simplicity and without lack of generality,we assume that only one ECG lead is being used, even though we can generalize it to the3-lead case given that packet size will change accordingly to accommodate the correspondingdata. As stated in the action variation recognition strategy in Section 2.3 and depicted inFigures 2.7 and 2.8, limb-torso links are a suitable indicator in order to tell action variationsand trigger transmit power selection phase.In order to illustrate this phenomenon, two links during a variety of actions with fixedpower level Ptx = 0 dBm are depicted in Figure 2.7. As seen in Figure 2.7b, specific changeof actions may impose remarkable path loss variations over limb-torso links. In Figure 2.8,larger variations of path loss over limb-torso links during the course of one action, i.e.,Figure 2.8a, and also larger path loss difference among multiple actions over these links, i.e.,Figure 2.8b are illustrated.As shown in Figure 2.9, the minimum transmit power level, Ptx=-25 dBm, suffices toachieve PER ≈ 1% for limb-limb or torso-torso links that exist in Figure 2.4. However, theseplots are not shown since they lie on the zero PDR level. In contrast to these links, muchhigher transmit power levels are needed for limb-torso, e.g., links from 1st and 2nd sensornodes to the sink in Figure 2.4. Moreover, actions and body movements result in increasedshadowing over limb-torso links and demand higher fixed transmit power level in order tomeet QoS requirements.In Section 2.3.2, we described the LP relaxation applied to the MILP problem expressed342.4. Results200 400 600 800 1000 1200−60−55−50−45−40Time [S]RSSI [dBm]RSSI behaviour over waist−chest link during doing different actionsSit−ups Jumping jackLateral pulldowns Running(a) waist-chest200 400 600 800 1000 1200 1400 1600−80−70−60−50−40Time [S]RSSI [dBm]RSSI behaviour over waist−wrist link during different actionsLateral pulldowns Sit−upsRunning Jumping jack(b) waist-wristFigure 2.7: RSSI behaviour over waist-chest link on the subject person during four actions oflateral pulldowns, running, sit-ups and jumping jack with Ptx = 0 dBm is shown in (a), whilewaist-wrist link for the same round of actions is illustrated in (b). Black function shows theEWMA with α = 0.05 over RSSI behaviour; As could be seen, RSSI over limb-torso link is a betterindicator of action variations.10 20 30 40 50 60 70 80 90 100 110−90−80−70−60−50−40RSSI [dBm]Time [s]RSSI comparison between different links during walking chest−abdominalswrist−abdominalswrist−elbow(a) RSSI comparison for different links duringrunning10 20 30 40 50 60 70 80 90 100 110−90−80−70−60−50−40Time [s]RSSI [dBm]RSSI comparison between different links for running and jumping jack waist−chest, runningwaist−wrist, runningwaist−chest, jumping jackwaist−wrist, jumping jack(b) RSSI comparison for different actions and linksFigure 2.8: RSSI behaviour on limb-limb, torso-torso or limb-torso links for Ptx = 0 dBm areshown during walking in (a) and during jumping jacks in (b). When action changes, most RSSIvariations occur on limb-torso links rather than torso-torso or limb-limb links.in (2.6) and also introduced the parameter IG. In Figure 2.10, we show that applying therelaxation even when the energy remaining in the sensors is small, e.g., 1 J, yields an accept-able approximation error, i.e., around 1%. For this scenario, the activity type is randomly352.4. Results−25 −20 −15 −10 −5 000.10.20.30.40.50.60.7Transmit power level [dBm]Packet Drop Ratio jumping jack, waist−anklejumping jack, waist−wristwalking, waist−anklewalking, waist−wristlateral pulldowns, waist−anklelateral pulldowns, waist−wristFigure 2.9: PER with respect to transmit power level for different on-body links and fitnessactivities; Higher transmit power level is required to achieve the desired PDR on limb-torso linkscompared to torso-torso or limb-limb linkschosen every 60 seconds out of five activities of interest. Even for small energy remaining inthe sensors, nij values are either 0 or fairly large, of the order of 103, hence relaxation androunding do not sacrifice any remarkable accuracy. As defined in Section 2.2.2, the trafficflow distribution matrix M(l)dist gives the ratio of transfer rounds in the update window, thateach node must spend communicating with other nodes so that network lifetime becomesmaximized. In order for energy depletion to be totally balanced, size of update window Wlshould be large enough compared to transfer round size so that probabilistic selection ofnext hops based on M(l)dist result in next hop ratios which actually comply with elements mijin M(l)dist. Moreover, the ideal case is for the whole network lifetime to consist of only oneupdate window so that the nij values derived in (2.6) are deterministically applied.In Figure 2.11, the communication overhead of transmit power selection phase, PERand energy depletion in sensors with respect to action transition probability p for the pro-362.4. Results0 5 10 15 20 25 301.021.041.061.081.1Remaining energy in the sensors [Joules]Integrality GapIntegrality gap of the linear programming relaxation Figure 2.10: IG with respect to remaining energy in the sensors; It can be seen that applyingrelaxation to (2.6) results in approximation error below 1% even for relatively small values ofremaining energy, ≈ 1 Jposed routing protocol are illustrated. We define communication overhead as the ratiobetween energy consumed in Phase 1 of the routing protocol proposed in Algorithm 1 andtotal energy consumption in the network. As a more realistic WBAN scenario, we assumethe case p = 0.004 for the mobility model shown in Figure 2.6 which translates to aver-age duration of 1 minute for each action. Figure 2.11b shows balanced energy depletion ofsensors under this condition.In Table 2.3, link-state and cluster-based WBANs are benchmarked in terms of relativeadvantages and drawbacks. In Dijkstra-based routing algorithm [53], remarkable additionalreception energy consumption is expended in nodes since each node listens to beacon packetstransmitted by all other nodes in the beginning of a transfer round. However, in terms ofconnectivity, the algorithm is powerful due to its frequent link assessments. In PRPLC [49],transmit power is fixed and next hop is chosen based on its probabilistic connectivity to the372.4. Results0.01 0.02 0.03 0.0400.10.20.30.40.50.60.7Action transition probability (p)Ratiorouting behaviour with respect to action transition probability Phase1 overheadPER(a)500 1000 1500 200000.20.40.60.81Running time [s]Energy [J]Energy depletion in sensors 1st node2nd node3rd node4th node5th node6th node(b)Figure 2.11: Performance of the proposed link-state routing protocol; (a) shows communicationoverhead and PER with respect to action transition probability. The larger frequency in actionvariations translates to less energy efficiency of the proposed protocol. Balanced energy depletionin sensors is depicted in (b).Table 2.3: Benchmark of different link-state and cluster-based routing protocols in terms ofnetworking metricsRoutingprotocolPRPLC Dijkstra-based HIT Probabilistic link-statePros1-very good connectivity2-useful for ultra-shortrange transceivers anddelay tolerant applications1-very goodconnectivity, delay2-very goodlifetime forhigh datarate applicationsgood lifetime for linenetworks on a single limbor torso and immobile scenarios wherelog-distance path loss model applies1-Very goodnetwork lifetime2-Acceptableconnectivity forcontinuous actions3- Very lowcontrol messageoverheadCons1-high control message overhead,2-high delay andpoor lifetime1-large controlmessage overheadfor low data rateapplications2-poor lifetimefor low datarate applications1-Low network lifetimefor mobile scenarios1-poor connectivityfor short actions andpostures,2-high controlmessage overheadfor short actionssink. Even though PRPLC beats our algorithm in terms of connectivity, balanced energyconsumption is not achieved. Further, PRPLC is best suited to intermittently connectedWSNs which are either made up of ultra-short range transceivers or work based on minimumtransmit power level on CC2420 transceivers and for applications with high delay tolerance.382.4. ResultsComparison with Cluster-based Routing Protocols: LEACH [54] and PEGASIS [55]are the two most popular cluster-based WSN routing protocols. Further, LEACH andPEGASIS work based on forming clusters and chains of nodes respectively and having acluster head (CH) aggregate the data and forward it to the BS. Intra-cluster and intra-chain communication in LEACH and PEGASIS are performed in multi hop and directmanner respectively. These protocols have inspired more energy efficient extensions suchas Energy-LEACH (E-LEACH), Multihop-LEACH (M-LEACH) [107], and techniques likeAnybody [42], Hybrid Indirect Transmission (HIT) [43] that are specifically devised forWBANs. HIT is a combination of LEACH and PEGASIS in the sense that in every cluster,packets are forwarded to the CH in a multi hop manner and the aggregated data will betransmitted to the BS afterwards [43].Table 2.4: Lifetime comparison between the proposed probabilistic routing protocol andcluster-based algorithms with 100 J energy available for each sensor❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤❤ActionDifferent techniquesHIT E-LEACH Single hop proposed probabilistic routingWalking 28h 40h 57h 65hJumping Jack 29h 41h 57h 69hRowing 29h 40h 57h 71hLateral Pulldowns 29h 40h 57h 71h(a) Spanning tree with threelevels(b) Spanning tree with twolevels (c) Spanning tree with one levelFigure 2.12: Simulating the algorithm for running activity; LP results in 12 spanning trees withone, two and three levels; some of which are illustrated. Solid lines are fixed in every graphwhereas dotted lines show the alternatives each node could forward the data to.In both HIT and E-LEACH, a gateway is designated at each transfer round to aggregatedata from all other sensors and forward them to the sink. Further, in E-LEACH and HITimplementations, the portion of transfer rounds each node takes up as gateway is chosenso that network lifetime is maximized with the constraint being put on the structure of thespanning trees which are assigned. As can be seen from the position of non-zero elements39(a) E-LEACH spanning tree (b) HIT spanning treeFigure 2.13: General spanning tree topologies resulted from HIT and E-LEACH techniques;E-LEACH yields two level trees whereas HIT which is inspired by PEGASIS yields 4 level trees. Inboth cases one gateway is responsible for data aggregation and forwarding it to the sink whereasnodes become gateway in a round-robin mannerM(walking)dist =0 0 0.23 0 0 00 0 0.18 0 0 00 0 0 0.07 0 00 0 0 0.25 0 00 0 0 0.35 0 01 1 0.59 0.32 1 1M(jumping jack)dist =0 0 0.18 0 0 00 0 0.13 0 0 00 0 0 0.03 0 00 0 0 0.25 0 00 0 0 0.29 0 01 1 0.69 0.43 1 1M(rowing)dist =0 0 0.18 0 0 00 0 0.13 0 0 00 0 0 0.03 0 00 0 0 0.25 0 00 0 0 0.29 0 01 1 0.69 0.43 1 1M(lateral pulldowns)dist =0 0 0.18 0 0 00 0 0.13 0 0 00 0 0 0.03 0 00 0 0 0.25 0 00 0 0 0.29 0 01 1 0.69 0.43 1 1(2.9)in (2.9), the distribution matrices that result from applying our proposed algorithm to402.4. Resultsdifferent actions are very similar. Furthermore, for the four shown actions, in every assignedtree, 1st, 2nd, 5-th and 6-th nodes directly communicate with the sink whereas 3rd and4-th nodes have other alternatives as well. Distribution matrices derived in (2.9) translateinto 12 spanning tree graphs some of which are illustrated in Figure 2.12. As observed inderived matrices in (2.9), the highest probability is assigned to the 1-level graph thereforethe mean hop count a packet takes to reach the sink is close to one whereas energy depletionis balanced as illustrated in Figure 2.11b.On the other hand, general spanning tree structure of HIT and E-LEACH is illustratedin Figure 2.13. As can be seen in E-LEACH all spanning trees are two level with nodes takingturn to adopt gateway role (3rd node is the gateway in Figure 2.13) whereas in HIT, treescould have different number of levels based on the node which has been assigned as gateway,e.g., 6-th node being assigned as gateway results in a 6-level tree. Therefore, due to thegeneral structure of the spanning trees defined for these techniques, the mean hop countis higher than that of single hop communication and the proposed probabilistic routingalgorithm.As stated in Table 2.3, even though HIT yields suitable lifetime for log-distance pathloss model where transmission to the closest neighbour saves energy, it is not necessarily anenergy-efficient option for mobile scenarios and transceivers with high reception power. Notethat even though balanced energy depletion is achieved in these techniques, mean hop countthat each packet takes in order to reach the sink is high and lifetime is far from maximum aswell. In Table 2.4, our proposed algorithm is compared to classic and popular cluster-basedrouting protocols in terms of network lifetime. Since our proposed transmit power control canbe used in complementary with these cluster-based protocols, in order for the comparisonto be fair and only be focused on the impact of routing and assigned routing spanningtrees, we have applied the same transmit power control strategy to E-LEACH and HIT.The reason these protocols perform worse than single-hop communication is the structureof their assigned routing spanning tree which does not allow direct transmission which is asuitable communication form due to relatively high reception energy of CC2420 transceivers.In Figure 2.14, applicability range of the proposed routing algorithm is shown. As can beseen the number of sensors is limited by characteristics of TDMA-based IEEE802.15.4 MAClayer. The step function is the result of fixed maximum number of guaranteed time slots ina IEEE802.15.4 superframe illustrated in Figure 2.1. Further for a larger number of sensors,one should consider using contention-based portion of the superframe as well.412.5. DiscussionFigure 2.14: Approximate applicability range of the proposed routing algorithm; Shaded regionshows the aggregate sampling rate (bandwidth) achievable for different number of sensors2.5 DiscussionIn this chapter, we have proposed a link-state routing protocol that uses LP techniquesand transmit power adjustment to maximize WBAN lifetime. The algorithm is best suitedto maximizing WBAN lifetime, and addresses connectivity in monitoring applications andmobility models which involve stationary postures associated with routine daily activities.In our proposed algorithm, we overcome communication overhead imposed by real time linkassessment, calculation complexity caused by routing table calculation, and address lifetimemaximization by: 1) monitoring RSSI in a dynamic and distributed manner on data packetscommunicated over links, therefore performing link assessment and changing the transmitpower levels only when sharp fluctuations in EWMA of RSSI is observed, 2) only accountingfor limb-torso links in the link assessment process because RSSI variations over limb-limb ortorso-torso links are not remarkable in terms of the required transmit power level, 3) usingLP to derive link likelihoods.The proposed routing protocol is suboptimal for two reasons; 1) the limited durationof each action which results in the algorithm not fulfilling the exact derived link likelihoodssince the number of transfer rounds within an update window is limited, 2) LP relaxation;the lifetime maximization problem is in fact a MILP. In the work proposed here, specific422.5. Discussioncharacteristics of IEEE802.15.4 MAC are taken into account to derive LP formulation ofthe lifetime maximization. Accordingly, this work applies to WBANs which are built uponIEEE802.15.4 MAC layer. As a future practice, deriving lifetime maximization LP forother standards, e.g., IEEE802.15.6 would be very useful. Moreover, IEEE802.15.6 mostlysupports one and two hop star networks, therefore new design constraints are needed. Notethat due to the limitations of TDMA-based IEEE802.15.4 MAC which mandates that alltime slots have equal durations, the proposed algorithm may not be efficient in terms ofbandwidth utilization. Therefore, design of MAC protocols with dynamic time slot durationand variable time slots throughout a transfer round would help to ensure more efficientutilization of bandwidth should larger number of sensors are deployed.43Chapter 3Periodic Connectivity in Body AreaNetworks and Its Implications forScheduling3.1 IntroductionIn this chapter, we propose an energy efficient scheduling algorithm for a particular class ofactions so-called periodic actions and a specific class of applications which are delay toler-ant. That is: 1) Firstly, we show that a group of actions (particularly fitness) are periodicin the sense that some links (extremity-torso) show periodic and predictable connectivitybehaviour, 2) Secondly, we propose a scheduling technique along with transmit power ad-justment to take advantage of predictability over these links for lower energy consumption.Moreover, the periodicity of on-body links is employed to predict the future behaviours oflinks so that energy-efficient communications between on-body nodes is established, therebynetwork lifetime is elongated. This scheduling technique can be used in complementary withWBAN routing protocols such as the proposed work in Chapter 2. Moreover the periodicityenables single-hop communication with sink at low transmit power, hence saves remarkableenergy.WBANs, as also defined in Chapter 1, are a subclass of WSNs which consist of a set ofsensing nodes worn on the human body or implanted into the tissues. After the observationsare made by the sensing nodes, they are sent to a centralized data monitoring and processingcentre, i.e., an off-body base station or an on-body sink node usually mounted on the leftwaist, by means of wireless communications so that relevant decisions are made or data islogged. As mentioned in Chapter 1, in WBANs frequent replacement of the batteries shouldbe avoided as battery replacement particularly for implanted sensors is not an easy taskto accomplish. Therefore, it is necessary to lower the power consumption in the WBAN.Wireless communication is the most energy consuming task performed by the sensor nodes443.1. Introduction[108]. This causes development of energy-aware communication protocols and mechanisms tocontribute the most to elongating batteries lifespan. Improvements in battery longevity canbe achieved with several means among which lowering transmit power level is significantlyimportant.In general, several scheduling techniques have been proposed for WBANs. Store andforward scheduling techniques [56, 57] increase likelihood of a packet reaching its destinationby storing the packet at multiple hops which however heavily increases energy consumption[53]. Transmit power control strategies [52] that work along with some of these techniquesstill result in high overhead due to frequent link assessments associated with transmit poweradjustment. Opportunistic scheduling techniques [58–60] which uses temporal and spatialdiversity of the channel to allocate bandwidth to the user with a more suitable channel statealso suffer from communication overhead. Most of the opportunistic techniques are designedto maximize resource utilization in the network while providing fairness among users. Onlya few of the opportunistic scheduling studies consider the power constraints in the design oftheir algorithms [80, 81]. In these studies, the transmission power is adjusted to the conditionof the underlying fading channel for achieving a desirable data rate. However, the continuouslink assessment make these techniques incompatible with WBANs where nodes ideally turntheir radio off as an energy-saving measure until it is their turn to transmit. Anotherclass of WBAN scheduling techniques focus on adaptive or optimized GTS allocation inIEEE802.15.4 WBANs in order to meet latency and fairness requirements or to make bestuse of bandwidth [61, 62, 109]. The idea in power management techniques [56, 98, 105, 110]is to exploit real-time link assessment in order to adapt the level of transmission power tothe variable nature of the channel caused by shadowing. In real time link assessment thetransmission power level is adapted to the current condition of the links. All these studiesonly focus on the cases with fixed or very slow moving nodes. However, in most dailyactivities WBAN is a highly dynamic network and the on-body links are highly dynamic,thereby the aforementioned acknowledgement-based schemes yield significant power controltraffic which is not power efficient.Furthermore, in most of these works, emphasis is on latency and bandwidth require-ments rather than to increase energy efficiency. One of the intrinsic characteristics ofWBANs that the aforementioned studies do not take advantage of is periodicity of mostprolonged body actions. Lots of daily routine activities, e.g., walking, running and fitnessactivities involve periodic body movements which result in periodic connectivity of somelinks as a result of severe shadowing caused by limbs obstructions or internode distance453.2. Conceptsvariation. We believe that the periodic nature of the actions can be exploited in the de-sign of scheduling techniques as an effective approach towards power efficiency in WBANs.For applications with looser deployment requirements, i.e., in terms of latency, priority andnode placement, action recognition along with predictability of connectivity over specificlimb-torso links during periodic actions are exploited to propose a scheduling algorithmalong with transmit power adjustment in order to achieve high energy efficiency.In this chapter we propose a novel action-based scheduling technique in order to reduceenergy expenditure. Further, we show that direct, i.e., single hop, transmission with lowtransmit power level is possible over many links which suffer from a high degree of shadowing,in case we make use of predictable behaviour of these links during specific actions. In theproposed algorithm, RSSI levels of on-body links are measured in a real time manner andare subsequently used by the naive Bayes algorithm for action recognition. Once the actionis recognized, given that periodic behaviour of specific links is known to sink, GTS allocationis carried out so that single hop transmission over periodic links with low transmit powerlevels becomes possible. To the best of our knowledge, this is the first time that a schedulingtechnique exploits the periodic behaviour of on-body links for packet transmission.The remainder of this chapter is as follows: in Section 3.2 we explain concepts suchas connectivity, periodic and non-periodic links, action recognition and also energy con-sumption lower bound, i.e., given that complete global knowledge about future behaviour ofpath loss is available. The lower bound provides us with a benchmark to assess our proposedtechnique. In Section 3.3, we explain mechanism of our RSSI-based action recognition tech-nique which does not need any IMU sensor in addition to our scheduling technique. Finallywe do the performance evaluation and explain the results in Section 3.4, and wrap up thechapter with conclusion in Section 3.5.3.2 ConceptsIn this section, we define some key concepts and terminologies in addition to nature of thescheduling problem that will be used in the rest of the chapter. Note that system model interms of radio model and MAC layer characteristics is the same as Section 2.2.1 discussedin Chapter 2. However in terms of data delivery model, the technique discussed in thischapter is mostly suited to query-driven applications or continuous application with largedelay tolerance. Further, as discussed in Section 3.1, the proposed technique is well-suited todelay tolerant applications where periodic links wait for their allocated GTS to arrive during463.2. Conceptstheir good channel state behaviour. In the following, we first explain periodic actions, and goon to define connectivity, periodicity and classification of links into periodic and non-periodictypes.3.2.1 Periodic ActionsPeriodic actions have been recognized in the literature for a long time [111, 112]. In factclassification of actions into periodic and non-periodic has been done in [111], while theperiodicity attribute has been used for action recognition in both works. Activities such aswalking, running, swimming, sit ups and many more daily activities particularly in fitnesscontext which follow a repetitive pattern in motion are known as periodic actions. Eventhough periodicity has been used for action recognition, using this important characteristicto achieve energy efficiency in WBANs has widely been ignored.3.2.2 Connectivity, Periodicity and Link ClassificationAssuming that transmit power level is employed in a discrete manner which is the case formost IEEE802.15.4 compliant modules, connectivity function Ckj(t) for k-th link and j-thtransmit power level PTx = Pjtx is defined asCkj(t) ={1 ; PRx > γ,PTx = Pjtx0 ; PRx < γ,PTx = Pjtx, (3.1)where γ is the minimum required received packet power which can be determined so thatthe successful reception of the packet is guaranteed. In our performance analysis, we definethe threshold as γ = −85 dBm because it guarantees high packet delivery ratio and alsolies within the required threshold range derived in [56]. k-th link is periodic when thereexists at least one j that renders the connectivity function Ckj periodic with action periodT, Ckj(t) = Ckj(t+T ). On the other hand non-periodic links follow more random path lossbehaviour. The links studied in Chapter 2 were treated as non-periodic links because weonly took advantage of their stationarity for transmit power adjustment.3.2.3 Scheduling for Periodic ActionsIn IEEE802.15.4 WBAN context, the purpose from scheduling is to allocate time slots tonodes so that applications requirements in terms of latency and bandwidth are met. Asdiscussed in Section 3.2.2, specific links show periodic behaviour during specific actions. This473.2. Conceptsadds extra amount of predictability to stationary actions studied in Chapter 2. Further, inChapter 2 we only took advantage of stationarity of links for transmit power adjustment.However, in this chapter, we show that periodic connectivity of links helps us adopt single-hop communication with low transmit power levels, therefore save more energy. The keyto such a time slot allocation is action recognition so that sink becomes aware of periodiclinks and does the power adjustment accordingly. Moreover, in this work we assume thataction’s period is fixed and once the action is known, the periodic links along with theirconnectivity behaviour are known. This may not be a realistic assumption for real worldscenarios, however it serves as a case study in order to prove the energy efficiency thatcan be achieved over periodic links. In the next section, we explain our action recognitiontechnique.3.2.4 Action RecognitionAction recognition is the first step en route to our WBAN scheduling technique. Severalworks have been previously done on action recognition using on-body sensors [113–115]. Inthese works, IMU sensors are used to capture limbs acceleration and angular velocity intwo directions: inclination angle θ and azimuth angle φ. Features, e.g., mean, standarddeviation, root mean square, first and second derivatives [115] are then extracted from thecollected parameters in different time segments. They are subsequently transmitted to thesink so that the action is decided based on hidden Markov model (HMM). In [113], angularvelocity and acceleration parameters in time windows of certain size are transmitted to a BSwhich uses a set of training motion sequences to classify the actions. The action recognitiontechnique proposed here, is more economical because sensor nodes are not required to beequipped with accelerometers.Our technique is also superior in terms of classification time which means it onlytakes one action period to do action recognition. In most periodic fitness activities, sometorso-limb links are likely to experience periodic connectivity bevahiour, e.g., wrist-waistduring jumping jack or ankle-waist during running. We can use these torso-limb linksto extract features such as path loss mean and standard variation. Assuming that thesefeatures are independent, naive Bayes algorithm is used as the classification tool. Eventhough naive Bayes classification is meant to be working for independent features, it oftenshows a good performance for more complex situations as well [116]. The algorithm islinear in time for both training and testing, therefore has optimal time complexity [117].Even though in our setup we only use two on-body links, i.e., wrist-waist and ankle-waist483.2. Conceptsfor action recognition, it can be easily and intuitively observed that applying more linkshelp us recognize more actions and with better accuracy. Action classification setup will beexplained in Section 3.3.1.3.2.5 Energy Consumption Lower BoundIn this section, we explain how to derive a lower bound on energy consumption of an ar-bitrary network which consists of n links that are going to be provided with time slots forTDMA communications. The lower bound in fact enables us to discover how the suggestedscheduling and power adjustment technique helps us reach closer to the power consumptionlower bound on so called periodic links than over non-periodic links. Moreover the purposefrom this derivation is to observe how close the periodic link behaviour helps us get to thecase where future behaviour of the link is totally known. In order to derive such a lowerbound, the BS is assumed to be aware of channel behaviour on both types of links. Moreoverthere exists a global awareness about channel behaviour of on-body links. Therefore eventhough no real-time channel assessment is conducted, packet failures and retransmission donot occur over the links. Note that even though this is not a realistic assumption in thereal world scenarios, it provides us with a useful benchmark for the comparison conductedin Section 3.4.Let P jki represent the power drawn from the transceiver battery when transmit powerPTx = Pjtx is employed whereas Pjtx is the minimum level required to have a successful packettransmission at i-th time slot over k-th link. Suppose rk is the required data rate for k-thlink and m is the data packet length in bits for each transmitted packet while R denotestransmission bit rate of the standard, e.g., IEEE802.15.4. This demands for nk =rk.Tmtimeslots per action period to be allocated to k-th link, where T is period of the action. We needto allocate time slots and transmit power levels to the nodes so that• only one node is permitted to transmit during a particular time slot,• required data rate over both links is met,• aggregate power consumption of transceivers is minimized.493.3. MethodologyThis translates to the following optimization problem:min(∑i∑kαikPki) subject to∑ni=1 αik > nk ; ∀k = 1, 2αik ∈ {0, 1} ; ∀i = 1, 2 · · · , n,∀k = 1, 2αi1 ∧ αi2 = 0 ; ∀i = 1, 2 · · · , n,(3.2)where αik denotes channel access permission factor for the kth link at i-th time slot. More-over, αik ∈ {0, 1} is a bit which takes on 1 if access at i-th time slot is given to the k-th link,takes on 0 when permission is not granted. In (3.2), Pki is the power drawn from batterywhich is associated with minimum transmit power level that guarantees connectivity on k-thlink at i-th time slot, i.e., condition PRx > −85 dBm is met. Note that transmitter’s powerconsumption with respect to transmit power level, as also described in Section 2.2.1, is anincreasing function [118]. In the third constraint, ∧ operator denotes logical AND. Secondand third constraints force only one packet transmission during a single time slot and pre-vent simultaneous transmission on links as it causes interference. Note that even though in(3.2) we are concerned with energy consumption, time slot duration is not involved becauseit is assumed to be fixed over the whole action period and is one packet long in terms oftransmission duration. It is again worth mentioning that (3.2) denotes aggregate energy con-sumption where single-hop communication is adopted for all nodes. Our measurements helpus determine Pki values. This optimization is a binary integer linear programming which isa NP-hard problem and can be solved with MATLAB for different required data rate vectorsrk. Note that the calculated lower bound is not practically obtainable since transmitter isoblivious to future link behaviour. In the next section, we explain our methodology thatleads to our proposed scheduling algorithm in addition to the measurement campaign andsimulation setups that are going to be numerically studied in Section 3.4.3.3 MethodologyIn this section, we explain practical considerations regarding implementation of our proposedscheduling algorithm. Further, we explain how the action recognition and transmit poweradjustment phases work on a IEEE802.15.4 WBAN.503.3. Methodology3.3.1 Proposed Scheduling TechniqueAs stated in Section 3.2.2, we divide on-body links into two types of periodic and non-periodic. In this section, we exploit our proposed link classification in order to devise ascheduling technique that works without frequent link assessments. The technique worksbased on periodicity and predictability of periodic links introduced in this chapter andstationary behaviour of non-periodic links which were discussed in Chapter 2. Note that,in ideal circumstances in terms of bandwidth utilization for TDMA-based communication,there should be no overlap among connected sessions of periodic links so that maximumnumber of time slots is granted to each node. However, this may not be possible as numberof nodes increases in realistic real world scenarios. In case, we are not looking to takeadvantage of periodic behaviour, the transmit power adjustment proposed in Chapter 2along with scheduling formulation in (3.2) can be used for time slot allocation.This work is a case study and only serves as a proof of concept for energy efficiencythat is achievable over periodic links which suffer high shadowing. Therefore, schedulingfor multiple periodic links to maximize bandwidth utilization remains as a future workand is out of scope of this chapter. In this work, we assume there are only two singlehop links from extremities to sink which is mounted on waist is available. As a schedulingstrategy, we suggest using the connected session of the periodic link with low transmit powerlevels whereas the other part of the action cycle, i.e., during which the periodic link is notavailable, is allocated to the stationary non-periodic link with adopting fairly high transmitpower levels, i.e., with power adjustment strategy proposed in Section 2.3.1.Let δk(j) denote probability of packet reception failure on k-th link when PTx = Pjtx,δk(j) = P (PRx < −85 dBm∣∣PTX = Pjtx), where P (·) denotes probability function. Wesummarize the criteria for choosing index j in P jtx as follows;j : argminj (Pjtx∣∣Ckj(t) = Ckj(t+ T )) ; periodic linkssame as Section 2.3.1 ; non-periodic links· (3.3)We solve (3.3) separately for both links, while the idea is to choose suitable fixed transmitpower levels that can satisfy (3.3). As noted earlier, power adjustment technique expressedin (3.3) has been justified in Sections 3.2, 2.3.1. After any action variation trigger, allocatedtime slots and required transmit power levels will be sent along with the beacon that sinkbroadcasts for synchronization purposes at the end of each transfer round.513.3. MethodologyAction Recognition: As explained in Section 3.2.4, action classification is one of themajor components of our study. Furthermore, we assume that once the action is known,the behaviour of periodic links in terms of connected sessions is known whereas behaviourof non-periodic links in terms of their stationary behaviour is recognized as described inChapter 2. An important issue to be considered in the design of our algorithm is that sink isable to recognize when one action is cut and another has started so that it can reschedule thelinks. Trigger of the action recognition phase is done based on the procedure explained inChapter 2, i.e., Section 2.3. The transceivers mounted on extremities will then be triggeredto stop data transfer whereas sink runs action recognition test again. Sink node sends shorttest packets, i.e., 17 byte long packets which is PHY/MAC header size and the minimumZigBee packet size, to wrist and ankle nodes during a single period of the action that isknown. These nodes read the RSSI levels, extract mean and standard deviation and sendthem back to the sink where naive Bayes algorithm is run to classify the actions. Once theaction is recognized, the time slot allocation is determined based on the scheduling techniquedescribed in Section 3.3.1.Training and Test Set: As discussed in Section 3.2.4, naive Bayes classification methodis used for action recognition in this chapter. As will be explained in the next section,our data set is composed of four actions, 3 minute long each. With action period being1 second, there are 180 mean and standard variation feature points available for each action.We allocate 135 and 45 points per action to training and test sets respective. Gaussianmodel for the training feature set in each class is calculated for mean and standard variationof the observed path loss points. Maximum a posteriori (MAP) decision rule is then appliedto classify the test set. Accuracy of our action recognition technique will be discussed inSection 3.4.3.3.2 Measurement Campaign and Simulation SetupIn order to proceed with numerical study of the proposed action recognition and scheduling,we need to capture path loss behaviour of the studied on-body links. In this work we studyfour periodic fitness actions: jumping jack, running, rowing and lateral pulldowns, with twoon-body links of wrist-waist and ankle-waist. The reason to choose this node placement setupis its diversity in providing suitable features and various combination of periodic links neededfor the proposed action recognition and scheduling technique which will be explained later.Even though we have only studied four actions in this chapter, the same discussion holds for523.4. Resultsother periodic actions as well. Our measurement tool, as also described in Section 2.3.4, ismicaZ CC2420 mote which is widely used in IEEE802.15.4 WSN research studies. The moteis a IEEE802.15.4/ZigBee compliant RF transceiver for low-power wireless applications. Wekeep the action’s period unchanged during the measurements as periodicity plays the majorrole in our proposed scheduling technique. The period of all four actions of interest is alsothe same. The subject person is a 29 year old lean male with 178 cm height and 78 kgweight. For each action of interest, waist transceiver is set to send 17 byte length packetswithin every 5 msec with the maximum power, 0 dBm. The test goes on for three minutesper action with RSSI values being recorded in the extremity transceivers. Note that formicaZ CC2420, received signal power has a linear relationship with RSSI values [118]. InSection 3.4 behaviour of periodic links will be illustrated whereas link classification, i.e.,periodic and non-periodic, will be tabulated.Sensor Placement and Simulation Setup: In terms of simulation setup, the simulatedscenarios are very similar to Chapter 2, i.e., explained in Section 2.3.4. However four actionsof study are running, jumping jack, rowing and lateral pulldowns. Whereas as opposed toChapter 2 where several positions for node placement is considered, in this chapter onlywrist and ankle have been designated for node placement, while waist is still the candidatefor sink’s position. In addition to higher diversity and independence in terms of featuresthat would benefit us for simple action recognition explained in Section 3.3.1, this nodeplacement serves our objective which is to show how periodic links help achieve more energyefficiency compared to non-periodic links. In terms of simulation scenarios for studyingaction classification accuracy and energy efficiency of the scheduling algorithm, the fouractions of interest are randomly chosen and each continue for one minute before the newaction starts. In the next section, behaviour of periodic links, classification of links forthe studied actions, performance of the proposed action recognition technique and energyefficiency of the proposed scheduling technique are illustrated and explained.3.4 ResultsIn this section, we present the results regarding behaviour of periodic links, performance ofaction recognition, and proposed scheduling algorithm in terms of energy efficiency. As ob-served in our measurement campaign, periodic links in four actions of interest, running (RN),jumping jack (JJ), rowing (RW) and lateral pulldowns (LPD) are tabulated in Table 3.1,while behaviour of two periodic links are illustrated in Figures 3.1 and 3.2. In Table 3.1,533.4. Resultswe refer to waist-wrist, and waist-ankle with wrist and ankle links respectively as the waistend is common between them, because sink is usually mounted on waist. As illustrated inFigures 3.1, and 3.2, fairly low transmit power levels result in periodic connectivity sessionsover periodic links during jumping jack and running.Table 3.1: Actions of interest and periodic linksAction RN JJ RW LPDPeriodic link Ankle Wrist Wrist, Ankle Wrist0 0.5 1 1.5 2 2.5 3 3.5 4−115−110−105−100−95−90−85−80−75Time [s]Received power [dBm]Waist−Wrist link during jumping jack Figure 3.1: Received power over waist-wrist link with PTx = −25 dBm; redline shows theconnectivity threshold which occurs when PRx = −85 dBm0 0.5 2 4−110−100−90−80−70Received power [dBm]Time [S]Waist−Ankle link during running Figure 3.2: Received power over waist-ankle link with PTx = −20 dBm; redline shows theconnectivity threshold which occurs when PRx = −85 dBm543.4. Results0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.040.30.40.50.60.70.80.91Normalized classification energy consumptionAccuracy (%)Action recognition accuracy and classification energy consumption Running−Jumping jackRunning−RowingRowing−Lateral pulldownsFigure 3.3: Action recognition accuracy with respect to classification energy to aggregate energyconsumption ratio for r = 1kB/s with two actions done in a rowRunning Lateral pulldowns Jumping jack Rowing05101520Action typeTransmission energy per packet ( µJ )Transmission energy consumption comparison on periodic links Lower boundProposedFigure 3.4: Per packet energy consumption comparison between proposed scheduling and lowerbound on periodic linksIn Section 3.2.4, we described how action recognition in our study works. Classifica-tion energy consumption is an important issue because it increases the aggregate energyconsumption in the network. Classifier accuracy with respect to normalized classificationenergy consumption is depicted in Figure 3.3, while the normalizing constant is aggregateenergy consumption. The simulation scenario is composed of various combinations of twoactions being done in a row for one minute each and with 37 slots/period having been allo-cated to both links when beacon order is 2, i.e., BO=2. Each point in Figure 3.3 correspondsto a specific rate at which RSSI levels are being sampled over one period for feature extrac-tion. As mentioned earlier in Section 3.3.2, there exists a simple linear relationship betweenreceived signal power in terms of dBm and RSSI values. Furthermore, accuracy varies withhow fast each link is sampled over each action period by test packets. Higher data packet553.4. ResultsRunning Lateral pulldowns Jumping jack Rowing0510152025Transmission energy consumption comparison on non−periodic linksAction typeTransmission energy per packet ( µJ ) Lower boundProposedFigure 3.5: Per packet energy consumption comparison between proposed scheduling and lowerbound on non-periodic linksFigure 3.6: Approximate applicability range of the proposed scheduling algorithm; Shaded regionshows the achievable bandwidth to meet PDR>95% over a periodic link for different transmitpower levelsrates will obviously result in lower classification energy ratios for the same action duration.As seen in Figure 3.3, accuracy improves as number of samples increases. This makes sensebecause small number of samples does not capture the action properly, therefore causes errorin action classification.We have done a comparison between lower bound energy consumption explained inSection 3.2.5 and proposed scheduling technique in terms of energy consumption per packetfor different actions and for both periodic and non-periodic links in the bar charts illustratedin Figures 3.4, and 3.5 respectively. Note that in all four actions, periodic link outperforms563.5. Discussionnon-periodic link in terms of reaching energy consumption lower bound. The differencebetween the lower bound and proposed scheduling energy consumption originates from thecompletely retransmission free and minimized transmit power level adopted in the formercase. This is not practical in the real world situation because global awareness of channelfuture behaviour does not exist. In fact, Figures 3.4, and 3.5 indicate that our schedulingtechnique over periodic links is more energy efficient in comparison to non-periodic links forwhich, there is no specific pattern present.It is also trivial that our technique outperforms techniques that use real time channelassessment because it is a very energy consuming task in highly varying WBANs [108, 110].As observed in Figure 3.5, in lateral pulldowns the energy consumption of proposed schedul-ing technique is very close to the lower bound. The reason for this is the fixed nature ofthe ankle-waist link during the action. It is noteworthy that wakeup, sleep, and processingpower consumption are neglected in our analysis. As stated in Chapter 1 and reiterated inChapter 2, this is a reasonable assumption since more than 80% of WSNs energy consump-tion is devoted to communications and the fact that wake up and sleep energy consumptionis negligible compared to transmit and receive power consumption. In Figure 3.6, the ap-proximate applicability range of our scheduling and power adjustment technique in (3.3) interms of application bandwidth for periodic extremity-waist links is illustrated. Further-more, the proposed technique allows us to achieve relatively high bandwidth and PDR atlow transmit power levels, i.e., as seen in Chapter 2, 4 kB/s is adequate to achieve the de-sired bandwidth for most WBAN monitoring applications. Note that the illustrated rangeholds only for a situation when a single periodic link exists. Presence of more nodes andlinks requires further study in order to achieve the maximum bandwidth by adopting lowtransmit power levels.3.5 DiscussionIn this chapter, we proposed a scheduling algorithm that accounts for the periodic shadowingobserved over many WBAN links and thereby reduce the transmit power required to transferinformation and thereby enhance energy efficiency at the expense of latency. This techniquehelps us achieve single hop communication between some limb-torso links by adopting lowtransmit power levels which is not possible for stationary actions studied in Chapter 2. Pe-riodic prolonged actions such as fitness activities cause on-body links to undergo periodicpredictable connectivity sessions that can be exploited for low power communications. Be-573.5. Discussionside periodicity which can be used for energy efficient communication, diversity of RSSIsamples over such links provides us with mean and standard deviation features which makessimple real-time action recognition based on naive Bayes classification possible. One of themost important implications of our algorithm is placement of the nodes which are not con-strained in terms of position and are not delay tolerant in terms of application. Further,since as discussed in Chapter 2 torso might be already occupied with restricted sensors interms of placement, sensors with looser placement and latency requirements can be mountedon extremities, e.g., ankles and wrists, so that energy efficiency is achieved by single hopcommunication and low transmit power levels.The main limitations of our study are: 1) action specificity of the algorithm from theperspective that its applicability to the actions not studied in this work needs to be evaluated,2) being applicable to fixed pace periodic actions since any change in activity’s pace resultsin additional packet drops, and 3) its dependence on subject person since training set foraction recognition may be required based on a new subject.One of the most fundamental future research areas is node placement and schedulingtechniques to maximize throughput with low transmit power level for scenarios where severalperiodic links are available. Because here, as a case study, we studied energy efficiency andachievable bandwidth for a single link. However, in the real world, many nodes with looserplacement requirements may exist. Placing these nodes on locations where their connectedsessions have shorter overlap yields more bandwidth for higher data rate applications.58Chapter 4RSSI-based DistributedSelf-Localization for Wireless SensorNetworks in Precision Agriculture4.1 IntroductionIn this chapter, we propose a RSSI-based distributed Bayesian localization algorithm basedon message passing to solve the approximate inference problem. The algorithm is designedfor precision agriculture applications such as pest management and pH sensing in largefarms where greater power efficiency besides communication and computational scalabilityare needed but location accuracy requirements are less demanding. Communication over-head which is a key limitation of popular non-Bayesian and Bayesian distributed techniquesis avoided by a message passing schedule in which outgoing message by each node doesnot depend on the destination node, therefore is fixed size. Fast convergence is achievedby: 1) eliminating the setup phase linked with spanning tree construction which is frequentin belief propagation schemes, and 2) the parallel nature of the updates since no messageneeds to be exchanged among nodes during each update, which is called the coupled variablesphenomenon in non-Bayesian techniques and accounts for significant amount of communica-tion overhead. These features make the proposed algorithm highly compatible with realisticWSN deployments, e.g., ZigBee which are based upon the AODV where RREQ and RREPpackets are flooded in the network during route discovery phase.Since late 1990’s, a wide range of indoor and outdoor localization techniques have emergedbased on camera, infrared, wireless local area network (WLAN), ultra wide band (UWB),Bluetooth, and RFID [119, 120], while GPS technology has revolutionized outdoor localiza-tion. Localization techniques are developed for a wide variety of applications and are differ-ent in terms of accuracy, coverage, cost, responsiveness and adaptiveness to environmentalchanges [121, 122]. Even though GPS-based localization techniques are attractive in terms594.1. Introductionof accuracy, their impaired coverage in metropolitan environments and lack of cost-effectivescalable solutions sparked emergence of IEEE802.15.4/ZigBee localization algorithms thatwork based on RSSI. These techniques have advantage over Bluetooth, UWB and Wi-Fi[123] due to their energy efficiency and capability to support high-range communicationand mesh networking [124]. Further, even though RSSI-based techniques are less accuratecompared to camera-based and infrared technologies, cost efficiency makes them ideal forlarge scale outdoor applications such as agricultural environments in which distance betweennodes so called inter-node distance is relatively high and localization accuracy requirementsare looser.Precision agriculture is one of the rapidly growing WSN areas for outdoor environmentswhich enhances crop management and yield through sophisticated management of soil, waterresources and applied inputs [125]. WSNs are deployed to improve spatial data collection,precision irrigation, variable-rate technology and supplying data to farmers [17, 126–128].This requires sampling of critical features such as soil pH, moisture, electrical conductivityin addition to deployment of actuators to trigger a wide variety of processes varying fromdrip irrigation to pest management, e.g., mating disruption. In order to provide meaningfulfeature maps that improve resource management and decision making, being aware of loca-tion of the sensors that have generated data is critical [129]. Loose accuracy requirementsbeside the cost involved with equipping all sensors with GPS, raise the need for localizationalgorithms which are low cost, and are compatible with COTS transceiver modules. This isparticularly important for large WSNs such as precision agriculture and smart grid wherefaulty recordkeeping, i.e., human error in data logging, has been reported a lot and may evencause devices to get lost. Besides, the sensor boxes which contain battery, transceiver andother components as well are usually taken off in bulks before being taken for service andbrought back for re-installation therefore operators need to be able to install them withouthaving to necessarily mount them at their initial point. These make a localization algorithmthat could seamlessly run and make each box aware of its location save a lot of time andresource.In this work, we propose an anchor-based, probabilistic, distributed and range-basedlocalization technique for static IEEE802.15.4 WSNs using RSSI samples. The algorithmis called Bayesian model for information aggregation, and is particularly suited to preci-sion agriculture or applications with similar accuracy requirements, network size and nodeconnectivity. Moreover, anchor-based localization algorithms make use of landmarks or an-chor nodes to help localizing unknown nodes [130] and are divided into range-based and604.1. Introductionrange-free techniques. Range-free algorithms do not take advantage of distance, angle ortime measurements in order to execute localization [131]. These algorithms use connectivityinformation [132], distance in terms of number of hops [133, 134] or other measurement freemetrics for positioning. On the other hand range-based algorithms exploit time of arrival(TOA) [135], angle of arrival (AOA) [136] or RSSI [137] to estimate inter-node distances.RSSI-based techniques [138–141] which are more attractive in the sense that no additionalhardware is required in order to make the distance estimation, have been proposed fornode localization in general context and precision agriculture applications as well [142]. Onthe other hand, distributed or cooperative techniques [9, 82] are attractive for large scaleproblems since processing burden is divided between nodes and are classified as Bayesianand non-Bayesian schemes. The algorithm proposed in this work belongs to Bayesian dis-tributed techniques where cooperative schemes are proposed to solve Bayesian estimatorssuch as minimum mean square error (MMSE) and MAP. In most distributed Bayesian tech-niques message passing algorithms such as belief propagation (BP), nonparametric beliefpropagation (NBP) and their variants are proposed to estimate the marginalization over aMarkov random field (MRF) that contains nodes location and pairwise distance estimates be-tween them as variables and observations respectively [143–146]. Whereas, in non-Bayesianschemes techniques such as alternating direction method of multipliers (ADMM) [147], de-scent gradient [148–150] and sequential greedy optimization (SGO) [151] are applied to solveconvex relaxation localization problems, i.e., semidefinite programming (SDP) and second-order cone programming (SOCP) [152, 153], or directly to solve the non-convex problem ina distributed manner.BP-based techniques are vulnerable to loopy graphs which cause them either not to con-verge at all or converge only under specific circumstances in terms of number of loops [154].Therefore these techniques are mostly used for the scenarios where a few slowly movingor static nodes along with relatively high number of anchors, and all equipped with shortrange transmitters, render the statistical graph spanning tree or have few number of loops.Further, multi-hop communication, at least O(N) communication cost, is required both inorder to form the statistical graph or the spanning tree. On the other hand, distributed non-Bayesian techniques are more suited to localization for large static WSNs and the fact thata fairly large number of these techniques is proposed in the literature, serves as an evidencefor that. Further, most of these techniques work based on single-hop communication andare not susceptible to loops in the network. However these works suffer from significantlyhigh communication overhead which is associated with the information that is required to614.1. Introductionbe exchanged among neighbouring nodes between consecutive update iterations. In the dis-tributed optimization context, this phenomenon is called coupled variables or complicatingvariables where each node depends on information from other nodes to form its new op-timization subproblem or update its outcome. Computational complexity which is linkedwith the tasks nodes are assigned during each iteration is another issue. On the other hand,in precision agriculture applications, relatively high number of connected unknown nodes,limited processing power of embedded microcontrollers and underlying IEEE802.15.4 WSNswhich work in conjunction with route discovery phase of AODV routing protocols, call fora real-time, fast and power efficient algorithm which relies on local single-hop informationexchange and is not susceptible to loops in the network.Our proposed Bayesian framework is similar to state-of-the-art distributed non-Bayesiantechniques from the perspective that nodes only communicate with their single-hop neigh-bours while it is inspired by graph theory in social networks context [155, 156]. Further,as opposed to message passing schemes for Bayesian estimation [143–146, 154, 157] wheregraph nodes represent random variables, our work is similar to [156] with the difference lyingin the fact that in [156], nodes denote agents or social sensors whereas in our work nodesrepresent physical sensors. Moreover, we propose a Bayesian framework for information ag-gregation which has low and scalable communication cost, i.e., independent from number ofneighbouring nodes, but still achieves desired accuracy for particular precision agricultureapplications such as pest management and pH sensing. Features such as single-hop com-munication, same outgoing message to all neighbouring nodes, i.e., lack of coupled variablesphenomenon, in addition to not having to use spanning tree construction techniques resultsin an algorithm which has low communication and computational complexity, therefore isscalable.The proposed technique is well positioned to address self-localization in do it yourself(DIY) networks which run ZigBee or other proprietary networking protocols based uponIEEE802.15.4 specifications. This is associated with the fact that algorithm starts workingin conjunction with route discovery phase of AODV-based routing protocols where RREQpacket originated from an arbitrary source node is flooded in the entire network. We derivea closed-form recursive relationship for message passing schedule that updates Bayesian es-timation of nodes location at a time step during which one or multiple path loss samples aregenerated and therefore call the algorithm a Bayesian model for information aggregation.We prove that the location constraint resulted from a generated path loss sample is in factconvolution of path loss likelihood and the most recent location estimation of the generating624.1. Introductionnode. Realistic assumptions regarding independence of RSSI samples and conditional inde-pendence of location updates of nodes are used to prove that location constraints resultedfrom dependent paths (loop forming paths) multiply. This makes the algorithm faster andmore power efficient both by setup phase elimination and also nature of the recursive messagepassing schedule. Setup phase elimination includes omission of spanning tree construction,and intermediate node tracking which helps making use of location constraints resulted fromthe paths that are traversed by flooding RREQ packets. In fact, the algorithm’s robust-ness against loops in the WSN connectivity graph is verified by extensive simulations. Onthe other hand the proposed message passing schedule results in parallel updates and fixedsize outgoing message from each sensor. Moreover, as opposed to non-Bayesian distributedtechniques, neighbouring nodes do not exchange additional information between iterationswhile outgoing message size is fixed and independent of destination node, therefore does notscale and grow with number of neighbouring nodes.Since our goal is to devise an algorithm that can work in conjunction with COTStransceiver modules, we characterize path loss at 2.45 GHz ISM band. Our measurementcampaign helps us 1) show log-distance path loss model provides a good fit to our collecteddata corresponding to below and above canopy level communication, 2) derive path losslikelihood function conditioned on inter-node distance which is a fundamental part of theproposed algorithm, 3) study shadowing correlation along different directions which helpsus conclude upon conditional independence of measured path loss samples that lead to theproposed message passing schedule, and 4) generate random independent path loss samplesand evaluate our algorithm since lognormal path loss model and shadowing independence isverified. Further, our measurement campaign gives us advantage over previous works whichsimply assume Gaussian distance measurement noise and an arbitrary noise factor (NF) inmeasured distance or a known path loss exponent with independent lognormal shadowingterms to evaluate their algorithms [139, 147, 148, 151, 158]. In other words, even thoughour collected data is not adequate to test the algorithm with real data, we achieve outcomeswhich are more reliable for realistic deployments in the field.The remainder of this chapter is organized as follows: In Section 4.2, we start withconcept behind Bayesian and non-Bayesian estimators and proceed to formulate the local-ization problem, define the notations, include a summary of our measurement campaignsand describe the path loss model along with path loss likelihood function conditioned onnode locations. In Section 4.3, we devise a recursive solution to the problem stated in Sec-tion 4.2 and propose a specific implementation of this solution based on nodes multicasting634.2. The Localization Problem and Path Loss Likelihood Functionin TDMA manner. We proceed with simulations and evaluation of our algorithm along withanalytical and numerical comparison with state-of-the-art techniques in Section 4.4.2 andwrap up the chapter with conclusion in Section 4.5.4.2 The Localization Problem and Path Loss LikelihoodFunctionAs stated in Introduction, pinpoint localization accuracy is not needed for precision agri-culture applications such as pest control since knowing approximate location of originatingsensors suffices to trigger the relevant actuators. Accordingly, we define the localizationproblem in a discrete manner which means that the agricultural field is divided into smallersquare cells and location of each unknown node is determined as centroid of one of the cellsthe field is divided into. The precision of the algorithm is adjustable via number of gridcells inside the field, however precision flattens once grid resolution exceeds a threshold.In the following, first we describe the concept behind Bayesian estimators for localizationproblem, approximate inference methods and message passing algorithms in Section 4.2.1.Formulation of the localization problem based on aggregated path loss samples from neigh-bour nodes is discussed in Section 4.2.2 and path loss model for orchard environments isexplained briefly in Section 4.2.3. The purpose from deriving path loss model is to evaluatethe proposed localization algorithm based on realistic assumptions in terms of connectivitybetween nodes in addition to a realistic path loss likelihood function which expresses prob-ability of a measured path loss value conditioned on a given distance. In Section 4.3, wewill see that this likelihood function is an essential part of the proposed distributed algo-rithm. Besides, our studies with regard to shadowing independence will help us simplify therelationships which will lead to our simple scalable localization algorithm in Section 4.3.4.2.1 ConceptIn this section, we briefly describe the non-Bayesian and Bayesian localization problem inSections 4.2.1, and 4.2.1. Thereafter, we proceed with a brief introduction to message passingalgorithms which are approximate inference methods for Bayesian estimators and include theline of reasoning behind the Bayesian model for information aggregation in Section 4.2.1.Note that in both Bayesian and non-Bayesian methods we are interested to estimate aparameter vector x from an observation vector z. The observation vector could containdistance or location related measurements such as RSSI, noisy distance measurement, TOA644.2. The Localization Problem and Path Loss Likelihood Functionor AOA.Non-Bayesian Estimators and Distributed MethodsIn non-Bayesian estimators, x, the parameter to be estimated, would be treated like anunknown deterministic parameter. Non-Bayesian estimators are divided in to least square(LS) and maximum likelihood (ML) methods. Let z = g(x) + µ where g(·) is a knownfunction and µ is the measurement error, one can define LS and ML estimators as,X̂LS = argminx‖z− g(x)‖2,X̂ML = argmaxxPZ|X(z|x),(4.1)where ‖·‖ represents norm function. As can be seen, the main difference between LS andML estimators is that the former does not take noise statistics into account. In case obser-vations are RSSI samples, X̂LS turns into summation of quadratic terms relating distanceextracted from g(·) [158, 159] whereas X̂ML would be equivalent to summation of logarithmicterms [147, 160]. Both of these formulations are strongly non-convex optimization problemsand are NP-hard. Therefore SDP [147, 151, 161, 162] or SOCP [152, 153, 163] relaxationtechniques are used to create convex optimization problems. Methods such as ADMM [147],descent gradient [148, 149], and SGO [151] among others are used to distribute the convexSDP, i.e., full SDP or edge-based SDP [164] among the sensors. Some of these techniquessuch as descent gradient are well suited to be directly applied to non-convex problems.In Section 4.4.2, we will compare state-of-the-art distributed techniques which are used tosolve these problems with our proposed Bayesian scheme in terms of communication andcomputation complexity.Bayesian Estimators and Approximate Inference MethodsBayesian formulation of the localization problem consists of inference of location of unknownnodes represented by vector x based on observation vector x. As opposed to non-Bayesianestimators, x is treated as random variable. The two well known Bayesian estimators areMAP and MMSE which estimate the location of sensors asX̂MMSE =∫xPX|Z(x∣∣z)dx,X̂MAP = argmaxx[PX|Z(x∣∣z)]. (4.2)654.2. The Localization Problem and Path Loss Likelihood FunctionNote that integration is replaced by summation for discrete problems. It is well-known thatBayesian location estimation (4.2), i.e., joint solution, for large number of sensors is anintractable problem with exponential complexity. Therefore one may resort to solve theseestimators with respect to individual location components Xk, i.e., PXk|Z(xk∣∣z). Messagepassing algorithms have emerged to provide an approximate solution to this problem, whichis generally NP-hard. In the next section, a brief review on these algorithms and the rationalebehind our proposed algorithm is provided.Message Passing Algorithms and Bayesian Model for information AggregationConsequently message passing algorithms like sum product algorithm (SPA), and its vari-ants such as BP, NBP and other message passing schemes are proposed to approximatemarginalization over a MRF, so called factor graph which represents location of nodes anddependencies between them by vertices and edges respectively.While SPA is a message passing algorithm which gives the exact solution for acyclicgraphs, it is extended to provide iterative message passing over cyclic factor graphs inorder to provide approximate solution which is no longer equal to the exact marginal aposteriori distribution. In loopy factor graphs there are many ways these messages alsoknown as message passing schedule are calculated and with each of them resulting in adifferent marginal distribution [82]. Most existing message passing schedules entail one orboth of the following features;1. outgoing message from a vertex to each of the neighbouring vertices is different there-fore communication overhead scales linearly as a result of increased sensor density,2. spanning tree of the statistical graph is constructed before message passing runs.These features increase communication overhead and render the algorithms not suitable forlarge scale WSNs. Besides, they make the algorithm unsuitable for deployment along withroute discovery phase of AODV-based routing protocols running on IEEE802.15.4 COTS.In order to address the issues claimed in Section 4.2.1, we aim to propose a message passingschedule with following properties;1. outgoing messages from each node is independent from the neighbouring node it arrivesat, since this renders the protocol scalable in terms of communication overhead,2. message passing schedule runs in parallel, i.e., nodes update their location once eachobservation is made which is highly compatible with multicasting nature of route664.2. The Localization Problem and Path Loss Likelihood Functiondiscovery phase in AODV routing protocols.3. there is no setup phase communication overhead since there is no need for spanningtree construction.4.2.2 Problem FormulationLet S = {S1, . . . , SN} be a set of sensors randomly scattered in a square field which is dividedinto m × m square cells with equal areas, and Ω = {1, 2, . . . ,m2} be the sample space ofall possible cell coordinates. Our objective is to make use of inter-node communicationsand find the grid cell each node is located in. In the following, we introduce the notationsand formalize the localization problem. It is noteworthy that we opt to use thin face lettersrepresenting scalar variables whereas bold letters represent variables in vector format.Without loss of generality, let the first na nodes be landmarks Sl = {S1, . . . , Sna}, andunknown nodes be represented by Su = {Sna+1, . . . , SN} while y[l]ij is a path loss sample oraverage of multiple path loss samples that Sj collects from Si at l-th time step. Note thatin general, multiple samples are collected, in case each calculation time step is composed ofmultiple communication time slots. Let Yk denote the vector of path loss samples whichhave been communicated between pairs of connected nodes during the first k time steps andlet y[k]jrepresent vector of all path loss samples that Sj has collected from its neighbournodes with index set Nj at k-th time step,Yk = (y[l]ij ) l = 0 : k1 ≤ j ≤ N, i ∈ Njy[k]j = (y[k]ij )i∈Nj· (4.3)Note that y[k]mj is not available in case, Sj has not collected any sample from Sm at k-th timestep. Let X[k]j be a random variable defined over Ω representing location estimation of Sjat k-th time step. Considering that we are looking to estimate location of Sj at M -th timestep based on previously aggregated data YM,xj = argmaxxj[P (X(M)j = xj∣∣YM)], (4.4)where P (·) is the probability function and argmaxx[f(x)] is the set of points x for which f(x)attains its largest value. In the remainder of this section, path loss model for agricultural en-vironment which is the key to generate y[l]ij samples, Yk and y[k]j is explained. Consequently674.2. The Localization Problem and Path Loss Likelihood Functionwe derive the path loss likelihood function that underpins the recursive algorithm describedin Section 4.3. Moreover, we derive likelihood of y[l]ij given that Si and Sj are estimated tobe located at xi and xj respectively, i.e., P (y[k]ij∣∣X [k]j = xj ,X [k]i = xi) .4.2.3 A Representative Path Loss Model for Orchard EnvironmentsIn this section, we describe the path loss model resulted from our measurement campaigns inapple orchards located at Keremeos, BC, Canada. This underlies the work in Section 4.2.4which explains derivation of path loss likelihood function expressing path loss distributionconditioned on the transmitter (Tx) and the receiver (Rx) locations. In the following, first webriefly explain path loss models in vegetated environments with more focus on log-distancepath loss model which proves to be the most suitable fit to our collected data. Afterwards,we proceed with our measurement campaign.Path Loss Models for Vegetated Environments: Several models are proposed forpath loss behaviour in vegetated environments. These models are mostly classified into mod-ified exponential decay (MED) [91], modified gradient models, and Nonzero Gradient [165].A drawback of these models is that they only account for the vegetation path loss. Further,there are more factors such as ground and canopy reflection that contribute to path loss.This makes the aforementioned models unable to make a good prediction of path loss in re-alistic environments [166]. In [166], modified models that take ground and canopy reflectioninto account have been proposed. However, these models are more complex because theyinclude summation of multiple terms in order to account for ground and canopy reflection.In order to address this issue, log-distance model is proposed since it encompasses effects ofall contributing factors and propagation mechanisms [75, 167–169]. Furthermore, there isan extensive literature on path loss models in forests and agricultural environments, whileeach model best fits to a different scenario and environment. In several works [75, 168, 169],log-distance path loss model is claimed to provide a good fit to the path loss collected invegetated environments,PL[dB] = PL0 + 10n log(dd0) +Xσ, (4.5)where Xσ is a zero-mean normal random variable with standard deviation σ, Xσ ∼ N(0, σ),while PL0 represents path loss at reference distance d0 and n denotes path loss exponentfor the specific case of study.684.2. The Localization Problem and Path Loss Likelihood FunctionMeasurement Campaign: We carried out the measurements in the Dawson orchards atKeremeos, British Columbia (BC). Measurements were conducted in a 6 hectare (ha) highdensity apple orchard consisting of apple tree rows with approximately 3 m height. We usethe path loss data collected from four directions of along, cross, 30◦, 45◦ and 60◦ with respectto tree rows, using different transmitter (Tx) and receiver (Rx) antenna heights. Further, weconducted measurements with Tx at 2.5 m (below canopy level) and 4 m (above canopy level)heights and Rx at 2.5 m. This setup is compatible with realistic WSN deployment scenarioswhere gateways, responsible for aggregating data of their neighbouring sensors, are mountedabove canopy while sensors and actuators are placed inside the canopy. As localization isconcerned, gateways which have better line-of-sight (LOS) are equipped with GPS to play thelandmark role. The measurements were conducted throughout three different measurementcampaigns, seven days combined and spread across two summer seasons. Measurements weredone in approximate range of 0-100 m at points which are approximately 10 m apart fromeach other at 9 different parts of the orchard along five directions illustrated in Figure 4.1.Our equipment on the transmitter side, are an Agilent E8267D vector signal generator (VSG)that feeds a 2.45 GHz omnidirectional dipole antenna with 5 multi-tones (5 MHz apartfrom each other) through a ZVA-213 power amplifier, in order to provide +23 dBm as theantenna input. While, on the receiver side, a Toshiba laptop which runs MATLAB andAgilent connection expert, i.e., specialized proprietary software for connecting computer toAgilent spectrum analyzer, is connected to a N9342C handheld spectrum analyzer (HSA) viaa LAN cable. Extra losses and gains resulted from cables, connectors and antennas at bothTx and Rx sides have been taken into account for calibration. We applied Kolmogorov-Smirnov (K-S) test at 5% significance level on our collected path loss data and verifiedGaussian distribution of path loss data around mean log-distance path loss data PL[dB]in (4.5) both for above and below canopy level communication. Besides, in Table 5.5 fitnessof popular path loss models for vegetated environments, e.g., MED, modified MED modelsand log-distance is tested against the collected data. The statistical measure R2 indicateshow well data fits a specific model, while root-mean-square error (RMSE) is an indicationof difference between predicted and observed samples. Since log-distance path loss model isa good fit to the data collected, 95% confidence interval (CI) for PL0 and n are expressedin Table 4.2, while path loss samples for two modes are illustrated in Figure 4.3. Note thatgateway-to-node and node-to-node communications comply with above and below canopylevel Tx modes respectively. As illustrated in Figure 4.3 and consistent with [170, 171] pathloss improves under raised Tx height conditions. According to our experimental data, path694.2. The Localization Problem and Path Loss Likelihood Function(a) Measurement scenarios are illustrated; Lightgreen dots represent tree rows and black dots showTx antenna position whereas Rx cart moves alongindicated directions(b) Magnified version of a measurement scenarioon the left is illustrated; in each scenario Txantenna (red dot) is fixed whereas Rx cart (blackdots) moves along the designated directions tocollect dataFigure 4.1: 9 measurement scenarios inside the orchard is illustrated; Transmitter antenna wasmoved 50 m across the rows to form a new scenario whereas Rx was moved along five differentdirections of along, cross, 30◦, 45◦ and 60◦ for each scenario and path loss samples were collectedthrough 0-100 m range and at ≈ 10 m apart points. Rx antenna was placed at 2.5 m elevation(0.5 m below tree height) while Tx antenna height was at 2.5 m and 4 m elevation (1 m abovecanopy level).loss improvement at short distances (≈ 50 m) complies with antenna gain GA = 20 log(hthr)suggested in literature where ht and hr are TX and Rx antenna height respectively. Howeverat longer distances, improvement observed in above canopy communication outperforms thegain predicted by [170, 171]. We believe the additional gain in path loss, particularly at longdistances, is associated with extra LOS that we achieve by raising Tx antenna over canopylevel.Shadowing Correlation: In the measurement campaign procedure, we observed thatpath loss samples are normally distributed around the mean path loss. Studying the cor-relation between pairs of links, i.e., samples arriving from different directions, is importantsince the independence between these samples will be exploited in Section 4.3.1. In order toconduct such a study, links are classified pairwise. The classification is based on length of thelinks and their relative orientation, so-called an arrangement inspired by the approach sug-704.2. The Localization Problem and Path Loss Likelihood Functiongested in [172]. Further, we choose pairs of links which are similar in terms of geometry, i.e.,rotated versions of a specific pair in different measurement scenarios. For example in Fig-ure 4.1, an arrangement with specific lengths, e.g., 10 m and 20 m links which are 60◦ apartfrom each other contains 4 pairs without replacement in each scenario, therefore 36 pairs intotal. We calculate shadowing correlation for all the arrangements that are α◦ apart fromeach other and let ρα denote average of these correlation values.In Table 4.3, average correlation values corresponding to arrangements of a specificangle in addition to standard deviation of these values are tabulated. It is noteworthy thatin order to calculate the average shadowing, these arrangements are not separated in termsof length. This is because, there is no significant variation observed particularly among thelinks that matter in this work, i.e., longer than 40 m associated with inter-node distances.Table 4.1: (R2,RMSE) for different variants of MED models, modified MED models based on [166]to take the canopy and ground reflection into account as well.❤❤❤❤❤❤❤❤❤❤❤❤❤❤ModelCommunication ModeAbove canopy Below canopyWeissberger (0.67,6.85) (0.3,14.01)ITU-R (0.43,9.04) (0.03,12.08)FITU-R (0.71,5.16) (0.3,10.29)Log-distance model (0.78,3.65) (0.74,5.67)Table 4.2: Path Loss Model characteristics for above and below canopy level modesMode n PL0 [dB] σ [dB] R2 95% CI for n 95% CI for PL02.45 GHz-Tx below canopy level 3.61 75 5.27 0.74 3.36-3.86 71-792.45 GHz-Tx above canopy level 2.91 72 4.14 0.78 2.60-3.22 67-77Table 4.3: Average shadowing correlation for pairs of links that are extended with specific angleswith respect to each other. Each average value is derived from correlation values of arrangementswith a specific angleMode below canopy above canopyShadowing correlationNumber of pairsper arrangementAverage Standard deviation Average Standard deviationρ0◦ 45 0.07 0.05 0.05 0.08ρ30◦ 36 0.04 0.07 -0.03 0.07ρ45◦ 36 0.06 0.07 -0.06 0.07ρ60◦ 36 -0.06 0.06 0.08 0.09ρ90◦ 18 -0.03 0.11 -0.04 0.08714.2. The Localization Problem and Path Loss Likelihood FunctionFigure 4.2: Location pmf of unknown nodes is updated recursively. Agricultural field is dividedinto m×m cells with equal area and probability of an unknown node being located inside each cellis calculated based on recently aggregated path loss samples and prior location pmf of connectednodes.10 100−120−110−100−90−80−70−60Path loss comparison for below and above canopy Tx scenariosDistance [m]Path Gain [dB] Tx above canopyTx below canopyPL[dB]=72+29.1log(d/10)PL[dB]=75+36.1log(d/10)Figure 4.3: Path loss samples for below and above canopy Tx level at 2.45 GHz collected from threemeasurement campaigns along with linear log-distance fits are illustrated. Values in distance axisappear in logarithmic scale; The difference between the two above and below canopy modes, whichis due to more line of sight (LOS) between Tx and Rx in the above canopy case, could be seen.724.3. Localization Algorithm for Precision Agriculture Applications4.2.4 Path Loss Likelihood FunctionIn this part, we derive likelihood function P (y[k]ij∣∣X [k]j = xj ,X [k]i = xi) which is a key com-ponent of the algorithm we propose in the next section since it relates path loss values tointer-node distances. A discretization process on likelihood function is required in orderto extract likelihood probability mass function (pmf), because RSSI samples that the pro-posed algorithm is going to use are discrete in nature. Therefore, we need to calculate theprobability that the discretized path loss sample y[k]ij would equal arbitrary value α over thedistance dij , P (y[k]ij = α∣∣D = dij). Assuming log-distance path loss model as discussed inSection 4.2.3 and taking a random point on the field into account, the probability of con-tinuous path loss sample plij falling in the range [α − ∆2 , α + ∆2 ], ∆ << α and when Sj islocated at distance dij from Si is calculated byP(y[k]ij = α∣∣D = dij) ≈ P(α− ∆2< plij < α+∆2∣∣∣∣D = dij) =C∆√2piσ2e−(α−PL(dij ))2σ2 ,(4.6)where PL(d) = PL0+10n log(dd0) is mean path loss at distance d while C is the normalizationconstant. Moreover in practice, in order to approximate the above conditional probability,we collect amplitude of the normal distribution with mean PL(dij) and standard deviationσ in the range[PL(dij)− 3σ, PL(dij) + 3σ]at 1 dB steps and normalize the values sothat they sum up to one. In Figure 4.4, we illustrate how path loss likelihood functionis created based on discretization step ∆ and observed path loss value α. On the coursefor discretization, discretization step ∆ and the PDF function which is Gaussian due tolognormal path loss model affect normalization value C. This process enables us to labeleach path loss and distance pair with a likelihood value. Based on (4.6), and the factthat each pair (xi, xj) translates into the corresponding distance dij , sensor Sj calculatesP (y[k]ij = α∣∣X [k]j = xj,X [k−1]i = xi), ∀xi, xj ∈ Ω.4.3 Localization Algorithm for Precision AgricultureApplicationsIn this section, we derive an algorithm to solve the problem stated in (4.4) which worksbased on Bayesian model for information aggregation. Further, our objective is to proposea recursive expression for P (X[k]j = xj∣∣Yk) that explains how location pmf is updated once734.3. Localization Algorithm for Precision Agriculture ApplicationsFigure 4.4: Discretization of path loss likelihood function involves sampling the correspondingGaussian distribution at ∆ steps within 3δ distance from mean path loss and normalizationafterwardsinformation is aggregating in the network, i.e., when the most recent evidence, i.e., RSSIsample, is collected. In Section 4.3.1, we first solve the problem for general case where ateach calculation time step, arbitrary amount of information or number of packets, betweenone or multiple pairs of nodes is exchanged. In Section 4.3.2, we proceed with the specialcase that is more compatible with route discovery phase of AODV-based routing protocolssuch as ZigBee. This special case, is in fact the algorithm simulated in Section 4.4.2.4.3.1 General CaseAccording to the notational definition in Section 4.2 and assuming that at each time step,Sj updates its location pmf only based on the samples it has received from single-hopneighbours, i.e., not samples communicated between other pairs of nodes,P (X[k]j = xj∣∣Yk) = P (X [k]j = xj∣∣Yk−1,y[k]j ) ∝P (y[k]j∣∣X [k]j = xj,Yk−1)P (X [k]j = xj∣∣Yk−1). (4.7)The second line in (4.7), results from the fact that Yk−1 ⊥ y[k]j where ⊥ denotes statisticalindependence. Note that the mentioned independence is a frequent assumption in Bayesianand non-Bayesian problems which implies that distance observations are independent fromeach other due to independent measurement noise samples [139, 147, 148, 151, 158]. Thedifference with RSSI samples in our realistic case is that in addition to random receivernoise, i.e., always independent, random shadowing also adds to mean path loss. Further, itis straightforward to show that in addition to receiver noise samples, shadowing samples also744.3. Localization Algorithm for Precision Agriculture Applicationsneed to be independent from each other in order for Yk−1 ⊥ y[k]j to hold. In Section 4.2.3,and Table 4.3 we showed that shadowing samples are gaussian and for different scenariosvery close to be uncorrelated, therefore independent. Let us recall that in general eachcalculation time step may be composed of several communication time slots, therefore wehave used y[k]jwhich are the path loss samples, Sj collects from one neighbour or a set ofneighbours during the k-th time step.Afterwards, we simplify P (y[k]j∣∣X [k]j = xj,Yk−1) in the second line of (4.7), based on thefollowing conditional independence assumption,(y[k]ij ⊥ y[k]mj)∣∣(X [k]j ,Yk−1) ∀i,m ∈ Nj , (4.8)where as defined in Section 4.2.2, N and Nj represent total number of nodes and index setof neighbouring nodes of the j-th node, Sj, respectively. Earlier, we explained the logicbehind independence of RSSI or measured path loss samples from each other and how itimplies (y[k]ij ⊥ y[k]mj)∣∣(dij , dmj). From this, (4.8) looks straightforward, because Yk−1 andX[k]j at best, only provide noisy distance measurements between other links in addition todij and dmj , therefore do not change conditional independence of y[k]ij , y[k]mj . Consequently,first term on the right-hand side of (4.7) is written asP (y[k]j∣∣X [k]j = xj ,Yk−1) = ∏i∈NjP (y[k]ij∣∣X [k]j = xj,Yk−1). (4.9)Based on conditional expectation rule, we simplify the right-hand side of (4.9),P (y[k]ij∣∣X [k]j = xj,Yk−1) =∑xiP (y[k]ij∣∣X [k]j = xj ,X [k]i = xi,Yk−1)P (X(k)i = xi∣∣X [k]j = xj,Yk−1)=∑xiP (y[k]ij∣∣X [k]j = xj,X [k]i = xi)P (X [k]i = xi∣∣Yk−1).(4.10)In (4.10), we use the assumptions (X[k]i ⊥ X [k]j )∣∣Yk−1 and (y[k]ij ⊥ Yk−1)∣∣(X [k]i ,X [k]j ). Inorder to clarify the first assumption, note that location posterior update of the j-th node,X[k]j , results from previous location update of its neighbours, i.e., Si, i ∈ Nj and the mostrecent path loss observations between Sj and these neighbouring nodes y[k]j. Traversingup the updating graph, path loss observations along with prior of the nodes suffice forX[k]j to update. Further, given all the aggregated path loss observations in the network,754.3. Localization Algorithm for Precision Agriculture ApplicationsX[k]i does not provide any information about X[k]j . The second assumption results fromshadowing correlation study in our measurement campaign following the same discussion wehad after (4.8). Combining (4.9) and (4.10) yieldsP (y[k]j∣∣X [k]j = xj,Yk−1) = ∏i∈Nj∑xi[P (y[k]ij∣∣X(k)j = xj,X(k)i = xi)P (X(k)i = xi∣∣Yk−1)].(4.11)Finally combining (4.7) and (4.11) completes the recursive update,P (Xj = xj∣∣Yk) ∝ P (Xj = xj∣∣Yk−1)×∏i∈Nj∑xi[P (y[k]ij∣∣X [k]j = xj,X [k]i = xi)P (X [k]i = xi∣∣Yk−1)]. (4.12)This means, in order to update posterior of Sj after observation of new samples collected fromSi, only priors of Si and Sj in addition to channel information P (y[k]ij∣∣X [k]j = xj,X [k]i = xi)are required. With respect to total number of nodes N , the algorithm has computationaland communication complexity of O(N) and O(1) per node, that causes the algorithm tobe scalable. The computational complexity is the same as BP-based techniques, while com-munication overhead which makes up most of power consumption in WSNs is significantlylower since each node only communicates with its single-hop neighbours. As will be ex-plained in the next section, in case the algorithm is deployed in a realistic WSN where onlyone node multicasts at each time step, communication and computational complexity wouldboth reduce to O(1).4.3.2 Localization Algorithm Compatible with Wireless SensorNetworksIn this section, we proceed with a realization of the general case algorithm which is amore specific case of the proposed recursive solution in (4.12). Moreover we assume thatat k-th time step, only Sk does the multicasting and all connected nodes update theirlocation posterior based on the observed path loss or mean of the path loss samples, i.e.,y[k]j= y[k]kj . This means each node is recipient of at most one sample at a single timestep which guarantees compatibility with real world deployment of WSNs such as TDMAor CSMA/CA, where at each time slot, a node can listen to at most one neighbour nodewithout interference. To be more specific, AODV which is the underlying routing protocolin ZigBee works based on flooding and multicasting RREQ packets and receiving RREP764.3. Localization Algorithm for Precision Agriculture Applicationsmessages, therefore our proposed localization algorithm can be integrated in a convenientand inexpensive manner. Transceiver modules such as Synapse which is equipped with lightand fast network operating system, SNAP, a more powerful microcontroller and is well-suited for more complex programming (with Python) can be used for mesh networking. InSection 4.4.2, we use numerical examples to evaluate the performance of our algorithm basedon radio characteristics of Synapse RF modules.Path Loss Model Auto-Tuning: In this chapter, as in [139, 147, 148, 151, 158], weassume that path loss is fixed and there is a global awareness of path loss model amongsensors. However, this may not be a realistic assumption due to remarkable changes dur-ing seasonal environmental variations and also possibility of spatial variations in path losscharacteristics in different environments. Complex path loss exponent estimation techniquessuch as Cayley–Menger determinant and pattern matching [173] could work in complemen-tary with our proposed algorithm. Based on the claimed results in [173], the technique iswell-positioned to work for the scenarios of our interest. Even though this technique workswell for arbitrary node placements with unknown topology, more simple techniques such asmethod of moments or quantile-quantile (q-q) plot are adoptable in case knowledge aboutdistribution of distance between neighbouring nodes is available [173]. For example, in [174],closed form internode distance distribution for complex node placement distributions suchas uniform and Gaussian has been derived. Accordingly, it is straightforward to derive dis-tance distribution for deterministic deployment, e.g., square grid which is the most frequentnode placement method in precision agriculture [173]. Note that realistically, there mightbe spatial variations over path loss statistics since they may vary between every differentpairs of nodes and along different directions. In such situations, iterative techniques mostlyinspired by Gauss-Seidel method are used to recursively update nodes locations and pathloss exponent afterwards [175]. Convergence is achieved once variations between successiveupdates fall below a determined threshold.Even though we have not incorporated these approaches into our scheme, we measuredsensitivity of our localization problem with respect to path loss exponent confidence intervaltabulated in Table 4.2. Moreover, we assume that the path loss exponent between eachnode to a neighbouring node is uniformly distributed around the centre value (which isglobally known and used to make estimations) with ±0.25 as margins around this centrevalue. Simulations show that for uniformly distributed offset, algorithm does not show muchsensitivity in terms of accuracy and convergence rate. The reason may be associated with774.3. Localization Algorithm for Precision Agriculture ApplicationsAlgorithm 2 Localization Algorithm For Agricultural EnvironmentsStep 1: Initialization (path loss model auto-tuning if required)• Initializing landmarks locationsFor i = na + 1, . . . , nt initializing unknown nodes locations• P (X [0]i ) ∼ U [1,m2]Step 2: Landmarks advertise themselves to unknown nodesFor i = 1, . . . , na∀j ∈ Ni• P (X [i]j∣∣Yi) = P (X [i−1]j ∣∣Yi−1)× P (yiij∣∣X [i−1]j = xj,X [i−1]i = xi)• Normalize P (X [i]j∣∣Yi)• Multicast and update with (4.12) continue till allunknown nodes are covered for each landmark advertisement.Step 3: A random node Si becomes source and multicasts RREQ packetStep 4:For j = na + 1, . . . , N• If dij < dconnectivity, j 6= i– Update rule (4.12) and normalization– Sj forwards and multicasts the RREQ packetif hop count, i.e., AODV allows• else– P (X[i]j = xj∣∣Yi) = P (X [i−1]j = xj∣∣Yi−1)– no change in location estimationWhile RREQ packet has not reached the landmarki← ∀j ∈ NiRedo step 4Step 5: Landmarks return the RREP packet towards the source over theminimum hop routeFor ∀ consecutivepairs of (i, j) on landmark-source route• P (X [i]j∣∣Yi) = P (X [i−1]j ∣∣Yi−1)× P (yiij∣∣X [i−1]j = xj,X [i−1]i = xi)• Normalize P (X [i]j∣∣Yi)• else– P (X[i]j∣∣Yi) = P (X [i−1]j ∣∣Yi−1)Go back to Step 3Step 5: Decision making after M time stepsFor j = na + 1, . . . , N• x˜j = argmaxxj[P (X[M ]j = xj∣∣YN)].784.4. Performance Evaluation of The Localization Algorithminternode distances as well, e.g., given ±0.25 path loss estimation offset, 40 m internodedistance results in ±1.5 dB path loss offset which in many cases is negligible compared toshadowing statistics and might be compensated in some cases.Precision Agriculture Accuracy Requirements: Coverage area of the sensors, spa-tial correlation of the measured features and distance required between actuators determineinter-node distance for deterministic grid WSN deployments. Further, inter-node distancevaries from 10 m for soil moisture [176] and electrical conductivity [177], to coarser resolu-tions, 60 m for pH sensing [178] or mating disruption applications [179]. As will be seenin Section 4.4.2, our algorithm is well-suited to pest management and mating disruptionapplications, where tolerance for error, caused by the algorithm simplifying assumptions ormistuned path loss model, is higher.4.4 Performance Evaluation of The Localization AlgorithmIn this section, first we describe the essential aspects of our simulation setup in Section 4.4.1.Afterwards, in Section 4.4.2, we present the simulation results regarding performance ofour localization scheme, including analytical and numerical comparison with state-of-the-art techniques such as ADMM [147], SGO [151] and decent gradient methods. In order toevaluate performance of our proposed algorithm, we do the simulations for both random anddeterministic (grid) deployment of WSN on a square field. Note that as stated in Section 4.1,our measurements allow us to derive the proposed message passing schedule. However, inorder to test the algorithm with real data, a lot more measurement is needed. Further,as explained in our measurement campaign in Section 4.2.3, Tx antenna was fixed in eachscenario and Rx antenna only moved along certain directions with data being collected atcertain distances. However in our cooperative algorithm, communication may occur betweenany pair of connected nodes at any location in the field, with any relative distance and angle.We particularly use simulations to show that the average number of unknown nodesand landmarks each node connects to, affect the accuracy of the localization algorithm fora specific landmark arrangement. Therefore, we define two parameters, so called averagelandmark degree and average unknown node degree. Let landmark and unknown node degreeof an arbitrary node Si be the number of landmark and unknown nodes Si is connected to.Note that node degree in graph theory is strongly related to connectivity in the communi-cations context. Further, average unknown node degree depends on the deployment densityand transmit power level of unknown nodes, while the transmit power of landmarks, location794.4. Performance Evaluation of The Localization Algorithmof the landmarks and number of them affect the landmark average degree. Different metricshave been used to evaluate performance of the localization algorithms [180].We use Twice the Distance Root Mean Square (2DRMS) as the accuracy metric forour localization technique where 2DRMS=r means there is 95% confidence that the locationestimation would fall within a circle with radius r around the actual node’s location. Notethat location estimation itself is a random variable due to random nature of path losssamples, and the generating source node. This is due to the event-driven data deliverymodel which is normally used for precision agriculture applications which implies that asensor transmits data only when a feature exceeds a predetermined threshold, thereforemessage passing schedule is different after landmarks advertise themselves. The randomnature of the problem makes 2DRMS an acceptable accuracy metric. In this work, we donot focus on optimizing landmarks location, however in the next section we describe the logicbehind our adopted landmark arrangement. In the remainder of this section, first we explainthe simulation setup and assumptions. We will then proceed with numerical examples toevaluate the performance of our algorithm.4.4.1 MethodologyIn this section, it is first explained why we opt for placing landmarks in the corner or middleof border lines, and proceed with justifying assumptions regarding adopted transmit power,orchard size and node density. For precision agriculture applications inside farms, gatewaysare placed on the corners and borders of the field, however in the following, we present thereason on why this would help to ensure the improvement of localization algorithm.Landmark Arrangement: Even though, placing landmarks close to each other and atthe centre of the field yields a higher average landmark degree, the localization accuracydrops dramatically since their path loss behaviour has a very high correlation at a givendirection and the path loss samples collected from them, are fairly close to each other atalmost any point inside the field. Moreover, we place landmarks in the middle of borderlinesor in the corners, because this arrangement provides more information about unknown node’slocation. In Figure 4.5, for a random unknown node location, it can be seen that havinga more landmark degree does not necessarily result in a better location estimation. Thisis because distances in Figure 4.5a are fairly close to each other, and given that a noisyestimation of them are made based on path loss samples, the location estimation will be farless accurate compared to the arrangement in Figure 4.5b. It can be easily shown that this804.4. Performance Evaluation of The Localization Algorithmscenario holds for most points on the field. Studying other landmark arrangements couldbe done accordingly, however we avoid to elaborate on it, since it does not add valuableinformation to evaluation of the algorithm, and is therefore beyond the scope of this work.40 90 140 190 2404090140190240Distance in cross track direction[m]Distance in along track direction[m]4321LOSLOSUnknownnode Landmarks(a) Landmarks placed in the middle with every oneof them having line of sight to the unknown node40 90 140 190 2404090140190240Distance in cross track direction[m]Distance in along track direction[m] 4231UnknownnodeLOSNLOSNLOSLOS(b) Landmarks placed on the borders with only twoof them having line of sight to the unknown nodeFigure 4.5: Two different landmark arrangements; The landmark arrangement in (b) provides moreinformation about location of the unknown node despite having fewer nodes having line of sight tothe unknown nodeTable 4.4: Deployment ScenariosOrchard size 6 ha, 20 haNode density (nodes per hectare) 3, 7Node arrangement GridTransmit power level of unknown nodes 0-15 dBmTransmit power level of landmarks 15 dBmTransmit power increment step 1 dBReceiver sensitivity for PER=1% -103 dBmGrid cell dimension 30 mNumber of landmarks 2,3,4,6 and 8Location of landmarks borders and cornersLandmark degree (6 ha orchard) varying from 1.78 to 6.3Landmark degree (20 ha orchard) varying from 0.8 to 2.18Maximum transmission distance for below canopy mode 120 mMaximum transmission distance for above canopy mode 220 m814.4. Performance Evaluation of The Localization AlgorithmDistance in cross track direction [m]Distance in along track direction [m]7 node/ha grid deployment (40 m internode distance) along with 6 landmarks 0 100 200 300 400100200300400(a) 6 landmarksDistance in cross track direction [m]Distance in along track direction [m]7 node/ha random deployment and 8 landmarks inside a 20 ha orchard100 200 300 4000100200300400(b) 8 landmarksFigure 4.6: Two different landmark arrangements; unknown nodes and landmarks aredemonstrated with green small dots and red large diamonds respectively. Location pmf for thedesignated unknown node (purple) is illustrated by heat map.0.511.522.5 010203020100220Average unknown degreeLocalization errorAverage landmark degree2DRMS [m](a) 2DRMS with respect to average landmark andunknown node degree is depicted. Surface points arecollected from all deployment scenarios5 10 15 20051015202530Transmit power level [dBm]Average unknown degreeAverage unknwon degree behaviour with transmit power level 3 nodes/ha−20 ha7 nodes/ha−20 ha3 nodes/ha− 6 ha7 nodes/ha− 6 ha(b) average unknown node degree of nodes withrespect to transmit power level of the unknownnodes. Dotted and solid graphs represent deploymentscenarios for 6 ha and 20 ha orchards respectively.Figure 4.7: Effect of landmark and unknown node degree is illustrated in (a); Effect of transmitpower level on average unknown node degree is shown in (b).Deployment Scenarios and Assumptions: In our simulation setup which is summa-rized in Table 4.4, we adopt two different orchard sizes including 6 and 20 ha with nodes824.4. Performance Evaluation of The Localization Algorithm0 10 20 30 40 50 6050100150200250Number of messages 2DRMS [m]2DRMS for 3 node/ha grid deployment and different landmark arrangements 3 landmarks4 landmarks6 landmarks8 landmarks(a) Low density grid deployment0 10 20 30 40 5050100150200250300Number of messages2DRMS [m]2DRMS for 3 node/ha random deployment and different landmark arrangements 3 landmarks4 landmarks6 landmarks8 landmarks(b) Low density random deployment0 20 40 60 80 100 120 14050100150200250Number of messages2DRMS [m]2DRMS for 7 node/ha grid deployment and different landmark arrangements 3 landmarks4 landmarks6 landmarks8 landmarks(c) High density grid deployment0 20 40 60 80 100 120 14050100150200250300Number of messages2DRMS [m]2DRMS for 7 node/ha random deployment and different landmark arrangements 3 landmarks4 landmarks6 landmarks8 landmarks(d) High density random deploymentFigure 4.8: 2DRMS for different node densities and landmark arrangements inside a 20 ha appleorchard; Low and high density grid deployments translate to 60 m and 40 m internode distancerespectively and is well-suited to mating disruption.834.4. Performance Evaluation of The Localization Algorithm5 10 15 20050100150200250300Transmit power level [dBm]2DRMS [m]2DRMS with respect to transmit power level of unknown nodes (3 node/ha) 3 landmarks4 landmarks6 landmarks8 landmarks(a) High density grid deployment5 10 15 200501001502DRMS with respect to transmit power level of unknown nodes (7 node/ha)Transmit power level [dBm]2DRMS [m] 3 landmarks4 landmarks6 landmarks8 landmarks(b) High density random deploymentFigure 4.9: 2DRMS variations with transmit power level Ptx; different scenarios in terms of nodedensity and number of landmarks inside a 20 ha apple orchard are illustrated. The 2 landmarkscenario is excluded for the sake of clarity and lack of space since it achieves a fairly low accuracy.Increasing node density allows us to achieve low 2DRMS with lower number of landmarks andtransmit powerrandomly scattered inside the field at two different densities, 3 nodes/ha, and 7 nodes/ha.As discussed in Section 4.3, these are the densities used for pest management applicationsand translate to 60 m and 40 m inter-node distance for grid deployment respectively. Gridcell dimension is chosen to be 30 m so that both these densities could be covered. Theaverage size of an apple orchard varies from 1 to 20 ha in different world regions, while theaverage size in Canada and the United States is approximately 6 ha and 20 ha respectivelyaccording to the United States Department of Agriculture [181]. Node density and typeof deployed RF modules varies based on the precision agriculture application and requiredsampling range [182]. We simulate the algorithm with four landmark arrangements, whiletransmit power level of unknown nodes is between 0 and +15 dBm. Receiver sensitivityfor PER=1%, is -103 dBm, and the communication between landmark and nodes occurs atmaximum transmit power (+15 dBm). Variation of landmark degree for different number oflandmarks and orchard sizes is also expressed in Table 4.4, which is based on the assumptionthat Synapse RF200 modules are used [183].As mentioned earlier in this chapter, we assume that landmarks (gateways) and un-known nodes (sensors) are mounted above and below canopy level respectively. We call Siand Sj connected, dij < dconnectivity, in case the probability of RSSI falling below receiver844.4. Performance Evaluation of The Localization Algorithmsensitivity is below 1% or connectivity probability is above 99%. This maximum transmis-sion distance is calculated based on our measurement-based path loss model summarizedin Table 4.2. In Table 4.4, we have tabulated the transmission distance of Synapse RF200module at its maximum transmit power so that connectivity requirement is met [183]. Inthe next section, we evaluate the performance of our algorithm.4.4.2 ResultsIn this section, we study the localization error of our algorithm for different simulation sce-narios. In Figure 4.6, two landmark arrangements, 6 and 8, along with 150 deterministicallyand randomly scattered sensors transmitting at maximum transmit power, are illustrated.Location distribution of one designated node (purple node) after the algorithm convergesis illustrated. In Figure 4.7a, we show the behaviour of 2DRMS with respect to averagelandmark and unknown node degree. As seen in the surface plot, error drops dramaticallywith average unknown node degree increasing. Further, even for a low average landmarkdegrees, ≈ 1.5, an approximate average unknown node degree of 8 yields the desired 2DRMS(≈ 20 m).In Figure 4.7b, we demonstrate how average unknown node degree increases withtransmit power level of unknown nodes in different simulation setups. These two figuresprovide an insight on how algorithm works with different transmit power levels. In Figure4.8, 2DRMS behaviour for different simulation setups during course of the algorithm isdemonstrated which shows that the algorithm converges after a few messages are multicast inthe network. As explained in Algorithm 2, the procedure starts with landmarks advertisingthemselves to the entire network. This accelerates convergence of the algorithm significantly,because one-hop neighbours of landmarks achieve a narrower pmf estimation during the firstround. As can be seen in Figure 4.8, generally 6 and 8 landmark/gateway scenarios meetthe accuracy requirement for pest management, however in order to make the algorithmwork for soil moisture application, number of landmarks or their maximum transmit powerneeds to increase.In other words, our simulations showed that a finer grid resolution does not affectthe accuracy in case cell dimension already supports the application in terms of internodedistance. We also observed that the total number of messages needed for algorithm toconverge grows slower than O(N) which is a promising aspect from the scalability stand ofview. Moreover, in spanning tree variants of BP-based techniques, at least O(N) messagesare required to make the spanning tree and after that every sensor needs to do a multicast854.4. Performance Evaluation of The Localization Algorithmat each iteration with algorithm taking anywhere between 1 and 3 iterations to converge.This means our algorithm is faster and consumes less communication energy to converge atthe expense of accuracy.In Figure 4.9, localization error for a 20 ha orchard, 40 m and 60 m inter-node distances,with respect to transmit power level is depicted. Node density has higher influence at lowtransmit power levels which is compatible with our observations from Figure 4.7a. Oncetransmit power increases, at a fixed landmark degree, average unknown node degree exceedsthe required threshold and error drops to minimum. Based on [173] and our simulations,the algorithm meets pest management (mating disruption) requirements with acceptableprobability inside a 20 ha orchard with 8 landmarks. However a different transceiver moduledemands for different landmark setups since the maximum transmit power level is different,whereas more landmarks are needed in larger orchards in order to meet the average landmarkdegree.Comparison with State-of-the-art Distributed Techniques: In this section, we com-pare our proposed algorithm with state-of-the-art distributed techniques which were brieflyexplained in Section 4.1 and 4.2.1 and have been applied to similar localization problems,i.e., large static anchor-based WSNs. As seen in Table 4.5, which has been partially ex-tracted or derived from [147, 148], the main advantage of our algorithm is its scalabilityreflecting in communication and computational cost which does not scale with size of theWSN. Note that in [148] which is a gradient decent algorithm a dynamic step size updatealong with position update is being used in order to accelerate the normally slow convergenceof gradient descent algorithms, i.e., proportional to inverse square root of iterations num-ber [184]. Gradient descent algorithms are more close to our work from the communicationcost point of view since each node only transmits its location which is identical for everydestination node however they suffer from very slow convergence. Step-size adjustment dis-cussed in [148] introduces communication complexity because of coupled variables howeverincreases convergence rate. Further, in each node two inner and outer sets of iterationscorresponding to step size and position updates are running. Both sets of updates requireinter-node messages to be exchanged between a node and all its neighbouring sensors whichimposes an immense communication overhead.In [147], ADMM method is used to solve convex edge-based relaxation of localiza-tion problem, with coupled variables, in a distributed manner. Moreover each node needsinformation from neighbouring nodes in order to solve a convex SDP optimization at each864.4. Performance Evaluation of The Localization Algorithmiteration, i.e., Algorithm 2 in [147]. On the other hand in [151], an extension of Gauss-Seidelalgorithm is used to solve the edge-based relaxation problem in a distributed manner. Themain differences compared to [147] is that the optimization problem at each node is SOCP,i.e., less complex and problem is solved sequentially, thus converges significantly slowerthan [147]. The proposed Bayesian model for information aggregation in this chapter has acommunication and computational cost that only grow with field dimensions as opposed tosize of the WSN in terms of number of nodes. Since iterations in our work and discussedtechniques are different both in terms of duration and communication context, we use themetrics in Table 4.6 for numerical comparison.In the numerical comparison, we only compare the Bayesian proposed model with thealgorithms which can run in parallel [147, 148] since sequential algorithms such as SGO [151]are not well-suited to run in conjunction with route discovery phase of AODV-based proto-cols. We use the scenario with high density grid deployment and 8 anchors for numericalcomparison against [147, 148]. This is one of the scenarios used in Section 4.4.2 and verysimilar to the scenario used in [148]. We used MATLAB CVX along with SDPT3 pack-age to solve the SDP optimization problems at each node in [147] whereas MATLAB wasused to solve Algorithm 2 in [148]. In order for the comparison to be fair, we assume thatdata containing coupled variables in the discussed non-bayesian techniques is encompassedin one packet and is multicast once since this is compatible with the proposed bayesianmodel for information aggregation. Note that in gradient descent, number of messages isrelatively too high even though amount of exchanged data is lower. This translates to slowconvergence rate compared to ADMM [147] and the proposed technique. Aggregate energyconsumption of these techniques have been calculated based on transceiver characteristicsof Synapse modules. It is noteworthy mentioning that our scheme can be in fact used as aninitialization scheme for gradient descent methods in the applications where high accuracyis required while number of anchors is limited.Table 4.5: Analytical comparison of the proposed technique with state-of-the-art distributednon-Bayesian techniquesPer node per iteration ADMM [147] SGO [151] Gradient descent [148]ProposedBayesianTechniqueSize of the problemconvex optimization with7|Ni|+ 2|Ni,a|+ 3 variablesconvex optimization with4|Ni|+ 3 variablesLocal gradient andtranslation withneighbouring nodes informa-tionm4 multiplicationsand summationsComputational complexity O(|Ni|+ |Ni,a|3) O(|Ni|3) O(1) O(1)Communication cost 9|Ni| 2|Ni| O(|Ni|) O(1)874.5. DiscussionTable 4.6: Numerical comparison of the proposed technique with state-of-the-art distributednon-Bayesian techniques for 7 nodes/ha and 8 anchors to achieve the desired accuracy(2DRMS=20 m)Comparison metric ADMM [147] Gradient descent [148] Proposed Bayesian TechniqueExchanged information [kB] 183 135 24Number of communicationrounds1700 65000 90Energy consumption for Synapse [mJ ] 10 7.6 1.34.5 DiscussionLarge size of the WSNs deployed in agricultural fields in addition to nature of higher layercommunication algorithms in terms of TDMA-based MAC and multicasting make mostexisting distributed localization algorithms ill-suited for use in such environments. More-over Bayesian distributed techniques suffer from communication overhead required for setupphase in order to form loop-free graphs. Whereas non-Bayesian techniques are burdenedwith excessive communication overhead resulted from coupled variables, remarkable compu-tational complexity needed to solve optimization problems at each iteration and generallysuffer from slow convergence.Our scalable RSSI-based localization algorithm overcomes these limitations by: 1) us-ing only local distance estimates with respect to neighbouring nodes, and 2) using a messagepassing schedule which benefits from a fixed size outgoing message that does not grow withnumber of neighbouring nodes, and 3) low computational complexity per node at each itera-tion which only grows with grid size and only involves summations and multiplications. Thealgorithm uses a Bayesian model for information aggregation to achieve scalable communi-cation and computational complexity with respect to the number of nodes at the expenseof accuracy.The main strength of our localization algorithm is its compatibility with realistic de-ployment scenarios of WSNs and the low communication overhead it adds to the alreadydeployed routing protocols. Further, the route discovery phase of AODV routing protocols,e.g., ZigBee and similar schemes, work based on flooding and multicasting RREQ pack-ets; therefore our proposed localization algorithm can be integrated in a convenient andinexpensive manner. Shadowing independence over the links in the apple orchard is an im-portant feature that leads towards the proposed iterative update to the localization problem.However, there are real world scenarios such as urban area where there might be a largecorrelation among shadowing observed over links.The main limitation of the proposed algorithm in this chapter is its incapability in884.6. Acknowledgementterms of achieving high precision localization. Further, as a remedy the proposed algorithmcan be used as the initialization step for algorithms such as gradient descent which sufferfrom high sensitivity to initialization. Moreover the proposed Bayesian model for informa-tion aggregation can be used to accelerate convergence of slowly converging gradient descentalgorithms in addition to providing them with the initialized location for the scenarios withfew number of landmarks and high number of nodes. As a future work, a WSN compatiblelocalization algorithm that overcomes such impairments and eliminate the message depen-dence and error propagation with low communication and computation complexity wouldincrease applicability domain of this algorithm to a huge extent.4.6 AcknowledgementWe would like to greatly thank SemiosBio, Vancouver-based startup company specializingin precision agriculture, for generously supporting and funding our measurement campaignsin addition to granting us access to the Dawson orchard at Keremeos, BC. SemiosBio’s needfor a localization algorithm which could run on Synapse transceiver modules to addressmating disruption application was a significant inspiration for the work proposed in thischapter. We would also like to thank UBC Radio Science Lab (RSL) 2012 and 2013 studentvolunteers for their hard work in preparing for conducting the measurement campaign.89Chapter 5Directional Path Loss and ItsImplications for Node Placement andNetwork Performance5.1 IntroductionExistence of radio irregularity and its effects on the performance metrics of routing protocolshas been long recognized and studied in the literature [25, 26, 185]. The most dominantfeatures of radio irregularity which have been studied are attributed to shadow and flatfading [25]. Moreover, effect of different radio wave propagation models such as shadowing,two-ray-ground and free space model on the performance of classic routing protocols suchas AODV, DSR, OLSR and DSDV routing for fixed and mobile WSNs has been investi-gated with simulations [86–89, 186, 187]. Zhou et al. introduce different causes of radioirregularity [25] and show that link asymmetry caused by fading does not have a remarkableimpact on performance of the AODV routing protocol. This is associated with multi-rounddiscovery phase nature of the protocol, i.e., a new route is found during the next round ofroute discovery phase. Effect of shadowing on end-to-end connectivity has also been stud-ied [188, 189]. Further, in link level studies, Rajagopalan et al. [188] concluded that highershadowing variance increases link connectivity, however this is attributed to shadowing in-dependence assumption between links. Whereas Bestseller and Hartmann [189] have takenshadowing correlation into account and studied impact of shadowing on connectivity ofmulti-hop randomly deployed WSNs showing that higher shadowing variance still increasesthe link connectivity. There is also a large number of works analytically evaluating the effectof fading, shadowing and different communication coverage models on network throughput,or end-to-end connectivity [188–191].Our work is similar to [189, 191] in the sense that it is based on connectivity forWSNs in lognormal shadowing environment however directional path loss component is the905.1. Introductiondominant feature in our study. Further, in previous works, connectivity of sensor nodesis derived based on assumptions which may not be valid for particular environments, e.g.,orchards, warehouse or libraries. Moreover in these works, either power-law (disk-shapecoverage model) or isotropic log-distance attenuation models have been deployed to studyconnectivity in WSNs. However in artificial man-made row-like environments, path loss mayhave directional components. Directional component of path loss in these environments hasnot been characterized and its impact on routing protocols has not been studied.In this work, first we show directional path loss is a real phenomenon by measuringit in a realistic environment. Further, we show existence of directional path loss in thefarm environments and particularly apple orchards. We proceed to show that its impacton performance metrics of AODV routing protocol such as network lifetime, and averagenumber of hops packets travel is remarkable. Note that average number of hops is anindication of latency and energy consumption in the network. This is a different approachfrom works in precision agriculture context that have studied node placement and its effecton connectivity [75, 76]. In [75], Liu et al. have compared connectivity of deterministicdeployment patterns inside a wheat field during different growing seasons. Even thoughpath loss exponent is characterized for seeding, booting, and jointing stages, both shadowingeffect and path loss directionality have been dismissed. Ndzi et al. [76] have characterizedpath loss inside a mixed crop farmland based on measurements conducted along the rows indifferent sections of the farm and have derived components of power-law attenuation modelfor each crop type. Dependence of connectivity on crop type is mentioned however moremeasurements for each specific crop type and land geometry is required prior to crop-basedevaluation of higher communication layers.We use simulations to show that directional path loss limits the number of nodeseach node connects to, so-called mean node connectivity in the network. Afterwards weshow that decreased mean connectivity results in increased hop count and shorter networklifetime. As a mitigation strategy, we suggest alternative node placements by narrowingdown and widening the inter-node distances along the directions which experience higherand lower impairment respectively as a result of directional path loss. Contribution of thiswork is twofold:• Firstly, we choose an apple orchard as an example of realistic environments which aremade up of rows of similar aligned objects to show existence of directional path loss byour measurement campaigns. Further we show that its impact on the performance ofAODV routing protocols, e.g., network lifetime and latency under conventional node915.2. Conceptsplacements is real and measurable.• Secondly, we generalize the path loss model derived from our measurements in agricul-tural fields to directional path loss associated with the environments which are similarto apple orchards in terms of geometry and study its effect on AODV routing proto-cols. Further, we show that directional path loss decreases network lifetime in additionto increasing mean hop count by decreasing mean connectivity in the network.The remainder of this chapter is organized as follows: In Section 5.2, we explain networkperformance metrics, conventional deterministic node placements, AODV routing protocolsand how their performance is affected by directional path loss. In Section 5.3, we explain ourmeasurement campaign in the Dawson apple orchard, general directional path loss modelscorresponding to similar environments followed by results and conclusion in Sections 5.4 and5.5 respectively.5.2 ConceptsAs mentioned in Section 5.1 and as we will show in Sections 5.3 and 5.4 directional path lossis likely to be encountered in many practical scenarios including precision agriculture. In thissection, we first explain basic definitions regarding performance of routing protocols thenwill proceed to explain basics of AODV protocols and how directional path loss affects theestablished routes. Finally we will explain how this translates to energy efficiency, networklifetime and latency in the network.5.2.1 Review of Conventional Node Placement Strategies for WSNsRegular deterministic node placement is the most common technique used for precisionagriculture applications [75, 76] and similar man-made environments. Further, even thoughrandom deployment strategies are well-suited for applications such as reconnaissance mis-sion during combat or forest fire detection, deterministic node placements are well-poisedto address man-made symmetric environments. The most popular deterministic node ar-rangements are square, triangular and hexagonal tessellations depicted in Figure 5.1. Theinternode distance d0 and number of nodes for a specific internode distance and fieldarea A are tabulated in Table 5.1. Precision agriculture applications are diverse in termsof node density requirements since different sampling distances are demanded by each ap-plication. For instance, as stated in Chapter 4, applications such as soil moisture mon-925.2. Conceptsitoring for irrigation or electrical conductivity require high density deployment (≈ 50-100 nodes/ha) [176, 177], whereas pest management or pH monitoring require much sparserdeployments (≈ 3-8 nodes/ha) [178, 179].Figure 5.1: Different regular topologies; square, triangular and hexagonal networksTable 5.1: Parameters for different tessellations corresponding to a WSN with N nodes andinter-node distance d0 deployed in a field with Area ATiling Triangle Square Hexagond0 ≈ 1.07√AN≈√AN≈ 0.88√ANNe ≈ 1.15 Ad20 ≈Ad20≈ 0.77 Ad205.2.2 Basic DefinitionsIn this section, we define network lifetime and mean hop count as two important performancemetrics of routing protocol. As stated in Section 5.1, mean hop count is a measure for energyconsumption and latency in the network due to the linear relationship between them. Wealso define link connectivity and end-to-end route connectivity since they form the basis forroute discovery phase and communication phase of AODV routing protocols.Network Lifetime: As mentioned in Chapter 2, various network lifetime definitions areproposed in the WSN context [102] with each network lifetime fitting best for a differentapplication. In this work since we do not make any specific assumption regarding theapplication and due to structure of the network which consists of a gateway in the corner935.2. Conceptsof the field, percentage of nodes that have a path to BS is defined as the network lifetimemeasure. To be more specific, we define network lifetime as the duration after which thereis no path between any node and the gateway.Mean Hopcount: We define this metric as the average number of hops a packet takesin order to reach the destination given that transmission is successful [192]. This is animportant metric since it provides a measure to identify length of the reliable routes in thenetwork. Besides, it is linearly related to end-to-end delay and aggregate energy consumptionin the network.Link Connectivity: Link connectivity is the probability of signal power remaining abovea detectable threshold γ over the link between a transmitting and receiving node. Forlog-distance ettenuation model, path loss βLD(dB) is expressed byβLD(dB) = β0 + 10α log10(dd0) +Xσ, (5.1)where α denotes path loss exponent, β0 represents path loss at reference distance d0 andXσ accounts for shadowing which is a zero-mean Gaussian random variable with standarddeviation σ, N(0, σ). Let Li represent the event that i-th link exists with di denoting lengthof the link. Let us assume β1 and β2 are deterministic and stochastic parts of the path lossrespectively, i.e., β1 is the path loss mean and β2 accounts for shadowing and is a zero-meanGaussian random variable with standard deviation σ. Link connectivity for i-th link Li isdenoted byP(Li∣∣di) = P (β(i) ≤ βth∣∣di)=∫ βth−β1−∞fβ2(β2)dβ2,(5.2)where f(·) denotes probability distribution function (PDF). Consequently (5.2) yieldsP(Li∣∣di) = 12− 12erf( 10α√2σlog10didref), (5.3)wherer0 = 10βthα10dB m, (5.4)945.2. Conceptsis the maximum distance which guarantees availability of i-th link when σ = 0 or for achannel with power-law attenuation function Pr(j) = Pt(i)d−α and erf(·) represents theerror function.End-to-end Route Connectivity: End-to-end route connectivity is the probability thata specific route between source and gateway nodes is up [188]. This definition is useful in thesense that there is usually one gateway in the corner of the farm which collects packets sentby sensing source nodes scattered inside the field. Let us assume there are n hops betweena source node and the sink. In case link connectivity over the link arriving at j-th hop isdenoted by P(j)h , end-to-end route connectivity for i-th route, CRi , is calculated byCRi =n∏j=1P(j)h . (5.5)Note that link connectivity P(j)h is a function of path loss model.Mean Node Connectivity: Mean node connectivity, Ci is average number of nodes eachnode can connect to. Let P(i)j denote link connectivity between j-th and i-th nodes. Nodeconnectivity for i-th node is then calculated by Ci =∑j∈S P(i)j , where S represents set ofall sensors in the network.5.2.3 AODV Routing and Its Performance Under Directional Path LossIn this part, first we briefly explain how AODV routing protocol performs and then basedon the metrics defined in previous section we will use an example to clarify how directionalpath loss may affect the resulted routes in addition to energy efficiency and network lifetimethereof.AODV Routing Protocol: AODV-based protocols are important since they form ba-sis for multi-hop networking deployed on IEEE802.15.4 COTS modules in WSNs. In thefollowing we explain the three main phases in AODV [193]:Route Discovery Phase: Source node originates a RREQ packet which floods throughthe entire network via multi-hop routing to reach the gateway. Each node adds its own IDto the path list in RREQ and forwards it to its neighbours, while RREQ is discarded in caseits travelled path is longer than that of the previous received RREQ packet. Gateway will955.2. Conceptssubsequently send a RREP packet over the shortest hop route and makes each node awareof its next hop node.Communication Phase: Nodes start to send data based on the assigned routes.Route Maintenance Phase: Hello message is broadcast by node A so that a neighbour-ing node B would update its entries for which, node B is the next hop to node A. In case,Hello message or regular messages from node A are not received for a specific period of time,route discovery phase will start again so that new reliable routes are established.Effect of Path Loss Model on Performance Metrics of WSNsAs explained in Section 5.2.2, link and route connectivity are functions of path loss model.As stated in Section 5.2.3, for a certain route between a source and the gateway to bechosen, a RREQ packets is required to travel the route up to the gateway and RREP packetis required to return back to the source.In the following, through a simple example we explain how end-to-end route connec-tivities and consequently performance metrics of AODV protocols change under directionalpath loss assumptions,Example: We clarify the problem with a very simple example. Consider the simple net-work illustrated in Figure 5.2 with two routes R1 and R2 being available between sourcenode (S) and gateway (G). Assume that end-to-end route connectivities C1 and C2 arederived based on two different path loss models in terms of directivity degrees so calledscenarios 1 and 2. For instance, scenario 1 may represent a situation where directivity ismore severe than in scenario 2. This is because even though end-to-end route is longer bothin terms of physical length and hop count, end-to-end connectivity is the same on routes R1and R2 whereas in scenario 2, R1 benefits from a much better connectivity.As explained in the beginning of this section, these metrics are important since inorder for a specific route to be assigned during the route discovery phase, RREQ and RREPpackets need to traverse the route successfully. Furthermore, as explained in Section 5.2.2,in fact C1 and C2 represent the end-to-end connectivity of routes R1 and R2 respectivelyand represent the probability of signal remaining above a threshold once transmitted fromone end of the route and received at the other end.965.2. ConceptsFigure 5.2: Connectivity graph of a simple network with two paths between source and the gatewayFor Synapse transceiver modules with amplifier efficiency η=0.2, electrical circuitrypower consumption Pelec=100 mW, reception power PRx=80 mW, packet length of 44 bytes,l1=3, l2=5 and assumption of nodes transmitting at full transmit power 15 dBm, networkperformance metrics are tabulated in Table 5.2. As seen in this table and as it is easilycalculable, around 30% saving in terms of energy consumption is achieved.Table 5.2: Performance of the AODV protocol under two different scenarios for the simple networkconnectivity graph illustrated in Figure 5.2❵❵❵❵❵❵❵❵❵❵❵❵❵❵ScenariosPerformanceAverage energy (µJbit) PDR (%) Average number of hopsScenario 1 5.37 65 3.37Scenario 2 3.83 94 35.2.4 Alternative Node Placement StrategiesAs explained in Section 5.2.1, deterministic regular patterns are the most common nodeplacements used for WSNs in man-made environments such as precision agriculture. How-ever depending on different design objectives such as coverage, connectivity, network lifetimeand data fidelity and constraints such as number of nodes, transmit power among others,alternative node placement techniques have been proposed [8, 194]. In this work, in order975.3. Methodologyto increase node connectivity along directions of interest under directional path loss cir-cumstances, we introduce elongated grid placement technique which includes increasing anddecreasing internode distance along least and most impaired directions while keeping nodedensity fixed. Further, we introduce a measure called elongation index, ωd0 , as a multiplica-tive factor for changing internode distance d0. Introduction of elongation index ωd0 to theregular square pattern demonstrated in Figure 5.1, multiplies internode distance along onedirection by ωd0 and the perpendicular direction by1ωd0so that node density, i.e., numberof nodes is kept intact. Similarly for triangular and hexagonal patterns, this translates toscaling the internode distances so that the area of the newly formed triangle and hexagonis kept fixed. In this work we only study grid square deployment however its extension toother regular patterns is straightforward. Our purpose from this technique is to make nodeconnectivity along different directions more uniform, therefore increase node connectivityalong directions that result in lower hop count towards gateway. The effect of such a schemeon realistic directional path loss scenarios will be simulated in Section 5.4.3.5.3 MethodologyIn this part, first in Section 5.3.1 we explain our measurement campaign in the Dawsonorchard, Keremeos, BC which helps us observe directional path loss in agricultural environ-ments, particularly apple orchards. In Section 5.3.2, we explain how node connectivity isaffected by path loss model observed in agricultural environments since this model servesas a representative case study for similar man-made environments. Afterwards, inspired bythe directional path loss observed in this specific environment, in Section 5.3.1 we generalizethis model to encompass similar environments which are made up of similar objects alignedon side-by-side rows. We also introduce a metric so called directivity degree to represent thegeneral model introduced in this section. Finally in Section 5.3.3, we explain the deploymentscenarios and simulation assumptions which underlie the results explained in Section 5.4.5.3.1 Observations of Directional Path Loss in Precision AgricultureIn this section, we first explain management of high density apple orchards in terms ofrootstock type, tree density and between-row-spacing. We proceed with path loss modelsfor vegetated environments and measurement campaign.985.3. MethodologyManagement of High Density Apple Orchards: Any orchard with more than 150 trees/acreis considered high density. There are various ways high density apple orchards are managedin terms of rootstocks and training system [195–197]. Rootstock type determines tree height,while training system is decisive in terms of number of trees per acre defined by in-row andbetween-row-spacing. The majority of rootstocks used in Similkameen valley, BC are M9and B9 which are medium in terms of height, 2.5-3 m. Training systems, on the other hand,are categorized into vertical axis (550-900 trees/acre), slender spindle (700-1500 trees/acre),and super spindle (2000-5000 trees/acre). Vertical axis, and slender spindle with between-row-spacing of 13 ft-15 ft and 10 ft-12 ft respectively, are very popular in the region. In-rowspacing for vertical axis is 4-6 ft, whereas 3-5 ft is required for slender spindle management.Path Loss Models for Vegetated Environments: As explained in Chapter 4, draw-back of existing models for vegetated environments is that they only account for the veg-etation path loss. Further, there are more factors such as ground and canopy reflectioncontributing to path loss which make the aforementioned models unable to make a goodprediction of path loss in realistic environments. Besides, modified models that take groundand canopy reflection into account have been proposed however are more complex since theyinclude summation of multiple terms to take ground and canopy reflection into account [166].In order to address this issue, log-distance model is proposed since it encompasses effects ofall contributing factors and propagation mechanisms [75, 167–169].Measurement Campaign: We carried out our measurements in Dawson orchards atKeremeos, Similkameen valley, BC, the majority of which is under vertical axis trainingsystem. Measurements were done in two 15 acre (ac) orchards consisting of apple tree rowswhich are considered high density in terms of vegetation with tree rows being approximately4.5 m/15 ft apart from each other. We did our measurements along five directions of along,across, 30◦, 45◦, and 60◦ with respect to tree rows, using different transmitter and receiverantenna heights. The measurements were conducted throughout three different measurementcampaigns, seven days combined and spread across two summer seasons.We did the measurements in approximate range of 0-100 m at points which are ap-proximately 10 m apart from each other in 9 different parts of the orchard with scenarioshaving been illustrated in Figure 5.3. Our equipment on the transmitter side, are an AgilentE8267D VSG feeding a 2.45 GHz omnidirectional dipole antenna with 5 multi-tones (5 MHzapart from each other) through a ZVA-213 power amplifier which provides +23 dBm asthe antenna input. On the receiver side, a Toshiba laptop which runs MATLAB and Agi-995.3. Methodologylent connection expert, specialized proprietary software for connecting computer to Agilentspectrum analyzer, is connected to a N9342C HSA via a LAN cable. Extra losses and gainsresulted from cables, connectors and antennas at both Tx and Rx sides are taken into ac-count for calibration. Using the explained setup, we were able to capture path loss up to(a) (b)Figure 5.3: 9 measurement scenarios inside the orchard is illustrated; Transmitter antenna wasmoved 50 m across the rows to form a new scenario whereas Rx was moved along five differentdirections of along, cross, 30◦, 45◦ and 60◦ for each scenario, with path loss samples being collectedfrom 0-100 m range and at ≈10 m apart points≈ 115 dB which is suitable for our study case since attenuation is fairly high for throughvegetation propagation and the amount of path loss IEEE802.15.4 compliant modules suchas synapse transceivers tolerate is limited to at most 115 dB [183] based on their maximumtransmit power level and sensitivity. Path loss samples collected during our measurementcampaigns are illustrated in Figure 5.6. Path loss along the crass track link, appears to behigher than other directions, whereas rotation of links towards the along track lowers pathloss. Path loss behaviour characteristics along different directions is tabulated in Table 5.4.Note that path loss exponent α is maximum for cross track links where signal propagatesthrough the most number of tree rows, while along track link shows the minimum path lossexponent which could intuitively be associated with waveguide characteristics of along trackrows. In Section 5.4, we will show log-distance path loss mode provides a good fit to datacompared to popular existing path loss models. Coefficient of determination, R2, indicates1005.3. Methodologyhow well observed outcomes are replicated by the model. The closer R2 gets to one, thebetter the variability in data is captured by the model.5.3.2 Representative Path Loss Model and Directivity DegreeBased on our measurement campaign results, path loss exponent increases as number of treerows through which the signal propagates rises. Further our extensive measurements showthat path loss inside apple orchards is directional, i.e., signal attenuation is higher over thepaths which are oriented diagonally or cross-wise with respect to tree rows compared tolinks that are extended along these rows. Moreover, path loss exponent in the log-normalshadowing model increases as angle between the tree rows and wireless link gets closer to 90◦.As a generalization to the path loss model observed in the farm and in order to representsimilar environments, we define a parameter so-called directivity degree, Dα as the ratio oftransmission range along the least to the most impaired direction when there is no shadowingpresent. This is a suitable measure since shadowing is not a dominant feature in agriculturalfields and large static WSNs with similar structure. A new path loss model is created bymultiplying path loss exponents α corresponding to different directions derived from ourmeasurement campaign with a fixed number, ωα, which is greater than one while only alongtrack path loss exponent is kept fixed. Obviously Dα would increase as this multiplicativeconstant increases. Note that in order to be focused on the impact of directional path loss,i.e., not shadowing, we calibrate shadowing effect so that it is the same along all directionsand in all scenarios.As discussed in management of high density apple orchards in Section 5.3.1, between-tree-row spacing varies from 10 ft to 15 ft depending on the adopted type of training system.As mentioned in Section 5.3.1, our measurement campaign was conducted in a high densityapple orchard where the spacing was relatively high, i.e., 15 ft. Therefore, we refer todirectivity associated with Dawson orchard as low directivity degree (LDD), Dα ≈ 2, whilethe directivity corresponding to smaller between-row-spacing as in slender spindle trainingsystem is referred to as high directivity degree (HDD) with Dα ≈ 3. In Figure 5.4, wehave illustrated a schematic view of no shadowing transmission range, r0, along differentdirections in the orchard. In Section 5.4, we will study effects of the representative path lossmodels with 1 < Dα < 5.Effect of Directional Path Loss on Node Connectivity: As discussed in Section 5.2.2,node connectivity results from adding up connectivity of links that emanate the node. There-1015.3. Methodology 100 200 302106024090270120300150330180 0 Dα=1Dα=2.2Dα=3.4Dα=4.5Dα=5.6Figure 5.4: No shadowing transmission range, r0, for different scenarios is illustrated; Along tracktransmission range is the same for all directional path loss scenarios scenarios since in-row pathloss is assumed to be kept intact for different scenarios. Dα = 1 represents directional path lossand other scenarios correspond to ωα = 1, ωα = 1.2, ωα = 1.4 and ωα = 1.6.fore, directional path loss that is resulted from degradation of links in different directions,i.e., increasing path loss exponent in log-distance path loss model, would decrease connec-tivity of nodes. In Figure 5.5, a schematic view of directional path loss impact on nodeconnectivity is illustrated, however we are going to simulate this in Section 5.4. Conse-quently the effect of node connectivity on hop count and WSN lifetime for AODV-basedrouting protocol will also be studied.5.3.3 Deployment Scenarios and Performance MetricsAs discussed in Section 5.2.4, deterministic grid deployment is the most common node place-ment strategy used in precision agriculture. Therefore, we choose square grid pattern as ourchosen deployment scheme. Mean hop count is a measure for average energy consumptionand latency in the network, while network lifetime as defined in Section 5.2.2, i.e., the dura-tion after which all nodes get disconnected from gateway, serve as the performance metrics.MAC Layer: As frequent for precision agriculture applications, TDMA MAC underliesthe deployed networking protocol. Further, we assume no retransmission occurs due to1025.3. MethodologyFigure 5.5: Effect of path loss directivity degree on node connectivity is illustrated; Coverage alongall directions except for along track has got limited as a result of increased path loss exponent anddecreased r0 in (5.4) which results in decreased node connectivity for Scollision or congestion in the network. Therefore, retransmissions happen because of linkfailures as a result of shadowing or signal falling below a specific threshold level. In thiswork, we neglect MAC layer energy consumption since our study is focused on the routingprotocol performance. Simulation setup parameters are included in Table 5.3.Simulation Setup: We tabulated the simulation parameters in Table 5.3. We use MAT-LAB to simulate the effects of directional path loss on square grid deployment and elongatedgrid with elongation indices applied. At each time instance a new connectivity graph is madebased on path loss models discussed in Section 5.3.2, tabulated in Table 5.3 and the packet isassumed to go through a single link in case the received power is above the reception thresh-old. For the route discovery phase, as soon as a source node is decided, all the alternativeroutes from the node to gateway are simulated accordingly in order to select those alongwhich RREQ and RREP packets have traversed successfully. Consequently the route withthe shortest hop count is selected from these routes which is the AODV routing protocolcharacteristics.Communication then starts between the designated node and the gateway along thisselected route which is held unless a packet drops. In the event of packet drops, source node1035.4. ResultsTable 5.3: Simulation ParametersParameter ValueTopologysquare with differentelongation indices ωd0Topological area 700 × 700 m2Node density (node/ha) 4Wireless channellog-normal shadowingwith 1 < Dalpha < 6and σ = 2 dBTransmit power +15 dBmRadio model Synapse RF 200Center frequency 2.45 GHzData rate 250 kbit/sData delivery model query-basedInitial sensors energy 40 µJGateway location Far right end of the fieldwould be notified and route maintenance phase will start as discussed in Section 5.2.3.5.4 ResultsIn this section we first show the outcome of our measurement campaigns in the apple orchardsat Keremeos, BC which shows directional path loss is a real phenomenon. Afterwards wego on with studying the effect of such directivity on node connectivity and network lifetimethereof.5.4.1 Observation of Directional Path Loss in Precision AgricultureIn Section 5.3.1, we elaborated our measurement campaign in the Dawson orchards as anexample for row-like environments, i.e., man-made environments made up of similar objectsaligned in side by side rows. We also explained representative path loss models for vegetatedenvironments in Section 5.3.1. In Table 5.5, we show that log-distance path loss modelprovides a good fit to collected data in the Dawson orchard, while Table 5.4 shows path losscharacteristics along different directions. In Figure 5.7, link connectivity for different typesof links in terms of direction is illustrated. Link connectivity decreases as the wireless linkpasses through more number of tree rows.1045.4. Results10 16 26 40 64 100 159−120−110−100−90−80−70−60Distance [m]Path Gain [dB]Path loss comparison along different directions Along60°45°30°CrossFigure 5.6: Path loss comparison between along, cross, 30◦, 45◦, and 60◦ directions; Cross trackshows a higher slope followed by 30◦, 45◦, 60◦ and along track directions.60 70 80 90 100 110 1200.20.40.60.81Connectivity comparison between different types of linksDistance [m]Linkconnectivity(%) Along60°45°30°CrossIsotropic path lossFigure 5.7: Connectivity for different types of links is illustrated; Synapse transceiver moduleassumptions for transmit power and sensitivity level have been taken into account. It could be seenthat most diagonal track links perform worse than the link which corresponds to isotropic path lossmodel1055.4. ResultsTable 5.4: Path loss characteristics along different directions in the Dawson apple orchardsDirection β0 α σ 95% CI for β0 95% CI for αAlong 74 3.12 3.65 70-76 2.94-3.3Cross 73 4.25 4.45 67-77 3.91-4.5930◦ 76 3.92 2.58 73-81 3.62-4.2145◦ 76 3.70 3.15 72-82 3.34-4.0660◦ 75 3.49 2.79 71-81 3.17-3.81Isotropic path loss model 75 3.61 5.67 71-79 3.36-3.86Table 5.5: (R2,RMSE) for different variants of MED models, modified MED models based on [166]to take the canopy and ground reflection into account as well.❤❤❤❤❤❤❤❤❤❤❤❤❤ModelTrack directionAlong Cross 30◦ 45◦ 60◦ Isotropic path loss modelWeissberger (0.67,6.85) (0.41,9.74) (-4.17,21.95) (-2.32,16.47) (-1.23,12.2) (-0.3,14.01)ITU-R (0.43,9.04) (0.72,6.76) (-2.65,18.43) (-1.02,12.83) (-0.02,8.25) (0.03,12.08)FITU-R (0.81,5.16) (0.73,6.57) (-1.8,16.14) (-0.5,11.06) (0.12,7.67) (0.3,10.29)COST235 (-2.15,21.25) (-0.38,14.93) (0.92,2.71) (0.4,7) (-0.91,11.27) (-0.58,15.43)Log-distance model (0.9,3.65) (0.87,4.45) (0.92,3.92) (0.4,3.7) (0.9,3.49) (0.75,5.67)6 8 10 12 14 166810121416ConnectivityHopcounthopcount and connectivity behaviour with 6 different directivity indicesFigure 5.8: Behaviour of mean hop count with respect to mean node connectivity is illustrated;4 simulations have been run for each directivity degree scenario5.4.2 Effect of Directional Path Loss on Node ConnectivityIn Section 5.3.2, we used a schematic figure to discuss how directional path loss affects nodeconnectivity in the network. In this section, we use simulations to show effect of directional1065.4. Results6 8 10 12 14 16120140160180200220240260Node connectivityLifetime (rounds)lifetime vs connectivity with 6 different directivity indicesFigure 5.9: Behaviour of network lifetime with respect to mean node connectivity resulted fromvarious path loss directivity degrees is shown.path loss on mean node connectivity and the manner in which network lifetime and meanhop count are affected by directional path loss for the simulation scenario shown in Table 5.3.In Figure 5.10, effect of directivity degree Dα, i.e., measure of directional path loss, on meannode connectivity. Figures 5.8 and 5.9 show effect of node connectivity on mean hop countand lifetime respectively. As illustrated in Figure 5.8, mean hop count for a packet travellingbetween a source and gateway drops linearly as mean node connectivity grows. In Figure 5.9,lifetime in terms of rounds with respect to mean node connectivity is depicted. As can beseen, the relationship between these two performance metrics is close to linear.5.4.3 Mitigation StrategiesAs explained in Section 5.2.4, different alternative node placement schemes have been pro-posed to meet various design objectives for WSNs. In this work we opt for a simple alter-native node placement identified by elongation index ωd0 to combat impairments caused bydirectional path loss in row like man-made environments. Our purpose is to mimic the be-haviour of non-directional path loss in the sense that neighbouring nodes surround each nodein a more uniform manner along different directions. In Figure 5.11, behaviour of mean hopcount and network lifetime for different elongation indices and for three different directivitydegrees, Dα, is illustrated. These Dα values correspond to three realistic scenarios explained1075.4. Results1 2.2 3.4 4.5 5.6 6.778910111213141516Directivity degreeNode connectivityNode connectivity and directivity degree Figure 5.10: Behaviour of mean node connectivity with respect to directivity degree is illustrated;4 simulations have been run for each directivity degree.0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 245678910111213elongation indexMean hop countMean hop count behaviour with respect to elongation index Dα=1Dα=2.2Dα=3.4(a) Mean hop count and elongation index0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2160180200220240260280300elongation indexLifetime (rounds)Network lifetime behaviour with respect to elongation index Dα=1Dα=2.2Dα=3.4(b) Network lifetime and elongation indexFigure 5.11: Behaviour of network performance metrics with respect to elongation index, ωd0 , forisotropic and two directional path loss scenarios which are common in high density apple orchardsis illustrated1085.5. Discussionin Section 5.3.2, where Dα = 1 corresponds to isotropic path loss, while Dα ≈ 2 and Dα ≈ 3correspond to high density apple orchards with larger and smaller between-tree-row spacingas explained in Section 5.3.1. As could be seen effect of elongated grid on higher directivitydegree scenarios is higher since node connectivity along cross track and diagonal directionsis very limited. The proposed alternative node placement technique, increases number ofneighbouring nodes along other directions apart from along track which results in lower hopcount and also network lifetime since it takes longer for network graph node groups to be-come disconnected. As seen in Figure 5.11b, elongated grid with ωd0 = 0.8 results in ≈ 5%Figure 5.12: Approximate applicability range of the proposed mitigation strategy; Shaded regionshows the range where elongated grid outperforms square grid for different directivity degrees inthe studied scenariolifetime improvement for Dα ≈ 2, while ωd0 = 0.6 yields ≈ 15% lifetime improvement forDα ≈ 3. In Figure 5.12, applicability range of the proposed mitigation strategy is illustratedwith the shaded region. The shaded region shows the approximate area where elongatedgrid outperforms square grid in terms of network lifetime. Figures 5.11b, and 5.12 showthat higher range of elongation indices are applicable to higher directivity degrees, whereasmore lifetime improvement compared to square grid is possible given that elongation indexis appropriately chosen.5.5 DiscussionIn this work, we first showed that directional path loss is a real phenomenon which happensin realistic man-made environments such as warehouses, libraries or agricultural environ-ments. Further, we characterized directional path loss with a measure called directivitydegree and showed that effect of this phenomenon on performance metrics of WSNs such1095.5. Discussionas network lifetime and mean hop count which translates to latency and energy efficiencyis measurable. Our simulations showed that directional path loss decreases network lifetimeand increases mean packet hop count by decreasing node connectivity. As a mitigationstrategy we suggested elongated grid deployment, i.e., decreasing internode distances alongimpaired directions, to increase node connectivity along various directions, therefore im-proving network lifetime. This technique in fact mimics behaviour of isotropic path lossby distributing neighbouring nodes in a more uniform way along different directions whichhelps network achieve higher lifetime as a result of higher time it takes network graph tobecome disconnected.The limitation of this node placement technique is its sub-optimality since patternof the grid, i.e., square in addition to its density is kept intact. Further, more complexnode placement techniques with irregular patterns, increasing node density surrounding thegateway or adding gateways to other corners of the field may result in better enhancementsin network performance. In addition to node placement strategies, geographical routing, i.e.,forwarding packets along certain directions, and transmit power control would help achievemore energy efficiency.It is noteworthy that the mitigation strategy proposed in this chapter, is suitable forlow shadowing environments with organized geometrical structure. As a practice for futureresearch, characterizing directional path loss in the environments that experience heavyshadow fading and proposing mitigation strategies to combat such impairments in order toincrease network lifetime is fundamental.110Chapter 6Conclusions and RecommendationsIn this chapter, we conclude the thesis with: 1) Conclusions regarding the effectiveness of ourproposed schemes, the limitations of our algorithm and the implications for current researchpractice, and 2) recommendations for future research that could overcome the limitations ofour work.6.1 ConclusionsFew previous studies have sought to assess the impact of propagation impairments on higherlayer protocols and algorithms and have devised schemes for mitigating such impacts. Here,we have presented four case studies that demonstrate how higher layer protocols and algo-rithms can be devised to achieve greater energy efficiency by accounting for the nature ofthe propagation impairments experienced in two radically different environments; WBANsand PAWSNs. In this chapter, first we review the effectiveness of our proposed schemes, therelationships between the design and performance parameters that we investigated, and theimplications for current practice or future research. In Section 6.2, we discuss limitations ofthe work reported in our work and possible methods for overcoming them.In Chapter 2, we proposed a routing protocol that uses linear programming techniquesto ensure that all nodes in a WBAN expend energy at a similar rate and thereby maxi-mize network lifetime. Moreover, in the existing protocols, communication overhead causedby frequent link assessments and computation burden imposed by routing table calculationmake existing link-state routing protocols unsuitable for dynamic WBANs. We overcomethese by: 1) monitoring RSSI in a dynamic and distributed manner on data packets com-municated over links, therefore changing the transmit power levels only when large RSSIvariations is observed 2) only having limb-torso links participate in link assessment processsince RSSI variations over limb-limb or torso-torso links is not remarkable in terms of therequired transmit power level, 3) using linear programming to derive link likelihoods.The algorithm is well-suited to maximize WBAN lifetime, and address connectivity1116.1. Conclusionsfor monitoring applications and mobility model which involves stationary postures and ac-tions in the context of routine daily activities. Even though the algorithm is proposed forWBANs, the LP-based link likelihood assignment proposed in this chapter can be used inconjunction with other transmit power adjustment techniques to maximize IEEE802.15.4network lifetime for other types of WSNs. The algorithm is particularly useful in future im-plementations of WBANs, as low listening power COTS are emerging, therefore multi-hopnetworking in WBANs will become more beneficial in terms of energy conservation. As faras lifetime maximization is concerned, the work in Chapter 2 applies to WBANs which arebuilt upon IEEE802.15.4 MAC layer. As a future practice, deriving lifetime maximizationLP for other standards, e.g., IEEE802.15.6, would be very useful because as opposed toIEEE802.15.4, IEEE802.15.6 only supports one and two hop star networks.In Chapter 3, we proposed a scheduling algorithm that accounts for the periodic shad-owing observed over many WBAN links and thereby reduce the transmit power required totransfer information and thereby increase energy efficiency. This technique helps us achievesingle hop communication by adopting low transmit power levels over some limb-torso linksthat experience severe shadowing, however show periodic connectivity as opposed to sta-tionary actions studied in Chapter 2. Further, periodic prolonged actions such as fitnessactivities cause on-body links to undergo periodic predictable connectivity sessions that canbe exploited for low power single hop communications at the expense of latency. The en-ergy efficiency is achieved by avoiding multi hop nature of store and forward schedulingtechniques and excessive energy expenditure caused by idle listening and channel sensingin opportunistic scheduling algorithms. Furthermore, the periodicity and predictability ob-served in on-body links can be exploited in opportunistic scheduling techniques to reducebeacon transfers required for channel sensing. The proposed technique is particularly suitedto increase energy efficiency for delay tolerant applications such as ambient assisted livingthat can tolerate latency because data can be logged and analyzed in an offline manner.Beside periodicity which can be used for energy efficient communication, diversity of RSSIsamples over such links provides us with mean and standard deviation features which makessimple real-time action recognition based on naive Bayes classification possible.One of the most important implications of this work in terms of node placement is thatsensors with looser placement and latency requirements can be mounted on extremities, e.g.,ankles and wrists, so that energy efficiency is achieved by single hop communication andlow transmit power levels. The most fundamental future research subjects is to devise nodeplacement and scheduling techniques in order to maximize throughput with low transmit1126.1. Conclusionspower levels for scenarios, where several periodic links are available. Moreover in this workas a case study, we studied energy efficiency and achievable bandwidth for a single link.However, in real world scenarios many nodes with looser placement requirements may beavailable.In Chapter 4, we proposed an efficient localization algorithm based on the Bayesianmodel for information aggregation. Moreover, existing Bayesian distributed techniques suf-fer from communication overhead required for setup phase in order to form loop-free graphs.While, non-Bayesian techniques are burdened with excessive communication overhead re-sulted from coupled variables, remarkable computational complexity needed to solve opti-mization problems at each iteration and generally suffer from slow convergence. Our scalableRSSI-based localization algorithm overcomes these limitations by: 1) using only local dis-tance estimates with respect to neighbouring nodes, and 2) using a message passing schedulewhich benefits from a fixed size outgoing message that does not grow with number of neigh-bouring nodes, and 3) low computational complexity per node at each iteration which onlygrows with grid size and only involves summations and multiplications.The algorithm uses a Bayesian model for information aggregation to achieve scalablecommunication and computational complexity with respect to the number of nodes at theexpense of accuracy. The proposed technique plays an important role in reducing energyexpenditure of PAWSNs, because the amount of data required to be exchanged for local-ization is comparable to the actual data exchanged in the network since in these types ofnetworks, sensors may only transmit very small amount of data, e.g., one byte per day.The main strength of our localization algorithm is its compatibility with realistic de-ployment scenarios of WSNs and the low communication overhead it adds to the alreadydeployed routing protocols. Further, the route discovery phase of AODV routing protocols,e.g., ZigBee and similar schemes, work based on flooding and multicasting RREQ packets.Therefore, our proposed localization algorithm can be integrated in a convenient and in-expensive manner, while remarkable amount of communication overhead is needed in casestate-of-the-art localization techniques are to be deployed. In this work, we exploited shad-owing independence over the links in the agricultural field to propose an algorithm withlow communication and computation complexity. However, there are real world scenariossuch as urban area where there might be a large correlation among shadowing observedover links. As a future work, a WSN compatible localization algorithm that could overcomesuch impairments and eliminate the message dependence and error propagation with lowcommunication and computation complexity would be very beneficial.1136.2. RecommendationsIn Chapter 5, we demonstrated that directional path loss is a real phenomenon whichhappens in realistic man-made and row-like environments such as warehouses, libraries oragricultural environments. Further, we showed that increase of directional path loss de-creases network lifetime and increases mean packet hop count by decreasing node con-nectivity along specific directions. As a mitigation strategy, we suggested elongated griddeployment, i.e., decreasing internode distances along impaired directions, to increase nodeconnectivity along various directions, therefore improving network lifetime.This technique in fact simulates the behaviour of non-directional path loss by dis-tributing neighbouring nodes in a more uniform way along different directions which helpsnetwork achieve higher lifetime as a result of higher time it takes network graph to becomedisconnected. The mitigation strategy proposed in Chapter 5, is well-suited to low shadow-ing environments with organized geometrical structure. As a future research, characterizingdirectional path loss in the environments that experience heavy shadow fading and propos-ing mitigation strategies to combat such impairments in order to increase network lifetimeis of huge interest.6.2 RecommendationsIn this section, we discuss the limitations of our work in the four research chapters inaddition to suggesting methods to overcome them. As a general recommendation, eventhough different techniques in PHY, MAC, and network layers have been proposed to makeWSNs more energy efficient, cross layer integration and design techniques help towards moreenergy consumption when dealing with application-based deployment of WSNs. A great dealof attention has been paid to integration of higher layers such as transport and applicationlayers into routing, scheduling and node placement techniques, however the impact of channelpropagation on these techniques is not much explored.In the routing technique proposed in Chapter 2, due to the limitations of TDMA-basedIEEE802.15.4 MAC which mandates all time slots to have equal duration, the proposedalgorithm may not be efficient in terms of bandwidth utilization. Therefore design of MACprotocols with dynamic time slot duration and variable time slots throughout a transferround helps towards more efficient utilization of bandwidth with higher number of sensorshaving been deployed. Data compression techniques can be used to reduce the time slotduration that is a fixed parameter of our algorithm, therefore cut down the idle listeningand electric circuit power consumption. It is beneficial to design a routing protocol that1146.2. Recommendationscan work based on contention-based IEEE802.15.4 MAC layer. Another limitation of thiswork is limited number of actions that have been used to evaluate the algorithm. Further,the action variation recognition technique proposed in this work needs to be tested on morevarious activities.In the scheduling technique proposed in Chapter 3, fixed pace and limited number ofactions is the main limitation of the work. Moreover, the work only serves as a proof ofconcept to achieved energy efficiency by using periodic limb-torso links. Action recognitionmay not work when actions pool gets bigger. As a remedy to this, periodic links and theirperiod should be recognized with link assessment techniques in the beginning of the actionrather than assuming that these links and their period is known once action is recognized.In the localization technique proposed in Chapter 4, the main limitation of the proposedalgorithm is its incapability in terms of achieving high precision localization. Further, as aremedy the proposed algorithm can be used as the initialization step for algorithms such asgradient descent which suffer from high sensitivity to initialization. Moreover the proposedBayesian model for information aggregation can be used to accelerate convergence of slowlyconverging gradient descent algorithms in addition to providing them with the initializedlocation for the scenarios with few number of landmarks and high number of nodes.In the directional path loss study and mitigation strategies conducted in Chapter 5,the limitation of this node placement technique is its sub-optimality since pattern of thegrid, i.e., square in addition to its density is kept intact. Further, more complex node place-ment techniques with irregular patterns, increasing node density surrounding the gatewayor adding gateways to other corners of the field result in better enhancements in networkperformance. In addition to node placement strategies, geographical routing, i.e., forward-ing packets along certain directions, and transmit power control would help achieve moreenergy efficiency.115References[1] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “A survey on sensornetworks,” IEEE Commun. Mag., vol. 40, pp. 102–114, Aug. 2002.[2] K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie, “Protocols for self-organization of awireless sensor network,” IEEE J. Pers. Commun., vol. 7, pp. 16–27, Oct. 2000.[3] V. Rajaravivarma, Y. Yang, and T. Yang, “An overview of Wireless Sensor Networkand applications,” in Proc. SSST, pp. 432–436, Mar. 2003.[4] C. Buratti, A. Conti, D. Dardari, and R. Verdone, “An overview on wireless sensornetworks technology and evolution,” Sensors, vol. 9, pp. 6869–6896, Aug. 2009.[5] K. Akkaya and M. Younis, “A survey on routing protocols for wireless sensor networks,”Ad Hoc Networks, vol. 3, no. 3, pp. 325–349, 2005.[6] J. Al-Karaki and A. Kamal, “Routing techniques in wireless sensor networks: a survey,”IEEE Wireless Commun., vol. 11, pp. 6–28, Dec. 2004.[7] I. Demirkol, C. Ersoy, and F. Alagoz, “MAC protocols for wireless sensor networks: asurvey,” IEEE Commun. Mag., vol. 44, pp. 115–121, Apr. 2006.[8] M. Younis and K. Akkaya, “Strategies and techniques for node placement in wirelesssensor networks: a survey,” Ad Hoc Netw., vol. 6, pp. 621–655, Jun. 2008.[9] N. Patwari, J. Ash, S. Kyperountas, A. Hero, R. Moses, and N. Correal, “Locating thenodes: cooperative localization in wireless sensor networks,” IEEE Signal ProcessingMag., vol. 22, pp. 54–69, Jul. 2005.[10] Y. Sankarasubramaniam, I. Akyildiz, and S. McLaughlin, “Energy efficiency basedpacket size optimization in wireless sensor networks,” in Proc. IEEE IWSNPA, pp. 1–8, 2003.116REFERENCES[11] “IEEE standard for telecommunications and information exchange between systems -LAN/MAN - specific requirements - part 15: Wireless medium access control (MAC)and physical layer (PHY) specifications for wireless personal area networks (WPANs),”IEEE Std 802.15.1-2002, pp. 1–473, Jun. 2002.[12] “Part 15.4:wireless medium access control (MAC) and physical layer (PHY) specifi-cations for low-rate wireless personal area networks (LR-WPANs),” IEEE approvedDraft Std P802.15.4, 2003.[13] I. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wireless sensor networks:a survey,” Computer Networks, vol. 38, no. 4, pp. 393–422, 2002.[14] D. Puccinelli and M. Haenggi, “Wireless sensor networks: applications and challengesof ubiquitous sensing,” IEEE Circuits Syst. Mag., vol. 5, no. 3, pp. 19–31, 2005.[15] B. Latré, B. Braem, I. Moerman, C. Blondia, and P. Demeester, “A survey on wirelessbody area networks,” Wireless Netw., vol. 17, pp. 1–18, Jan. 2011.[16] H. Cao, V. Leung, C. Chow, and H. Chan, “Enabling technologies for wireless bodyarea networks: A survey and outlook,” IEEE Commun. Mag., vol. 47, pp. 84–93, Dec.2009.[17] N. Wang, N. Zhang, and M. Wang, “Wireless sensors in agriculture and food industry-recent development and future perspective,” Comput. Electron. Agric., vol. 50, pp. 1–14, Jan. 2006.[18] P. Harrop and R. Das, “Wireless sensor networks (WSN) 2014-2024: Forecasts, tech-nologies, players,” 2014.[19] Frost and Sullivan, “Global wireless sensor networks market.” http://www.frost.com/sublib/display-report.do?id=N92B-01-00-00-00, 2014. Retrieved Aug. 2015.[20] M. Hatler, D. Guraganious, and C. Chi, “Wireless sensor networks (WSN) 2012-2022:Forecasts, technologies, players,” 2013.[21] U. Nations, “World population prospects, the 2010 revision.” http://www.un.org/en/development/desa/population/publications/pdf/trends/WPP2010/WPP2010_Volume-I_Comprehensive-Tables.pdf.117REFERENCES[22] H. Charles, J. Godfray, J. R. Beddington, and I. R. Crute, “Food security: The chal-lenge of feeding 9 billion people,” Sci. Mag., 2010.[23] “Precision farming market worth 4.80 billion USD by 2020.” http://www.marketsandmarkets.com/PressReleases/precision-farming.asp. Retrieved Jun.2016.[24] G. Anastasi, M. Conti, and M. Di Francesco, “A comprehensive analysis of the MACunreliability problem in IEEE 802.15.4 wireless sensor networks,” IEEE Trans. Ind.Inform., vol. 7, pp. 52–65, Feb. 2011.[25] G. Zhou, T. He, S. Krishnamurthy, and J. Stankovic, “Impact of radio irregularity onwireless sensor networks,” in Proc. MobiSys, pp. 125–138, 2004.[26] D. Kotz, C. Newport, and C. Elliott, “The mistaken axioms of wireless-network re-search,” Tech. Rep. TR2003-467, Jul. 2003.[27] S. Ullah, H. Higgins, B. Braem, B. Latre, C. Blondia, I. Moerman, S. Saleem, Z. Rah-man, and K. Kwak, “A comprehensive survey of wireless body area networks,” J. Med.Syst., vol. 36, pp. 1065–1094, Jun. 2012.[28] S. Movassaghi, M. Abolhasan, J. Lipman, D. Smith, and A. Jamalipour, “Wirelessbody area networks: A Survey,” IEEE Commun. Surveys Tuts., vol. 16, pp. 1658–1686, Mar. 2014.[29] M. Oliver, “An Overview of Geostatistics and Precision Agriculture,” in GeostatisticalApplications for Precision Agriculture, pp. 1–34, Springer Netherlands, 2010.[30] A. McBratney, B. Whelan, T. Ancev, and J. Bouma, “Future directions of precisionagriculture,” Precision Agriculture, vol. 6, pp. 7–23, Feb. 2005.[31] M. Anisi, “A survey of wireless sensor network approaches and their energy consump-tion for monitoring farm fields in precision agriculture,” Precision Agriculture, vol. 16,pp. 216–238, Apr. 2015.[32] “Wireless sensor networks see uptake in global industries due to technological break-throughs.” Frost & Sullivan, 2015.[33] z wavealliance, “About Z-Wave Technology.” http://z-wavealliance.org/about_z-wave_technology/. Retrieved Aug. 2015.118REFERENCES[34] E. Electric, “System engineering guidelines IEC 62591 WirelessHART.” http://www2.emersonprocess.com/siteadmincenter/PM%20Central%20Web%20Documents/EMR_WirelessHART_SysEngGuide.pdf, 2014. Retrieved Aug. 2015.[35] Z. Shelby and C. Bormann, “6LoWPAN: The wireless embedded Internet - Part 1:Why 6LoWPAN?.” http://www.eetimes.com/document.asp?doc_id=1278794, 2011.Retrieved Aug. 2015.[36] O. Puzanov, “Short-range wireless: Comparison of the key technologies,” Nov. 2013.[37] “ZigBee setting standards for energy-efficient control networks,” Tech. Rep.WP40110601EN-US, Schneider electric, Jun. 2011.[38] “Wireless - ISA 100.” http://www.smar.com/en/technical-article/wireless-isa-100, 2012. Retrieved Aug. 2015.[39] G. Fang and E. Dutkiewicz, “BodyMAC: Energy efficient TDMA-based MAC protocolfor wireless body area networks,” in Proc. ISCIT, pp. 1455–1459, 2009.[40] N. Timmons and W. Scanlon, “An adaptive energy efficient MAC protocol for themedical body area network,” in Proc. VITAE, pp. 587 –593, 2009.[41] A. El-Hoiydi and J. Decotignie, “WiseMAC: an ultra low power MAC protocol forthe downlink of infrastructure wireless sensor networks,” in Proc. ISCC, pp. 244–251,2004.[42] T. Watteyne, I. Augé-Blum, M. Dohler, and D. Barthel, “Anybody: a self-organizationprotocol for body area networks,” in Proc. ICST, pp. 1–7, 2007.[43] B. Culpepper, L. Dung, and M. Moh, “Design and analysis of Hybrid Indirect Trans-missions (HIT) for data gathering in wireless micro sensor networks,” in Proc. SIG-MOBILE Mob. Comput. Commun., pp. 61–83, 2004.[44] N. Javaid, Z. Abbas, M. Fareed, Z. Khan, and N. Alrajeh, “M-attempt: A new energy-efficient routing protocol for wireless body area sensor networks,” Procedia ComputerScience, vol. 19, pp. 224 – 231, 2013.[45] C. Oey and S. Moh, “A survey on temperature-aware routing protocols in wirelessbody sensor networks,” Sensors, vol. 13, pp. 9860–9877, Aug. 2013.119REFERENCES[46] A. G. Ruzzelli, R. Jurdak, G. M. O’Hare, and P. Van Der Stok, “Energy-efficientmulti-hop medical sensor networking,” in Proc. ACM SIGMOBILE, pp. 37–42, 2007.[47] B. Braem, B. Latre, I. Moerman, C. Blondia, and P. Demeester, “The wireless au-tonomous spanning tree protocol for multihop wireless body area networks,” in Proc.MobiQuitous- Workshops, pp. 1–8, 2006.[48] B. Latre, B. Braem, I. Moerman, C. Blondia, E. Reusens, W. Joseph, and P. De-meester, “A low-delay protocol for multihop wireless body area networks,” in Proc.MobiQuitous, pp. 1–8, Aug. 2007.[49] M. Quwaider and S. Biswas, “Probabilistic routing in on-body sensor networks withpostural disconnections,” in Proc. ACM Int. Symp. on MobiWAC, pp. 149–158, 2009.[50] S. Yang, J. Lu, F. Yang, L. Kong, W. Shu, and M. Wu, “Behavior-aware probabilisticrouting for wireless body area sensor networks,” in Proc. IEEE GLOBECOM, pp. 444–449, Dec. 2013.[51] A. Maskooki, C. Soh, E. Gunawan, and K. Low, “Opportunistic routing for body areanetwork,” in Proc. IEEE CCNC, pp. 237–241, Jan. 2011.[52] M. Nabi, T. Basten, M. Geilen, M. Blagojevic, and T. Hendriks, “A robust protocolstack for multi-hop wireless body area networks with transmit power adaptation,” inProc. BodyNets, pp. 77–83, 2010.[53] G. Tsouri, A. Prieto, and N. Argade, “On increasing network lifetime in body areanetworks using global routing with energy consumption balancing,” Sensors, vol. 12,pp. 13088–13108, Sep. 2012.[54] W. Heinzelman, A. Chandrakasan, and H. Balakrishnan, “Energy-efficient communi-cation protocol for wireless microsensor networks,” in Proc. HICSS, pp. 1–10, 2000.[55] S. Lindsey and C. Raghavendra, “PEGASIS: Power-efficient gathering in sensor infor-mation systems,” in Proc. IEEE AeroConf, vol. 3, pp. 1125–1130, 2002.[56] M. Quwaider, J. Rao, and S. Biswas, “Body-posture-based dynamic link power controlin wearable sensor networks,” IEEE Commun. Mag., vol. 48, pp. 134 –142, Jul. 2010.[57] A. Ehyaie, M. Hashemi, and P. Khadivi, “Using relay network to increase life time inwireless body area sensor networks,” in Proc. IEEE WoWMoM, pp. 1–6.120REFERENCES[58] Y. Tselishchev, L. Libman, and A. Boulis, “Reducing transmission losses in body areanetworks using variable TDMA scheduling,” in Proc. IEEE WoWMoM, pp. 1–10, Jun.2011.[59] X. Liu, E. Chong, and N. Shroff, “Opportunistic transmission scheduling with resource-sharing constraints in wireless networks,” IEEE J. Sel. Areas Commun., vol. 19,pp. 2053 –2064, Oct. 2001.[60] X. Liu, E. Chong, and N. Shroff, “A framework for opportunistic scheduling in wirelessnetworks,” Comput. Netw., vol. 41, pp. 451–474, Mar. 2003.[61] B. Shrestha, E. Hossain, S. Camorlinga, R. Krishnamoorthy, and D. Niyato, “Anoptimization-based GTS allocation scheme for IEEE 802.15.4 MAC with applicationto wireless body-area sensor networks,” in Proc. IEEE ICC, pp. 1–6, 2010.[62] Y. Huang, A. Pang, and H. Hung, “An adaptive GTS allocation scheme for IEEE802.15.4,” IEEE Trans. Parallel Distrib. Syst., vol. 19, pp. 641–651, May 2008.[63] N. Karthickraja, V. Sumathy, and J. Ahamed, “A novel hybrid routing protocol fordata aggregation in agricultural applications,” in Proc. IEEE ICCCCT, pp. 227–231,2010.[64] S. Sutar, K. Swapnita-Jayesh, and M. Pune, “Irrigation and fertilizer control for pre-cision agriculture using WSN: energy efficient approach,” Int. J. Advances in Comput.and Info. Researches, vol. 1, no. 1, 2012.[65] A. Mittal, K. Chetan, S. Jayaraman, B. Jagyasi, A. Pande, and P. Balamuralidhar,“mKRISHI wireless sensor network platform for precision agriculture,” in Proc. ICST,pp. 623–629, Dec. 2012.[66] K. P. Ferentinos, T. A. Tsiligiridis, and K. G. Arvanitis, “Energy optimization ofwireless sensor networks for environmental measurements,” in Proc. IEEE CIMSA,pp. 250 – 255, 2005.[67] H. Sahota, R. Kumar, A. Kamal, and J. Huang, “An energy-efficient wireless sensornetwork for precision agriculture.,” in Proc. IEEE Symp. Comput. Commun., Jun.2010.[68] H. Sahota, R. Kumar, and A. Kamal, “A wireless sensor network for precision agricul-ture and its performance,” in Proc. WCMC, pp. 1628–1645, 2011.121REFERENCES[69] W. Ye, J. Headmen, and D. Estrin, “An energy-efficient MAC protocol for wirelesssensor networks,” in Proc. IEEE INFOCOM, pp. 1567–1576, 2002.[70] T. van Dam and K. Langendoen, “An adaptive energy-efficient MAC protocol forwireless sensor networks,” in Proc. ACM SenSys., pp. 171–180, 2003.[71] S. Yoo, J. Kim, T. Kim, S. Ahn, J. Sung, and D. Kim, “A2S: Automated agriculturesystem based on WSN,” in Proc. IEEE ISCE, pp. 1–5, Jun. 2007.[72] A. Baggio, “Wireless sensor networks in precision agriculture,” in Proc. ACM REAL-WSN, 2005.[73] M. Keshtgari and A. Deljoo, “A wireless sensor network solution for precision agricul-ture based on ZigBee technology,” Wireless Sensor Network, pp. 25–30, 2012.[74] K. Fleming, D. Westfall, D. Wiens, and M. Brodahl, “Evaluating farmer definedmanagement zone maps for variable rate fertilizer application,” Precision Agriculture,vol. 2, no. 2, pp. 201–215, 2000.[75] H. Liu, Z. Meng, and Y. Shang, “Sensor nodes placement for farmland environmentalmonitoring applications,” in Proc. WiCom, pp. 1–4, Sep. 2009.[76] A. Awasthi and S. Reddy, “Monitoring for precision agriculture using wireless sensornetwork- a review,” Computers and Electronics in Agriculture, vol. 105, pp. 83–94, Jul.2014.[77] K. Seada, M. Zuniga, A. Helmy, and B. Krishnamachari, “Energy efficient forwardingstrategies for geographic routing in lossy wireless sensor networks,” in Proc. ACMSenSys., 2004.[78] R. C. Shah and J. M. Rabaey, “Energy aware routing for low energy ad hoc sensornetworks,” in Proc. IEEE WCNC, vol. 1, pp. 350–355, 2002.[79] P. Baronti, P. Pillai, W. Chook, S. Chessa, A. Gotta, and Y. Hu, “Wireless sensornetworks: A survey on the state of the art and the 802.15.4 and ZigBee standards,”Comput. Commun., vol. 30, no. 7, pp. 1655 – 1695, 2007.[80] N. Salodkar, A. Karandikar, and V. Borkar, “A stable online algorithm for energy-efficient multiuser scheduling,” IEEE Trans. Mobile Comput., vol. 9, pp. 1391 –1406,Oct. 2010.122REFERENCES[81] X. Liu, “Opportunistic scheduling in wireless communication networks,” Ph.D. Thesis,Purdue University, 2002.[82] H. Wymeersch, J. Lien, and M. Win, “Cooperative localization in wireless networks,”UWB Technol. and Emerg. Appl., vol. 97, pp. 427–450, Feb. 2009.[83] G. Mao, B. Fidan, and B. Anderson, “Wireless sensor network localization techniques,”Comput. Netw., vol. 51, pp. 2529 – 2553, Jul. 2007.[84] K. Kim, I. Lee, M. Yoon, J. Kim, H. Lee, and K. Han, “An efficient routing protocolbased on position information in mobile wireless body area sensor networks,” in Proc.NETCOM, pp. 396–399, 2009.[85] L. Sang, A. Arora, and H. Zhang, “On link asymmetry and one-way estimation inwireless sensor networks,” ACM Trans. Sen. Netw., vol. 6, pp. 1–25, Feb. 2010.[86] T. Yang, T. Oda, L. Barolli, J. Iwashige, A. Durresi, and F. Xhafa, “Investigation ofpacket loss in mobile WSNs for AODV protocol and different radio models,” in Proc.IEEE AINA, pp. 709–715, 2012.[87] G. Sharma, V. Sahu, P. Maurya, and R. Paulus, “Analyzing the effect of constant andlognormal shadowing model on ad-hoc routing protocols,” Int. J. Comp. Appl., vol. 66,no. 8, pp. 16 –19, 2013.[88] S. Itoua, “Effect of propagation models on ad hoc networks routing protocols,” in Proc.SENSORCOMM, pp. 752–757, 2008.[89] I. Eltahir, “The impact of different radio propagation models for mobile ad hoc net-works (MANET) in urban area environment,” in Proc. AusWireless, p. 30, 2007.[90] Y. S. Meng, Y. H. Lee, and B. C. Ng, “Path-loss modeling for near-ground VHFradio-wave propagation through forests with tree-canopy reflection effect,” Progress InElectromagnetics Research M, pp. 131–141, 2010.[91] M. Weissberger, “An initial critical summary of models for predicting the attenuationof radio waves by trees,” Tech. Rep. ESD-TR-81-101, 1982.[92] M. O. Al-Nuaimi and R. B. L. Stephens, “Measurements and prediction model opti-mization for signal attenuation in vegetation media at centimetre wave frequencies,”IEE Microwaves, Antennas and Propagation, vol. 145, pp. 201–206, Jun. 1998.123REFERENCES[93] A. Natarajan, B. De Silva, K.-K. Y., and M. Motani, “To hop or not to hop: Networkarchitecture for body sensor networks,” in Proc. IEEE SECON, pp. 1–9, Jun. 2009.[94] M. Cardei and D. Du, “Improving wireless sensor network lifetime through power awareorganization,” IEEE/ACM Trans. Netw., 2005, vol. 11, pp. 333–340, Mar.[95] A. Lindgren, A. Doria, and O. Schelen, “Probabilistic routing in intermittently con-nected networks,” SIGMOBILE Mob. Comput. Commun. Rev., vol. 7, pp. 19–20, Jul.2003.[96] S. Ahmed, N. Javaid, S. Yousaf, A. Ahmad, M. Sandhu, M. Imran, Z. Khan, andN. Alrajeh, “Co-LAEEBA: cooperative link aware and energy efficient protocol forwireless body area networks,” Computers in Human Behavior, vol. 51, pp. 1205–1215,2015.[97] N. Javaid, A. Ahmad, Q. Nadeem, M. Imran, and N. Haider, “ iM-SIMPLE: iMprovedstable increased-throughput multi-hop link efficient routing protocol for wireless bodyarea networks,” Computers in Human Behavior, vol. 51, pp. 1003–1011, 2015.[98] F. Di Franco, C. Tachtatzis, R. Atkinson, I. Tinnirello, and I. Glover, “Channel es-timation and transmit power control in wireless body area networks,” IET WirelessSensor Systems, vol. 5, no. 1, pp. 11–19, 2015.[99] L. Liang, Y. Ge, G. Feng, W. Ni, and A. Wai, “A low overhead tree-based energy-efficient routing scheme for multi-hop wireless body area networks,” Computer Net-works, vol. 70, pp. 45–58, 2014.[100] Q. Wang, M. Hempstead, and W. Yang, “A realistic power consumption model forwireless sensor network devices,” in Proc. IEEE SECON, pp. 286–295, 2006.[101] C. Cordeiro and M. Patel, “Body area networking standardization: present and futuredirections,” in Proc. ICST, p. 10, 2007.[102] I. Dietrich and F. Dressler, “On the lifetime of wireless sensor networks,” ACM Trans.Sen. Netw., vol. 5, pp. 1–39, Feb. 2009.[103] K. Srinivasan and P. Levis, “RSSI is under appreciated,” in Proc. EmNets, 2006.[104] C. Antonopoulos, A. Prayati, T. Stoyanova, C. Koulamas, and G. Papadopoulos,“Experimental evaluation of a WSN platform power consumption,” in Proc. IEEEIPDPS, pp. 1–8, 2009.124REFERENCES[105] C. Guo, R. Prasad, and M. Jacobsson, “Packet forwarding with minimum energyconsumption in body area sensor networks,” in Proc. IEEE CCNC, pp. 1–6, 2010.[106] Y. Yu, B. Krishnamachari, and V. Prasanna, “Energy-latency tradeoffs for data gath-ering in wireless sensor networks,” in Proc. INFOCOM, pp. 244–255, 2004.[107] F. Xiangning and S. Yulin, “Improvement on LEACH protocol of wireless sensor net-work,” in Proc. SensorComm, pp. 260–264, 2007.[108] A. Dhamdhere, V. Sivaraman, V. Mathur, and S. Xiao, “Algorithms for transmissionpower control in biomedical wireless sensor networks,” in Proc. IEEE APSCC, pp. 1114–1119, 2008.[109] S. Misra and S. Sarkar, “Priority-based time-slot allocation in wireless body area net-works during medical emergency situations: An evolutionary game-theoretic perspec-tive,” IEEE J. Biomed. Health Inform., vol. 19, no. 2, pp. 541–548, 2015.[110] S. Xiao, V. Sivaraman, and A. Burdett, “Adapting radio transmit power in wirelessbody area sensor networks,” in Proc. ACM BodyNets’08, pp. 141–148, 2008.[111] Q. He and C. Debrunner, “Individual recognition from periodic activity using hiddenmarkov models,” in Workshop Human Motion, pp. 47–52, 2000.[112] E. Ijjina and C. Mohan, “One-shot periodic activity recognition using convolutionalneural networks,” in Proc. ICMLA, pp. 388–391, 2014.[113] A. Yang, R. Jafari, S. Shankar, and R. Bajcsy, “Distributed Recognition of HumanActions Using Wearable Motion Sensor Networks,” J. Ambient Intell. Smart Environ.,vol. 1, pp. 103 –115, Feb. 2009.[114] E. Guenterberg, H. Ghasemzadeh, V. Loseu, and R. Jafari, “Distributed continuousaction recognition using a hidden markov model in body sensor networks,” in Proc.IEEE ICDCS, pp. 145–158, 2009.[115] H. Ghasemzadeh, V. Loseu, and R. Jafari, “Structural action recognition in bodysensor networks: distributed classification based on string matching,” IEEE Trans.Inf. Technol. Biomed., vol. 14, pp. 425 –435, Mar. 2010.[116] I. Rish, “An empirical study of naive Bayes classifier,” int. joint on AI, pp. 41–46,2001.125REFERENCES[117] G. F. Cooper, “The computational complexity of probabilistic inference using bayesianbelief networks,” J. AI, vol. 42, no. 2-3, pp. 393 – 405, 1990.[118] “Chipcon data sheet for CC2420, 2.4 GHz IEEE 802.15.4/ZigBee RF transceiver.”http://focus.ti.com/lit/ds/symlink/cc2420.pdf, 2004.[119] H. Liu, H. Darabi, P. Banerjee, and J. Liu, “Survey of wireless indoor positioningtechniques and systems,” IEEE Trans. Syst. Man Cybern., vol. 37, no. 6, pp. 1067–1080, 2007.[120] Y. Gu, A. Lo, and I. Niemegeers, “A survey of indoor positioning systems for wirelesspersonal networks,” IEEE Commun. Surveys Tuts., vol. 11, no. 1, pp. 13–32, 2009.[121] Z. Farid, R. Nordin, and M. Ismail, “Recent advances in wireless indoor localizationtechniques and system,” J. Comput. Netw. and Commun., vol. 2013, 2013.[122] M. Allen, E. baydere, and G. Gaura, “Evaluation of localization algorithms,” in Local-ization Algorithms and Strategies for Wireless Sensor Networks, 2009.[123] C. Pearson, M. McGuire, and Y. Coady, “The application of Wi-Fi radiolocation re-search to mobile devices,” in Proc. IEEE Pacific Rim Conf. on Commun., Comput.and Signal Process., pp. 768–773, Aug. 2009.[124] O. Hernandez, V. Jain, S. Chakravarty, and P. Bhargava, “Position location monitoringusing IEEE 802.15.4/ZigBee technology.” in Freescale Wireless Connectivity Operationin Mexico, 2007.[125] K. G. Cassman, “Ecological intensification of cereal production systems: Yield poten-tial, soil quality, and precision agriculture,” Proceedings of the National Academy ofSciences, vol. 96, pp. 5952–5959, May 1999.[126] S. El-kader and B. El-Basioni, “Precision farming solution in Egypt using the wirelesssensor network technology,” Egyptian Informatics Journal, vol. 14, no. 3, pp. 221–233,2013.[127] M. Keshtgari and A. Deljoo, “A wireless sensor network solution for precision agri-culture based on ZigBee technology,” Wireless Sensor Networks, vol. 4, pp. 25–30,2012.126REFERENCES[128] Y. Zhu, J. Song, and F. Dong, “Applications of wireless sensor network in the agricul-ture environment monitoring,” Wireless Sensor Networks, vol. 4, pp. 25–30, 2012.[129] A. Boukerche, H. Oliveira, E. Nakamura, and A. Loureiro, “Localization systems forwireless sensor networks,” IEEE Wireless Commun., vol. 14, pp. 6–12, Dec. 2007.[130] G. Han, H. Xu, T. Duong, J. Jiang, and T. Hara, “Localization algorithms of wirelesssensor networks: a survey,” Telecommunication Systems, vol. 52, pp. 2419–2436, Aug.2013.[131] T. He, C. Huang, B. M. Blum, J. Stankovic, and T. Abdelzaher, “Range-free localiza-tion schemes for large scale sensor networks,” in Proc. MobiCom, pp. 81–95, 2003.[132] Y. Shang, W. Ruml, Y. Zhang, and M. J. Fromherz, “Localization from mere connec-tivity,” in Proc. ACM MobiHoc, pp. 201–212, 2003.[133] Y. Wang, X. Wang, D. Wang, and D. Agrawal, “Range-free localization using expectedhop progress in wireless sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 20,pp. 1540–1552, Oct. 2009.[134] D. Niculescu and B. Nath, “DV based positioning in ad hoc networks,” Telecommun.Syst., vol. 22, pp. 267–280, Jan. 2003.[135] H. Shen, Z. Ding, S. Dasgupta, and C. Zhao, “Multiple source localization in wirelesssensor networks based on time of arrival measurement,” IEEE Trans. Signal Process.,vol. 62, pp. 1938–1949, Apr. 2014.[136] J. Xu, M. Ma, and C. Law, “Cooperative angle-of-arrival position localization,” Mea-surement, vol. 59, pp. 302–313, 2015.[137] F. Yaghoubi, A. Abbasfar, and B. Maham, “Energy-efficient RSSI-based localizationfor wireless sensor networks,” IEEE Commun. Lett., vol. 18, pp. 973–976, Jun. 2014.[138] F. Bandiera, A. Coluccia, and G. Ricci, “A cognitive algorithm for received signalstrength based localization,” IEEE Trans. Signal Process., vol. 63, pp. 1726–1736,Apr. 2015.[139] G. Wang and K. Yang, “A new approach to sensor node localization using RSS mea-surements in wireless sensor networks,” IEEE Trans. Wireless Commun., vol. 10,pp. 1389–1395, May 2011.127REFERENCES[140] A. Coluccia, “Reduced-bias ML-based estimators with low complexity for self-calibrating RSS ranging,” IEEE Trans. Wireless Commun., vol. 12, pp. 1220–1230,Mar. 2013.[141] A. Coluccia and F. Ricciato, “RSS-based localization via bayesian ranging and iterativeleast squares positioning,” IEEE Commun. Lett., vol. 18, pp. 873–876, May 2014.[142] H. Sahota and R. Kumar, “Network based sensor localization in multi-media appli-cation of precision agriculture Part 1: Received signal strength,” in Proc. ICNSC,pp. 191–196, Apr. 2014.[143] A. Ihler, J. Fisher, R. Moses, and A. Willsky, “Nonparametric belief propagation forself-localization of sensor networks,” IEEE J. Sel. Areas Commun., vol. 23, pp. 809–819, Apr. 2005.[144] V. Savic and S. Zazo, “Cooperative localization in mobile networks using nonparamet-ric variants of belief propagation,” Ad Hoc Networks, vol. 11, no. 1, pp. 138 – 150,2013.[145] J. Yedidia, W. Freeman, and Y. Weiss, “Exploring artificial intelligence in the newmillennium,” ch. Understanding belief propagation and its generalizations, pp. 239–269, 2003.[146] M. Welling and J. Lim, “A distributed message passing algorithm for sensor localiza-tion,” in Proc. ICANN, pp. 767–775, 2007.[147] A. Simonetto and G. Leus, “Distributed maximum likelihood sensor network localiza-tion,” IEEE Trans. Signal Process., vol. 62, pp. 1424–1437, Mar. 2014.[148] G. Calafiore, L. Carlone, and M. Wei, “A distributed technique for localization of agentformations from relative range measurements,” IEEE Trans. Syst., Man, Cybern. A,Syst.,Humans, vol. 42, pp. 1065–1076, Sep. 2012.[149] J. A. Costa, N. Patwari, and A. O. Hero, III, “Distributed weighted-multidimensionalscaling for node localization in sensor networks,” ACM Trans. Sen. Netw., vol. 2,pp. 39–64, Feb. 2006.[150] R. Garg, A. Varna, and M. Wu, “Gradient descent approach for secure localization inresource constrained wireless sensor networks,” in Proc. IEEE ICASSP, pp. 1854–1857,Mar. 2010.128REFERENCES[151] Q. Shi, C. He, H. Chen, and L. Jiang, “Distributed wireless sensor network localizationvia sequential greedy optimization algorithm,” IEEE Trans. Signal Process., vol. 58,pp. 3328–3340, Jun. 2010.[152] S. Tomic, M. Beko, and R. Dinis, “Distributed RSS-based localization in wireless sensornetworks based on second-order cone programming,” Sensors, vol. 14, pp. 18410–18432,Feb. 2014.[153] S. Srirangarajan, A. Tewfik, and L. Zhi-Quan, “Distributed sensor network localizationusing SOCP relaxation,” IEEE Trans. Wireless Commun., vol. 7, pp. 4886–4895, Dec.2008.[154] A. T. Ihler, W. Fischer III, John, and A. S. Willsky, “Loopy Belief Propagation:Convergence and Effects of Message Errors,” J. Mach. Learn. Res., vol. 6, pp. 905–936, Dec. 2005.[155] V. Krishnamurthy, O. Gharehshiran, and M. Hamdi, “Interactive sensing and decisionmaking in social networks,” Found. Trends Signal Process., vol. 7, no. 1-2, pp. 1–196,2014.[156] V. Krishnamurthy and M. Hamdi, “Mis-information removal in social networks: Con-strained estimation on dynamic directed acyclic graphs,” IEEE J. Sel. Topics SignalProcess., vol. 7, pp. 333–346, Apr. 2013.[157] R. Peng and M. Sichitiu, “Robust, probabilistic, constraint-based localization for wire-less sensor networks,” in Proc. SECON, 2005.[158] M. Rabbat and R. Nowak, “Decentralized source localization and tracking,” in Proc.IEEE ICASSP, vol. 3, pp. 921–924, May 2004.[159] P. Oguz-Ekim, J. Gomes, J. Xavier, and P. Oliveira, “A convex relaxation for approx-imate maximum-likelihood 2D source localization from range measurements,” in Proc.IEEE ICASSP, pp. 2698–2701, Mar. 2010.[160] K. Lui, W. Ma, H. So, and F. Chan, “Semi-definite programming algorithms for sensornetwork node localization with uncertainties in anchor positions and/or propagationspeed,” IEEE Trans. Signal Process., vol. 57, pp. 752–763, Feb. 2009.129REFERENCES[161] P. Biswas, T. Liang, K. Toh, Y. Ye, and T. Wang, “Semidefinite programming ap-proaches for sensor network localization with noisy distance measurements,” IEEETrans. Autom. Sci. Eng., vol. 3, pp. 360–371, Oct. 2006.[162] Z. Luo, W. Ma, A.-C. So, Y. Ye, and S. Zhang, “Semidefinite relaxation of quadraticoptimization problems,” IEEE Signal Processing Mag., vol. 27, no. 3, pp. 20–34, 2010.[163] P. Tseng, “Second-order cone programming relaxation of sensor network localization,”SIAM J. Optim., vol. 18, pp. 156–185, Feb. 2007.[164] Z. Wang, S. Zheng, Y. Ye, and S. Boyd, “Further relaxations of the semidefinite pro-gramming approach to sensor network localization,” SIAM J. Optim., vol. 19, pp. 655–673, Jul. 2008.[165] A. Seville and K. Craig, “Semi-empirical model for millimetre-wave vegetation atten-uation rates,” Electron. Lett., vol. 31, pp. 1507–1508, Aug. 1995.[166] Y. Meng, Y. Lee, and B. Ng, “Path loss modelling for near-ground VHF radio-wavepropagation through forests with tree-canopy reflection effect,” Prog Electromagn Res,vol. 12, pp. 131–141, 2010.[167] J. Gay-Fernandez, M. Garcia Sanchez, I. Cuinas, and A. Alejos, “Propagation anal-ysis and deployment of a wireless sensor network in a forest,” Prog Electromagn Res,vol. 106, pp. 121–145, 2010.[168] A. Harun, M. Ramli, L. Kamarudin, D. Ndzi, A. Shakaff, A. Zakaria, and M. Jaafar,“Comparative performance analysis of wireless RSSI in wireless sensor networks motesin tropical mixed-crop precision farm,” in Proc. ISMS ’12., pp. 606–610, Feb. 2012.[169] S. Phaiboon and S. Somkuarnpanit, “Mobile path loss characteristics for low basestation antenna height in different forest densities,” in Proc. ISWPS’06, pp. 1–6, 2006.[170] Y. Meng, Y. Lee, and B. Ng, “Empirical near ground path loss modeling in a forest atVHF and UHF bands,” IEEE Trans. Antennas Propag., vol. 57, pp. 1461–1468, May2009.[171] R. Tewari, S. Swarup, and M. Roy, “An empirical result for the height gain in forestmedium,” IEEE Trans. Antennas Propag., vol. 32, pp. 1265–1268, Nov. 1984.130REFERENCES[172] P. Agrawal and N. Patwari, “Correlated link shadow fading in multi-hop wireless net-works,” IEEE Trans. Wireless Commun., vol. 8, pp. 4024–4036, Aug. 2009.[173] G. Mao, B. D. O. Anderson, and B. Fidan, “Path loss exponent estimation for wirelesssensor network localization,” Comput. Netw., vol. 51, pp. 2467–2483, Jul. 2007.[174] L. Miller, “Distribution of link distances in a wireless network,” J. Res. Natl. Inst.Stand. Technol., vol. 106, pp. 401–412, Mar. 2001.[175] A. Bel, J. Vicario, and G. Seco-Granados, “Localization algorithm with on-line pathloss estimation and node selection,” Sensors, vol. 11, pp. 6905–6925, 2011.[176] B. Majone, A. Bellin, E. Filippi, L. Loriatti, M. Martinelli, A. Massa, and G. Toller,“Wireless sensor network deployment for monitoring soil moisture dynamics at thefield scale,” Procedia Environmental Sciences, pp. 426–435, 2013.[177] R. Grisso, “Precision farming tools: soil electrical conductivity.” Virginia CooperativeExtension, 2009.[178] T. Mueller, F. Pierce, O. Schabenberger, and D. Warncke, “Map quality for site-specificfertility management,” J. Soil Sci. Soc. of America, vol. 65, pp. 1547–1558, 2001.[179] A. Agnello and H. Reissig, “comparison of mechanically applied pheromone dispensingtechnologies for mating disruption of tree fruit pest lepidoptera.” Virginia CooperativeExtension, 2008.[180] J. Eckert, F. Villanueva, R. German, and F. Dressler, “Considerations on QualityMetrics for Self-localization Algorithms,” in Proc. IEEE SASO’11, pp. 104–115, 2011.[181] “Apple facts.” http://urbanext.illinois.edu/apples/facts.cfm. Retrieved Aug.2015.[182] H. Liu, Z. Meng, H. Wang, and M. Xu, “Systematic random deployment for wirelesssensor network in agricultural sampling-interpolation applications,” in Proc. CCTA’13, vol. 393, pp. 53–59, 2013.[183] “Proven solutions for the internet of everything.” https://www.synapse-wireless.com/snap-components/rf-engine. Retrieved Aug. 2014.131REFERENCES[184] J. C. Duchi, A. Agrawal, and M. Wainright, “Dual averaging for distributed opti-mization: Convergence analysis and network scaling,” IEEE Trans. Automat. Control,vol. 57, no. 3, pp. 592–606, 2012.[185] A. Cerpa, N. Busek, and D. Estrin, “SCALE: A tool for simple connectivity assessmentin lossy environments,” Tech. Rep. 0021, UCLA CENS, 2003.[186] S. Shaik and S. Setty, “Performance comparison of AODV, DSR and ANODR for gridplacement model,” Int. J. Comp. Appl., vol. 11, no. 12, pp. 6–9, 2010.[187] K. Raju and S. Setty, “Performance evaluation of AODV and DSR in feasible andrandom placement models,” Int. J. Computer Sci. Manage. Stud., 2014.[188] R. Rajagopalan and P. Varshney, “Connectivity analysis of wireless sensor networkswith regular topologies in the presence of channel fading,” IEEE Trans. Wireless Com-mun., vol. 8, pp. 3475–3483, Jul. 2009.[189] C. Bettstetter and C. Hartmann, “Connectivity of wireless multihop networks in ashadow fading environment,” Wireless Netw., vol. 11, pp. 571–579, Sep. 2005.[190] X. Liu and M. Haenggi, “The impact of the topology on the throughput of interference-limited sensor networks with rayleigh fading,” in 2nd Annu. IEEE Commun. Soc. Conf.on Sensor and Ad Hoc Commun. and Netw., pp. 317–327, 2005.[191] R. Hekmat and P. Van Mieghem, “Connectivity in wireless ad-hoc networks with alog-normal radio model,” Mob. Netw. Appl., vol. 11, pp. 351–360, Jun. 2006.[192] Z. Zhang, G. Mao, and B. Anderson, “On the hop count statistics in wireless multihopnetworks subject to fading,” IEEE Trans. Parallel Distrib. Syst., vol. 23, pp. 1275–1287, Jul. 2012.[193] C. Perkins and E. Royer, “Ad-hoc on-demand distance vector routing,” in Proc. WM-CSA ’99, pp. 90–100, 1999.[194] J. Li, L. Andrew, C. Foh, M. Zukerman, and H. Chen, “Connectivity, coverage andplacement in wireless sensor networks,” Sensors, vol. 9, pp. 7664–7693, 2009.[195] “Steps to success in replanting.” http://www.al.gov.bc.ca/treefrt/replant/Steps_to_Success_in_Replanting.pdf, 1994.132REFERENCES[196] “High density apple production.” http://bayfield.uwex.edu/files/2011/02/High-Density-Apple-Production.pdf, 2011.[197] T. Robinson, “Should new york apple growers move up to higher tree densities?,” NewYork Fruit Quarterly, vol. 13, no. 1, pp. 27 –31, 2005.133