Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Optimization in wireless sensor and machine-type communication networks Naddafzadeh Shirazi, Ghasem 2014

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
24-ubc_2014_september_naddafzadehshirazi_ghasem.pdf [ 1.51MB ]
Metadata
JSON: 24-1.0167441.json
JSON-LD: 24-1.0167441-ld.json
RDF/XML (Pretty): 24-1.0167441-rdf.xml
RDF/JSON: 24-1.0167441-rdf.json
Turtle: 24-1.0167441-turtle.txt
N-Triples: 24-1.0167441-rdf-ntriples.txt
Original Record: 24-1.0167441-source.json
Full Text
24-1.0167441-fulltext.txt
Citation
24-1.0167441.ris

Full Text

Optimization in Wireless Sensor andMachine-Type CommunicationNetworksbyGhasem Naddafzadeh ShiraziB.Sc., Shiraz University, Iran, 2006M.Eng., National University of Singapore, Singapore, 2009A 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)April 2014c© Ghasem Naddafzadeh Shirazi 2014AbstractWireless sensor networks (WSNs) are systems used for detecting events andgathering information from an area of interest in many different applicationdomains, from home and industry automation, to healthcare and transporta-tion, to environmental monitoring. With regard to the communication taskinvolved in WSNs, they can also be seen as an instance of the new paradigm,known as machine-type communication (MTC). Similar to traditional wire-less sensors, MTC-enabled devices can communicate together without directhuman interference.Energy efficiency for the sake of longevity is perhaps the most challengingrequirement for many WSNs and MTC networks. In this thesis, we considerultra-wideband (UWB) transmission technology for energy-efficient commu-nication in WSNs. UWB achieves frugal use of energy by transmitting withlow spectral efficiency when compared to legacy wireless technologies. Thisalso allows it to operate license-exempt in many jurisdictions around theworld. More recently, however, wireless service operators consider the use ofcellular technology also for low data-rate applications originally only servedby WSN-type technology. In particular, long-term evolution (LTE) technol-ogy has moved into the focus for joint personal-communication and MTCnetworks. Recent releases of the LTE standard and ongoing work itemsiiAbstractin LTE standardization specifically accommodate low-cost and low-powerMTC.This thesis presents contributions that improve the performance of UWBWSN and LTE MTC networks in several aspects, namely lifetime, localiza-tion accuracy, and coverage. A common theme of these different contribu-tions are the use of optimization methods for obtaining scalable, robust,and/or low-complexity solutions.We first address the lifetime maximization problem in a UWB-basedWSN designed for multiple event detection. The key contribution is thejoint optimization of transmission and routing parameters of sensor nodesso that the energy consumption is distributed as evenly as possible amongthe entire WSN. We then investigate the challenges of localization in WSNsand provide a convex solution which is robust to measurement uncertainties.In the last part of this thesis we focus on providing coverage for low-costLTE MTC networks, where the challenge is to develop efficient transmissionstrategies that maximize the coverage of MTC devices in an LTE cell.iiiPrefaceThe material presented in this thesis is entirely based on research performedby myself under the supervision of Prof. Lutz Lampe in the Departmentof Electrical and Computer Engineering (ECE) at the University of BritishColumbia (UBC). Below is a list of publications related to the work presentedin this thesis, which includes commentaries on the role of collaborators.Publications Related to Chapter 2• Ghasem Naddafzadeh Shirazi and Lutz Lampe, “Lifetime Maximiza-tion in UWB Sensor Networks for Event Detection”, IEEE Trans.Signal Processing, vol. 59, no. 9, pp. 4411 – 4423, September 2011.• Ghasem Naddafzadeh Shirazi and Lutz Lampe, “Lifetime Maximiza-tion in UWB Sensor Networks for Event Detection Applications”, inIEEE International Conference on Communications (ICC), pp. 1 – 6,Cape Town, South Africa, May 2010.ivPublications Related to Chapter 3Publications Related to Chapter 3• Ghasem Naddafzadeh Shirazi, Michael Botros Shenouda, and LutzLampe, “Second Order Cone Programming for Sensor Network Lo-calization with Anchor Position Uncertainty”, IEEE Trans. WirelessCommunications, vol. 13, no. 2, pp. 749 – 763, February 2014.• Ghasem Naddafzadeh Shirazi and Lutz Lampe, “Second Order ConeProgramming for Robust Localization in Mobile Sensor Networks”,in IEEE Global Communication Conference (Globecom), 4th Interna-tional Workshop on Wireless Networking and Control for UnmannedAutonomous Vehicles (Wi-UAV), pp. 1 – 6, Atlanta, USA, December2013.• Ghasem Naddafzadeh Shirazi, Michael Botros Shenouda, and LutzLampe, “Second Order Cone Programming for Sensor Network Local-ization with Anchor Position Uncertainty”, in IEEE 8th Workshop onPositioning Navigation and Communication (WPNC), pp. 51 – 55,Dresden, Germany, April 2011.I hereby acknowledge the contribution by Dr. Michael Botros Shenouda, whowas a post-doctoral fellow in the Department of Electrical and ComputerEngineering at UBC in 2011, and helped me to understand the concept ofthe second order cone programming and to formulate the sensor localizationproblem.vPublications Related to Chapter 4Publications Related to Chapter 4• Ghasem Naddafzadeh Shirazi, Lutz Lampe, Gustav Vos, and SteveBennett,“Coverage Enhancement Techniques for Machine-to-MachineCommunications over LTE”, submitted.• Ghasem Naddafzadeh Shirazi, Lutz Lampe, Gustav Vos, and SteveBennett, “Enhancement for LTE Communication Systems”, UnitedStates Patent App.#14/046733, International App.#PCT/CA2013/050749,Sierra Wireless Inc. (Filed October 4, 2013).Chapter 4 is based on our research conducted in collaboration with SierraWireless 1 as a 4-term MITACS-Accelerate2 internship program (July 2012-November 2013) for “designing low-cost machine-to-machine (M2M) devicesfor long-term evolution (LTE) networks”. I would like to thank and acknowl-edge the help of Gustav Vos and Steve Bennett from Sierra Wireless, whohave provided continuous support and feedback in this project, in particularwith regard to the problem formulation and relevance for ongoing standard-ization efforts in the third generation partnership project (3GPP).We have acquired the necessary disclosure permissions from Sierra Wire-less for what appears in Chapter 4 in accordance with the UBC Mitacs-Accelerate Internship terms and Non-Disclosure Agreements3. The intelec-tual property and results of this project are owned by Sierra Wireless, in-cluding but not limited to the filed US and international patents listed above1Sierra Wireless (Head Office) is at 13811 Wireless Way, Richmond, British Columbia,Canada, V6V 3A4, Tel: 604.231.1100 – See more at: http://www.sierrawireless.com/2http://www.mitacs.ca/accelerate3http://www.mitacs.ca/sites/default/files/UBC-MitacsTerms-FINAL_June28_2011.pdfviPublications Related to Chapter 4and technical documents (Tdocs) that appear on the 3GPP website4.4http://www.3gpp.org/viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xivList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . xxAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xxvDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Machines Operating as Sensors . . . . . . . . . . . . . . . . . 31.2 Optimization Aspects . . . . . . . . . . . . . . . . . . . . . . 61.3 Thesis Outline and Main Contributions . . . . . . . . . . . . 81.4 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4.1 Ultra Wideband (UWB) . . . . . . . . . . . . . . . . . 10viiiTable of Contents1.4.2 Long-Term Evolution (LTE) . . . . . . . . . . . . . . 141.5 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . 161.5.1 Wireless Sensor Networks . . . . . . . . . . . . . . . . 171.5.2 Lifetime Maximization in Wireless Sensor Networks . 181.5.3 Sensor Network Localization . . . . . . . . . . . . . . 221.5.4 Machine-Type Communication over LTE . . . . . . . 262 Lifetime Maximization for UWB Sensor Networks . . . . . 302.1 Event Detection System Model . . . . . . . . . . . . . . . . . 322.1.1 Sensing Model . . . . . . . . . . . . . . . . . . . . . . 332.1.2 Transmission Model . . . . . . . . . . . . . . . . . . . 372.1.3 Routing . . . . . . . . . . . . . . . . . . . . . . . . . . 402.1.4 The Optimization Procedure . . . . . . . . . . . . . . 412.2 UWB Maximum Lifetime for Joint Event Detection (UMLJE) 432.2.1 Closed-Form Expression for the GLRT . . . . . . . . . 442.2.2 Detection Requirements . . . . . . . . . . . . . . . . . 452.2.3 Operational Lifetime . . . . . . . . . . . . . . . . . . . 482.3 Extension to Distributed Optimization (D-UMLJE) . . . . . 502.3.1 Distributed UMLJE (D-UMLJE) . . . . . . . . . . . . 512.3.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 552.4 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . 572.4.1 A Sample Scenario . . . . . . . . . . . . . . . . . . . . 582.4.2 Lifetime Comparison . . . . . . . . . . . . . . . . . . . 612.4.3 Convergence of D-UMLJE . . . . . . . . . . . . . . . . 652.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67ixTable of Contents3 Robust Localization in Wireless Sensor Networks . . . . . 693.1 Sensor Localization Framework . . . . . . . . . . . . . . . . . 723.1.1 Localization with Perfectly Known Anchor Positions . 723.1.2 Localization with Anchor Position Uncertainty . . . . 733.2 Unambiguously Localizable Nodes . . . . . . . . . . . . . . . 763.3 Tradeoffs between Accuracy and Complexity . . . . . . . . . 793.3.1 Relation of Robust SOCP and Robust SDP Relaxations 793.3.2 Combination of Robust SOCP and SDP . . . . . . . . 823.4 Extensions of the SOCP Formulation . . . . . . . . . . . . . . 843.4.1 Distributed SOCP-based Robust Localization Algo-rithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 853.4.2 Complexity Analysis . . . . . . . . . . . . . . . . . . . 883.4.3 An Expectation Maximization (EM) Approach for Gaus-sian Uncertainty with Unknown Covariance . . . . . . 953.4.4 Gradient Descent Refinement Method . . . . . . . . . 983.5 Robust Localization in Mobile Sensor Networks . . . . . . . . 993.5.1 Robust Formation Control . . . . . . . . . . . . . . . . 1003.5.2 Detecting Boundary Trespassing . . . . . . . . . . . . 1023.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . 1023.6.1 Performance of the Robust SOCP . . . . . . . . . . . 1033.6.2 Combination of RSOCP and RSDP . . . . . . . . . . 1093.6.3 The Distributed RSOCP Method . . . . . . . . . . . . 1123.6.4 EM Performance . . . . . . . . . . . . . . . . . . . . . 1143.6.5 Formation Control . . . . . . . . . . . . . . . . . . . . 1153.6.6 Boundary Trespassing Detection . . . . . . . . . . . . 119xTable of Contents3.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1214 Coverage Enhancement for LTE MTC . . . . . . . . . . . . 1224.1 Overview of Coverage in Uplink and Downlink LTE Channels 1264.1.1 LTE and MTC Coverage Requirements . . . . . . . . 1274.1.2 LTE Channel Model . . . . . . . . . . . . . . . . . . . 1294.2 Coverage Enhancement in PUSCH . . . . . . . . . . . . . . . 1294.2.1 Flexible TTI Bundling with CDMA Support . . . . . 1304.2.2 Protocol for Flexible TTI bundling and CDMA . . . . 1344.3 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . 1364.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1415.1 Directions for Future Research . . . . . . . . . . . . . . . . . 142Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144AppendicesA Proof of Proposition 3.1 . . . . . . . . . . . . . . . . . . . . . 170B Proof of Proposition 3.2 . . . . . . . . . . . . . . . . . . . . . 173xiList of Tables1.1 Comparison between wireless sensor networks (WSNs) andmachine-type communication networks (MTCNs). A bold-face font is used to identify the typical values for each feature. 41.2 Number of RBs per time slot for different LTE system band-widths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.1 Simulation Parameters for Lifetime Maximization . . . . . . . 583.1 Complexity of robust and non-robust SDP and SOCP. . . . . 893.2 Performance and complexity comparison of different robustlocalization methods for the network in Figure 3.2. CPU run-time is defined as the time spent for solving the CVX problem,and it is measured using Matlab’s tic and toc commands. . 1063.3 Performance of formation control with and without prior lo-calization and tightening. . . . . . . . . . . . . . . . . . . . . 1184.1 Comparison of some features for different LTE UE categoriesand LTE MTC UEs (category 0 (CAT0) devices). . . . . . . . 124xiiList of Tables4.2 MCL for UL and DL LTE channels in FDD mode. eNodeBin 2 transmit and 2 receive antenna configuration. UE with1 transmit and 2 receive antennas, and UE CAT0 with 1transmit and 1 receive antenna. . . . . . . . . . . . . . . . . 1284.3 Achieved coverage gain, spectral efficiency, and MTC datarates for flexible TTI bundling and spreading. Simulated CE,spectral efficiency and data rate for TBS=104 in one RB usingQPSK (M = 2). . . . . . . . . . . . . . . . . . . . . . . . . . 138xiiiList of Figures1.1 Thesis content and interdependencies between chapters. Wefocus on three main optimization problems related to WSNand MTC, two of which (lifetime and localization) are un-der the UWB sensor network framework, and the third one(coverage) relates to the LTE MTC. To model and solve eachof these three optimization problems, scalability, low com-plexity, robustness, and coexistence criteria are taken intoaccount. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.2 The first derivative of the Gaussian function known as theGaussian Monocycle, can be used as an IR-UWB pulse. Thepulse width parameter, tw, in this example is 0.5 ns. . . . . . 111.3 The concept of two-way ranging based on time of arrival(ToA) in IR-UWB. The pair-wise distance can be calculatedby dividing the propagation time to the propagation speed. . 121.4 LTE transmission block diagrams, a) OFDM in downlink di-rection, b) SC-FDMA in uplink direction for UE k. eNodeBis the LTE term for a base station. . . . . . . . . . . . . . . . 15xivList of Figures2.1 Illustration of the UWB-based sensor network for event de-tection. N UWB-enabled nodes (circles, si, i = 1, . . . , N) arelocated around a sink (square, o). They measure data fromK events (stars, ek, k = 1, . . . ,K with parameters θk), quan-tize the measurements into bki bits, and report it to the sink,where fkij denotes the data flow from si to sj for reportingthe event ek. . . . . . . . . . . . . . . . . . . . . . . . . . . . 332.2 Sensing model under presence of ek. . . . . . . . . . . . . . . 342.3 Flowchart of the proposed centralized and distributed lifetimemaximization algorithms. . . . . . . . . . . . . . . . . . . . . 422.4 Comparison between routes (a) URFP, (b) MERG, and (c)UMLJE. N = 25 sensor nodes (circles) detecting K = 2events e1, e2 (squares) with DRs νk = 0.03, ηk = 0.97. TheMLB approach in the homogeneous networks chooses thesame routes as URFP. The sink is located at (0,0), and thesquares at (30,0) and (30,30) represent the location of events.The numbers in brackets show the optimal number of quanti-zation bits bki at each node and the numbers in the parenthe-ses show the amount of flow in the link for each event. Eachline’s thickness is proportional to the amount of flow on thecorresponding link. In (c), arrows are used for indicating theflow directions in the network. . . . . . . . . . . . . . . . . . 592.5 Network lifetime of UMLJE and D-UMLJE as a function ofnumber of nodes for K = 2 events. . . . . . . . . . . . . . . . 62xvList of Figures2.6 Network lifetime of MERG, URFP and D-UMLJE as a func-tion of network size N for K = 2 events. . . . . . . . . . . . . 632.7 Network lifetime as a function of DRs for N = 25 nodes andK = 2 events. A smaller value of ζk corresponds to a stricterDR, which is shown as (ηk, νk) for each point. . . . . . . . . . 642.8 Achieved detection rate as a function of the desired detectionprobability ηk. Dotted line shows the 45◦ line for reference. . 652.9 Convergence of (a) qi, (b) ρki , and (c) value of dual functionin sample networks of sizes N = 10, 25, 50, and with K = 2.The values are normalized to their optimal value. . . . . . . . 663.1 A schematic of the proposed EM algorithm. In each E step, arobust SOCP is executed and then the covariance is estimatedin the M step. . . . . . . . . . . . . . . . . . . . . . . . . . . 973.2 Location of nodes found by the RSDP and RSOCP relax-ations for a sample scenario with |Na| = 8 anchors, |Ns| = 10general sensors, Rc = 25 m (|Ki| = 8.7), σ2d = −20 dBm2,and Ψi = −10 I2 dBm2. The blue circles and diamonds rep-resent the actual position of general nodes and anchors, re-spectively; the red asterisks and plus signs show the estimatedlocations of general nodes and anchors by RSDP, respectively;and the black dots and crosses show the estimated locationsof general nodes and anchors by the proposed RSOCP (3.7),respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . 104xviList of Figures3.3 The positioning MSE of the standard SOCP, RSOCP, andRSDP with and without gradient descent (GD) refinementas well as the positioning MSE of RESDP in random topolo-gies with |Ns| = 35 sensors, |Na| = 15 anchors, and Ψi =−10 I2 dBm2. The CRLB are also shown. . . . . . . . . . . . 1073.4 The positioning MSE, η, as a function of noise variance factorσ2d in random topologies with |Ns| = 18 sensors, |Na| = 12anchors, and Ψi = κ2i I2, κ2i = {−10, 0, 10} dBm2. 8 of theanchors are located at the corners. . . . . . . . . . . . . . . . 1083.5 The positioning MSE in a 1 km × 1 km area with |Ns| = 105sensors and |Na| = 45 anchors. A link failure probability of30% is considered. The link noise variance σ2ij changes from20 to 34 dBm2 (i.e. 10 to 50 m of noise standard deviation)and Ψi = κ2i I2, κ2i = {34, 37.5} dBm2 (i.e. a radius of 50 or75 m uncertainty around anchors). The anchor positions arerandomly chosen based on a uniform distribution. . . . . . . . 1093.6 Illustration of the RSOCP-RSDP combination algorithm in asample scenario. Communication range is Rc = 5 m (|Ki| =7.4), and the noise variance factor and uncertainty are set toσ2d = −20 dBm2, and Ψi = −10I2 dBm2, respectively. . . . . 110xviiList of Figures3.7 Average positioning MSE (solid lines) and time taken (dashedlines) for solving centralized RSDP, RSOCP and their com-bination for |N | = 200 nodes as a function of the fraction ofanchors, |Na||N | , with Rc = 6 m (|Ki| = 9.3), σ2ij = −35 dBm2,and κ2i = 0 dBm2. The anchor positions are randomly chosenbased on a uniform distribution. . . . . . . . . . . . . . . . . 1113.8 Comparison between the proposed distributed RSOCP andthe three-phase heuristic. The scatter plots for (a) η and (b)time are shown for 50 scenarios with |N | = 100 to 500, 40% ofwhich are anchors, σ2d = −20 dBm2, and Ψi = −10I2 dBm2.The diagonal solid and dashed lines are the x = y identity lines.1133.9 Positioning MSE, η, for EM after 1, 2, 3, 5, 10, 25 iterationsand after convergence, compared to the standard and robustSOCP. Number of sensors and anchors are |Ns| = 35 and|Na| = 15, respectively, and nm = 5 initial readings are usedin EM for each anchor. σ2ij = −20 dBm2, and Ψi = κ2i I2. . . 1153.10 Average and standard deviation of number of mobility iter-ations needed for making the entire network unambiguouslylocalizable. σ2d,ij = −20 dBm2, Ψi = −10 I2 dBm2, andRc = 8 m, |N | = 50, 100, 150, 200, and 40% of nodes arestatic anchors. . . . . . . . . . . . . . . . . . . . . . . . . . . 116xviiiList of Figures3.11 Formation of |N | = 200 mobile sensors, into a rotation ofthe letter G. The sensors are initially uniformly-randomlydistributed in a unit square around (0,0). The formationwith and without prior localization is shown with differentcolors and markers, and their corresponding performance areprovided in Table 3.3. . . . . . . . . . . . . . . . . . . . . . . 1173.12 Detecting trespassing of |Ns| = 60 mobile nodes on the con-vex hull of |Na| = 40 static anchors, a) entering b) exiting.Squares show actual trespassing and crosses are detectionsmade by RSOCP. σ2d = −20 dBm2, Ψi = −10 I2 dBm2. . . . 1204.1 A TTI bundle in our invention consists of NB “spreadingblocks”. Spreading codes of length NS are used for spreadingA symbols over one or more (F ) subframes, enabling con-current transmission of up to NS UEs. Different spreadingblocks may be scheduled non-consecutively over time and/orfrequency. Note that 2 out of 14 OFDM symbols in each sub-frame are unavailable for spreading since they are dedicatedto transmission of demodulation reference symbols (DMRS)for channel estimation. . . . . . . . . . . . . . . . . . . . . . . 1314.2 Comparison of rBLER as a function of SNR for the legacy(1, 1) PUSCH transmission and different spreading and bundlingconfigurations (Ns, NB). The rBLER curves are shown forboth perfect and imperfect (im) channel estimations. . . . . . 137xixList of Abbreviations3GPP Third Generation Partnership ProjectBLER Block Error RateBLUE Best Linear Unbiased EstimatorCAT0 LTE Category 0 User EquipmentCE Coverage EnhancementCP Cyclic PrefixCRLB Cramer-Rao Lower BoundD-UMLJE Distributed UMLJEDL DownlinkDMRS Demodulation Reference SymbolsDR Detection RequirementEM Expectation MaximizationEPA Extended Pedestrian Channel Model Type-AFCC Federal Communications CommissionxxList of AbbreviationsGLRT Generalized Log-Likelihood Ratio TestGPS Global Positioning SystemGSM Global System for Mobile CommunicationsH2H Human to Human CommunicationHSPA High Speed Packet AccessIFFT Inverse Fast Fourier TransformIoT Internet of ThingsIR-UWB Impulse Radio Ultra WidebandKKT Karush Kuhn Tucker Optimality ConditionsLCM Least Common MultiplierLoS Line of SightLP Linear ProgrammingLTE Long Term EvolutionLTE-A Long Term Evolution-AdvancedM2M Machine to Machine CommunicationMAC Medium Access ControlMB-OFDM Multi Band Orthogonal Frequency Division Multi-plexingxxiList of AbbreviationsMDS Multi-Dimensuinal ScalingMERG Minimum Energy Routing with Guaranteed Detec-tion RequirementsMLB Maximization of the Lifetime Upper-BoundMSE Mean Square ErrorMTC Machine-Type CommunicationMTCN Machine-Type Communication Networkns Nono SecondsOFDM Orthogonal Frequency Division MultiplexingPAPR Peak To Average Power RatioPBCH Physical Broadcast ChannelPDCCH Physical Downlink Control ChannelPDSCH Physical Downlink Shared ChannelPRACH Physical Random Access ChannelPRB Physical Resource BlockPSD Power Spectral DensityPUCCH Physical Uplink control channelPUSCH Physical Uplink Shared ChannelxxiiList of AbbreviationsQ-BLUE Quasi-Best Linear Unbiased EstimatorQoS Quality of ServiceRAN TSG Radio Access Network Technical Specification GroupRB Resource BlockrBLER Residual Block Error RateRE Resource ElementRSDP Robust SDPRSOCP Robust SOCPRV Redundancy VersionSC-FDMA Single Carrier Frequency Division Multiple AccessSDP Semidefinite ProgrammingSNR Signal to Noise RatioSOCP Second Order Cone ProgrammingTBS Transport block SizeTH Time HoppingToA Time of ArrivalTTI Transmission Time IntervalUE User EquipmentxxiiiList of AbbreviationsUL UplinkUMLJE UWB Maximum Lifetime for Joint Event DetectionUMTS Universal Mobile Telecommunications SystemURFP UWB Maximum Rate Feasibility ProblemUSN Ultra Wideband Sensor NetworkUWB Ultra WidebandWSN Wireless Sensor NetworkxxivAcknowledgementsFirst of all, I would like to express my deepest gratitude to Professor LutzLampe for his invaluable academic and personal support during my PhDstudies. His has taught me numerous concepts in the field of wireless com-munications and his advise has always directed my research towards success.I would also like to thank Dr. Anand Oka fromMicrosoft for his teachingsand support during my internship at BlackBerry. I also appreciate the helpof Dr. Michael Botros Shenouda for his teachings on the concept of convexoptimization.I am thankful to Mr. Gusav Vos and Mr. Steve Bennett from SierraWireless who have provided their valuable and frequent feedback on ourproject for low-cost machine-type communication design over LTE. I amalso grateful to MITACS for funding this part of my research through theAccelerate internship program.Last but not least, I am appreciative of all my great friends at UBC andECE’s Data Communication Lab., Dr. Ehsan Mohammadi Zahrani, JavadHajipour, Hao Ma, and Narjes Torabi to name a few, and especially mywife, Mrs. Fariba Aalamifar, who is the biggest inspiration in my academicand personal life.xxvDedicationIn the name of God, the compassionate, the merciful.To Fariba, my beloved wife; and to my dear parents.xxviChapter 1IntroductionWireless sensor networks (WSNs) are systems used for detecting events andgathering information from an area of interest in many different applicationdomains, from home and industry automation, to healthcare and transporta-tion, to environmental monitoring for social safety and security. Wirelesssensors operate on small batteries with limited energy and it is usually im-possible to provide external sources of energy. A sensor network shouldbe able to operate days, months, or even years without requiring humanassistance for inserting new sensors or replacing their batteries.Sensors are typically deployed in large amounts in random locations.A broad range of WSN applications, for example detection and trackingof events and targets, require accurate location information of sensors toperform well. Despite this fact, for preserving their low cost, it is unlikelythat they are equipped with complex self-localization units such as globalpositioning system (GPS). Therefore, WSNs should employ localization al-gorithms for obtaining location estimates. This is usually accomplished bycollecting the ranging information between nearby sensors. Once all the sen-sors in the network are localized, they can also find the most energy-efficientroutes to transmit their information to the data center (also known as the1Chapter 1. Introductionsink) so that they can last longer [1]. Hence, two preeminent optimizationproblems in WSNs are accurate localization from ranging information, andlifetime maximization based on adjusting the transmission power and routes.Wireless ultra wideband (UWB) technology enables transmission of sig-nals over a very large communication bandwidth. For example, accordingto the United States’ Federal Communications Commission (FCC), UWBtransmissions occur over a bandwidth larger than 500 MHz or 20% of thetotal available bandwidth [2]. UWB devices typically utilize the spectrumin the 3.1-10.6 GHz range in a license-exempt fashion, adhering to the spec-tral density (PSD) emission regulations and possible further restrictions ontheir transmission activities. Due to the stealth-like operation of UWB ra-dios enabled by the use of a large transmission bandwidth, UWB has a lowertransmission power, and equivalently a longer operation time of the batteryfor a given data rate, compared to a narrowband system [3]. UWB signalsalso have a high temporal resolution which makes it possible to measure timeof flight and thus find an accurate distance estimate between the transmitterand the receiver.The above-mentioned properties of UWB are well-aligned with the low-transmission-power and location-awareness requirements of WSNs. Theserelations are investigated in detail in the first two parts of this thesis. Specif-ically, we present a UWB sensor network (USN) model and optimize its life-time in Chapter 2. We then provide an optimization framework for WSNlocalization, which is also applicable to USNs, in Chapter 3.21.1. Machines Operating as Sensors1.1 Machines Operating as SensorsWith the advent of Internet of Things (IoT), the traditional sensors networksare being evolved to smarter entities with a higher degree of autonomy andinformation processing. This fact has given rise to the concept of machine-type communication (MTC), also known as machine to machine (M2M)communication, which has gained popularity in the past few years. MTCcan be considered a generalization of traditional sensor networks in termsof their higher processing capabilities and covering in a broader range ofapplications[4, 5].Different features of WSN and machine-type communication networks(MTCNs) are compared in Table 1.1. As can be seen, similar to a wire-less sensor node, an MTC device can be used for automation, healthcare,transportation, and environment monitoring applications. In addition, MTCdevices can be embedded to smart utility meters, electric vehicles, vendingmachines, point of sales terminals, etc., to accomplish a task related to a“business application” [5]. Similar to the traditional wireless sensor nodes,MTC devices usually have a simple design (low cost), transmit with a lowpower to conserve energy, and are typically deployed in large densities in anarea of interest. Both wireless sensor nodes and MTC devices can be staticor mobile. Although most of the WSN and M2M applications, such as eventdetection and smart metering, fit into the class of static networks, mobil-ity can occur in for example, target tracking applications, or in the caseof MTC, in electronic vehicle monitoring (charging control and billing [5]).The same argument holds for low versus high data rate, that is, most of31.1. Machines Operating as SensorsTable 1.1: Comparison between wireless sensor networks (WSNs) andmachine-type communication networks (MTCNs). A boldface font is usedto identify the typical values for each feature.Feature WSN MTCNDesired design Low Lowcost and complexityDensity High HighEnergy consumption Low LowMobility Zero-High Zero-HighData rate Low-High Low-HighProcessing capability Low Low-MediumCommon applications Monitoring, Monitoring,Automation, Automation,Healthcare, Healthcare,Transportation Transportation,Smart metering,Electronic VehiclesSelected wireless technology UWB LTEin this thesisInfrastructure Ad hoc Cellular41.1. Machines Operating as Sensorsthe WSN and M2M applications require low data rates, in contrast to fewhigh-data rate applications, e.g. video surveillance. MTC devices may alsohave extra processing capabilities compared to the traditional wireless sen-sor nodes which in turn helps them in local decision making and requiringlower data rates.M2M applications have grown tremendously in the past few years. Itis predicted that the number of M2M connections reaches a quarter of abillion in the year of 2014 [6, 7], and that the global M2M market valuedoubles every three years [8]. This is a big incentive that drives the cellularoperators to accommodate MTC in their networks. Long-term evolution(LTE) and LTE-advanced (LTE-A) are the latest cellular communicationstandards developed by the third generation partnership project (3GPP).Many cellular network operators have been migrating from GSM/HSPA,UMTS, and other legacy standards to LTE.There exist, however, some important challenges for providing MTC inLTE. As explained above, MTC devices (user equipment (UE) in the LTEterminology) should be able to work without a need for human interaction,e.g. for maintenance, for a long duration. Moreover, the high density ofMTC UEs should not lead to a substantially increased network cost forLTE operators (and consequently M2M customers). Hence, MTC UEs needto be designed with a low cost. Moreover, since in many M2M applicationsMTC UEs are located inside buildings or structures with large penetrationlosses and also unable to move, it is essential to enhance the MTC coverageso that they can access the network.This is the subject of the third optimization problem in this thesis.51.2. Optimization AspectsSpecifically, in Chapter 4 we compare the coverage of different LTE uplinkand downlink channels and identify the coverage gain required for MTCUEs in each of these channel, as reported in the 3GPP technical documents.We then focus on the channel with the worst coverage and propose a newtransmission scheme which can provide the required gain for low cost MTCUEs.1.2 Optimization AspectsThe algorithms that are developed in Chapters 2 and 3 of this thesis, respec-tively for lifetime maximization and sensor localization, take into accountthe specific characteristics and requirements of WSNs and USNs. In thesetwo chapters, we use the following criteria to design our “efficient” solutions.• Scalability: When the density of sensors becomes very large in thenetwork, even a powerful central controller may be unable to solvethe optimization problem. Therefore, a distributed algorithm shouldbe devised to let the nodes individually solve small-size optimizationproblems based on the local information in their neighborhood. Theglobal parameters are propagated in the network by iteratively solvingsuch small distributed algorithms until all the nodes converge to thefinal optimum solution.• Low Complexity: Due to the essentially limited resources availablein wireless sensor nodes, we need to derive solutions that are simple toimplement. In general, the solution to an optimization problem may61.2. Optimization Aspectsrequire a high computational power, and hence unsuitable for imple-mentation on simple sensors. On the other hand, the family of linearprogramming (LP) [9] and convex optimizations [10] can be usuallysolved, and implemented on sensors, with a tractable complexity.• Robustness: Because of the limited reliability of sensors and theirsimple design, algorithms devised for WSNs should take into accountthe underlying uncertainty in the system. The so called robust algo-rithms typically put a constraint on the problem so that the networkcan provide the desired performance, even when some of the nodes inthe networks suddenly fail, or provide inaccurate input information.The concepts of low complexity, scalability, and robustness will be definedmore formally in the context of each optimization metric in Chapters 2and 3.When we propose our transmission scheme for coverage enhancement oflow-cost MTC UEs in Chapter 4, we also provide scalability by allowingconcurrent transmission of multiple MTC UEs. The low complexity crite-ria in this context is enforced by the LTE regulations to design low-costMTC UEs. In addition, we take into account another criteria, namely co-existence, that is set by the LTE standard for MTC UEs. In fact, 3GPPasserts that the proposed coverage enhancement solutions for MTC UEsshould require a minimal change to the current LTE standards, so that theMTC UEs can operate with no hindrance to the legacy LTE UEs. We alsoobserve this requirement for our proposed solution in Chapter 4.71.3. Thesis Outline and Main Contributions1.3 Thesis Outline and Main ContributionsThe rest of this chapter provides an overview of the communication systemsthat will be used in our optimization frameworks in the later chapters. Inparticular, Section 1.4 provides background information on UWB commu-nication (used for USNs in Chapter 2), and on LTE cellular systems (usedfor MTC networks in Chapter 4). The literature review regarding WSNsand MTC networks in the context of lifetime, localization, and coverageoptimization problems will then be provided in Section 1.5.The contents and interdependencies of the next chapters of this thesisare illustrated in Figure 1.1. As this figure shows, Chapter 2 provides a USNmodel which is dedicated to detection and reporting of multiple events. Thelifetime of such networks is analyzed in detail and formulated as a convexfunction of the sensing rate and data flow in each UWB sensor. Then,based on the dual decomposition technique, a scalable distributed lifetimemaximization solution is derived. Our main contribution in Chapter 2 isproviding efficient (centralized and distributed) algorithms for maximizingthe network lifetime by jointly considering the UWB physical layer, sensingand routing parameters, and detection requirement constraints.Chapter 3 delves into the WSN localization problem and provides a suiteof convex optimization formulations for achieving robust and distributedlocalization. Our main achievement in this chapter is developing a robustlocalization framework with the capability of balancing between localizationaccuracy and computational complexity, a very important prerequisite forimplementing a localization algorithm on low cost sensors. At the end of81.3. Thesis Outline and Main ContributionsWireless SensorNetworks (WSNs)Machine-Type Communication Networks (MTCNs)Ultra-Wide Band (UWB)Long-Term Evolution (LTE)Optimization Problems:Features:Low Transmission PowerLifetime Maximization for Event Detection(Chapter 2)Accurate RangingNetwork Localization (Chapter 3)Low-Cost Design Coverage Enhancement (Chapter 4)Wireless Technology:Coexistence with legacy LTE devicesDistributed Algorithms (Scalability) Complexity ConstrainedRobustness to UncertaintyProperties of Proposed Solutions:Figure 1.1: Thesis content and interdependencies between chapters. We fo-cus on three main optimization problems related to WSN and MTC, two ofwhich (lifetime and localization) are under the UWB sensor network frame-work, and the third one (coverage) relates to the LTE MTC. To model andsolve each of these three optimization problems, scalability, low complexity,robustness, and coexistence criteria are taken into account.this chapter, an extension to the mobile sensor networks is also presented.Chapter 4 considers the coverage enhancement problem in MTC LTEnetworks and provides a transmission strategy which can significantly im-prove the coverage of the LTE uplink data channel, which is currently theLTE channel with the worst coverage. The novelty of the proposed coverageenhancement technique lies in its dynamically adjustable transmission sizewhich is scalable to the number of active MTC UEs, and can be controlled91.4. Backgroundfor the desired coverage gain. Moreover, it requires a minimal change in thecurrent LTE standard. Finally, Chapter 5 presents the concluding remarksand avenues for future extension.1.4 BackgroundThis section provides an introduction to the basic mathematical models andtransmission properties of ultra wideband (UWB) and long term evolution(LTE) wireless technologies. UWB and LTE are used in the next chaptersas the underlying wireless technologies for the wireless sensor and machinetype communication networks, respectively. More standardization details,comprehensive overviews and comparisons between UWB and LTE can befound in [11–13].1.4.1 Ultra Wideband (UWB)Large bandwidth required for UWB transmission can be realized using twodistinct signalling methods, namely carrier-modulated and carrier-free sig-nalling. Carrier-modulated UWB can be either based on the transmissionwith a single carrier over at least 500 MHz of bandwidth [14], or based on themulti-band orthogonal frequency division multiplexing (MB-OFDM) on the14 bands defined in the 3.1-10.6 GHz spectrum [15]. High data rates (severalhundred Mbps) can be achieved in both versions of carrier-modulated UWBover a short communication range (3-10 m).On the other hand, impulse radio UWB (IR-UWB) transmits carrier-less “impulses” with a very short duration of a few nano seconds (ns)) [16].101.4. Background−2 −1.5 −1 −0.5 0 0.5 1 1.5 2−0.5−0.4−0.3−0.2−0.100.10.20.30.40.5nanosecondsAmplitudeFigure 1.2: The first derivative of the Gaussian function known as the Gaus-sian Monocycle, can be used as an IR-UWB pulse. The pulse width param-eter, tw, in this example is 0.5 ns.Figure 1.2 shows a possible shape of the impulse in time domain knownas the Gaussian monocycle, which is basically the first derivative of theGaussian function. Mathematically,sIR-UWB(t) =ttwexp(−( ttw)2), (1.1)where tw is the pulse width parameter.The short duration of pulse translates into the large signal bandwidth inIR-UWB. This enables low to moderately high data rates (e.g., several tensto a few hundreds of kbps) for low-power short-range transmission when111.4. BackgroundFigure 1.3: The concept of two-way ranging based on time of arrival (ToA)in IR-UWB. The pair-wise distance can be calculated by dividing the prop-agation time to the propagation speed.combined with relatively simple receiver structures. But variants of IR-UWB can also be used for high data-rate. Moreover, the short pulse lengthleads a high temporal resolution, which mitigates the effect of fading andmakes precise ranging possible. In particular, from the time of arrival (ToA)of the line-of-sight (LoS) signal path, the ranging information between the121.4. Backgroundnodes can be calculated, for example using the two-way ranging protocol [17,18], as illustrated in Figure 1.3. As can be seen, the IR-UWB device Atransmits an impulse to device B at time t0, which is received and detectedat time t1. After a delay, td, which is known a priori to both sides, device Btransmits an impulse to A which is detected at time t3 at device A. Then,the A-B distance can be estimated as,dAB =t3 − t0 − td2c (1.2)where c is the propagation speed. The two-way ranging mechanism enablesIR-UWB nodes to obtain ranging information from their neighbours imme-diately after a round of hand-shaking. Besides the processing required atthe receivers for signal detection and ToA estimating, the only side informa-tion needed for this calculation is the propagation speed of the UWB signal,c, which is equal to the speed of light and known. This makes IR-UWBan ideal technology for implementation of positioning systems [19, 20]. Wefocus on the impulse radio transmission mode for UWB in this thesis.Since IR-UWB devices transmit with low power and low data rates overa wideband channel, it is not required to employ carrier sensing, powercontrol, or other medium access control (MAC) protocols for such UWBsystems [21]. Concurrent transmissions from multiple devices can be easilyaccommodated in the IR-UWB’s MAC layer, for example by time hopping(TH). In TH, different nodes transmit their impulses at different time in-stances that are identified by their unique pseudo-random TH sequences. Allof these properties make UWB radio an excellent choice for sensor networks,131.4. Backgroundwhere energy efficiency and operational simplicity is highly desirable. Wecan envision an application example, where nodes in an ultra wideband sen-sor network (USN) start their operation from a random placement, collectlocal ranging measurements from nearby nodes and perform self-localizationwith respect to other nodes in the network. Routes to send sensory data tothe data collection center are then established such that the USN is able tocontinue its operation for a very long time.1.4.2 Long-Term Evolution (LTE)As a leading cellular technology, LTE offers a flexible communication ar-chitecture designed to provide communication at a lower cost per bit andto accommodate the continuous growth in wireless cellular demand, bothin the number of connections and in the required data rate. Some of thekey elements of LTE are the integration of applications into an all-IP ar-chitecture, spectral flexibility with signal bandwidths between 1.4 MHz and20 MHz, and the use of orthogonal frequency division multiplexing (OFDM)for multiple access and high spectral efficiency [11].1.4.2.1 LTE StructureIn LTE, OFDM and its precoded variant known as single carrier frequencydivision multiple access (SC-FDMA) are employed for the transmission ofdata. In OFDM, information bits are modulated on orthogonal subcarriers,as illustrated in the transmitter block diagram in Figure 1.4(a). An effi-cient implementation of OFDM is possible by taking the inverse fast Fouriertransform (IFFT) of the input data, with the same size as the number of141.4. BackgroundeNodeB’s Modulated dataSerialToParallelConverterIFFTParallelToSerialConverterAdd CPLow-Pass Filter (LPF)OFDM Symbol(a)UE k’s Modulated dataSerialToParallelConverterIFFTParallelToSerialConverterAdd CPLow-Pass Filter (LPF)SC-FDMA SymbolFFTSub-Carrier MappingRBs of UE kRBs of otherUEs(b)Figure 1.4: LTE transmission block diagrams, a) OFDM in downlink direc-tion, b) SC-FDMA in uplink direction for UE k. eNodeB is the LTE termfor a base station.available subcarriers Nc, in order to map the symbols into their correspond-ing subcarriers [22, 23]. Mathematically,sOFDM(t) =1√NcNc−1∑k=0xk exp (j2pifkt) , 0 ≤ t < Ts (1.3)where xk is the data, Ts = 66.7µs is the OFDM symbol duration in LTE, andsubcarriers with center frequencies fk and uniform spacing of fk−1 − fk =1Ts = 15 kHz are used. Based on this, the atomic data unit in LTE, knownas a resource element (RE), has a duration of Ts = 66.7µs and a bandwidthof 15 kHz. A grid of 7 × 12 REs, in the time-frequency domain, is knownas the LTE resource block (RB), which forms the basic unit commonly usedin the LTE standard for scheduling and resource allocation of the devices.Considering the guard bands in frequency and cyclic prefix (CP) in time, anRB occupies 200 kHz over half a millisecond, which is also the duration of151.5. Literature ReviewTable 1.2: Number of RBs per time slot for different LTE system bandwidthsSystem Bandwidth (MHz) 1.4 2.5 5.0 10.0 15.0 20.0Number of RBs per time slot 6 12 25 50 75 100an LTE time slot. One LTE subframe, also known as the data transmissiontime interval (TTI), consists of two time slots (1 ms), and 10 consecutivesubframes form a radio frame. Depending on the total bandwidth, thenumber of RBs in a time slot can be obtained from Table 1.2 [24].SC-FDMA is used in uplink LTE transmission, as illustrated in Fig-ure 1.4(b). SC-FDMA is implemented by performing a partial FFT prior tothe actual OFDM mapping in the IFFT block, forming a “single-carrier” sig-nal. The main advantage of a single-carrier transmission is the lower peak toaverage power ratio (PAPR) compared to the (multi-carrier) OFDM trans-mission. Low PAPR is a highly desirable property in uplink LTE, becauseit simplifies the design of power amplifiers and leads to the development ofmore cost-effective UEs [11]. In SC-FDMA, each UE maps its symbols ondistinct subcarriers by using Fourier coefficients different from other UEs.The subcarriers which are assigned to a UE are usually selected consecu-tive to each other, which further reduces the cost of the FFT operation andsub-carrier mapping in SC-FDMA.1.5 Literature ReviewBefore proceeding to the technical chapters, we present a synopsis of theexisting literature on wireless sensor and machine-type communication net-161.5. Literature Reviewworks in this section. The studies that are closely related to our work willbe highlighted again in each individual chapter with more technical details.We start by reviewing the studies on WSNs and USNs in Section 1.5.1. Adetailed literature review on the lifetime maximization and location estima-tion problems is then provided in Sections 1.5.2, and 1.5.3, respectively. Theworks that consider LTE-based MTC and address its coverage enhancementproblem are finally reviewed in Section 1.5.4.1.5.1 Wireless Sensor NetworksThanks to the advances in the design of low cost sensors, WSNs are nowwidely used in many applications including manufacturing automation [25,26], smart home design for entertainment [27], healthcare [28], and safety[29]. There has been a considerable volume of research in the last decadeon the optimization of different aspects of WSNs, for example lifetime max-imization (cf. Section 1.5.2), accurate localization (cf. Section 1.5.3), con-gestion control, coverage enhancement, and quality of service (QoS)-awarescheduling [1, 30–35].1.5.1.1 Ultra Wideband Sensor NetworksIR-UWB transmission was proposed by Scholtz and Win in 1998 [16]. InIR-UWB, low data rate communication in short range is possible with avery low transmission power. Furthermore, the use of TH [36] allows a verysimple MAC without a need for power control or carrier sensing [21, 37–39].Performing localization in USNs is also very effective due to the high resolu-tion multipath components in the IR-UWB signal. Accordingly, the use of171.5. Literature ReviewIR-UWB as the physical layer of WSN devices has been promoted in severalstudies [19, 20, 40–46]. Zhang et al. [41] provide a comparison between theperformance of narrowband WSNs and USNs, and conclude that UWB is abetter choice for many sensor applications due to high interference resilience,low transceiver complexity, low transmission power, and localization accu-racy. A practical USN architecture for outdoor applications is presented byOppermann et al. in [40]. This model supports low data rate (around 10kbps) transmission of a few thousands of UWB sensors through multi-hopcommunication. Based on this framework, a USN were deployed in a ski fieldfor the localization and tracking purposes. Similarly, IR-UWB is used in [42]for developing a real-time target-tracking and accident-warning system forunderground construction sites. Melodia and Akyildiz utilize TH-IR-UWBtowards the design of a QoS-aware USN for multimedia applications [43].1.5.2 Lifetime Maximization in Wireless Sensor NetworksEnergy efficiency is probably the most important challenge in WSN designdue to the limited capacity of sensor batteries [47, 48]. Sleep mechanismscan provide longer sensor lifetime [49], however, care must be taken not tomake the network disconnected [50]. Several node placement and clusteringmethods have been proposed in the literature to account for coverage andadjusting the sleep duration [51–54].The WSN lifetime maximization through flow control has been thor-oughly investigated in the literature [55–60]. The lifetime can be definedas the time at which the first, or a specific percentage of sensors depletetheir batteries [55–57] and/or the network becomes disconnected [61]. A181.5. Literature Reviewmore application-oriented definition, however, is given in terms of the net-work lifetime, which is defined as the total time interval during which thenetwork as a whole is able to accomplish the required objective [58–60] evenif some sensors are already disconnected, or if a disconnected topology in amulti-sink architecture occurs [62–64].Chang and Tassiulas [55] investigate the minimum energy routing throughthe lowest cost paths from sensors to the sink, where the cost is defined asthe sum of energy consumed for transmission and reception of data pack-ets. Wang et al. [56] provide a cross-layer convex optimization frameworkbased on tuning the physical-layer, MAC and routing parameters in orderto maximize the lifetime in different network topologies. They derive theKarush-Kuhn-Tucker (KKT) optimality conditions in the general case, andgive closed-form solutions for the 3 and 4-node networks.Direct formulation of lifetime maximization commonly leads to a cen-tralized optimization problem [55, 60]. In order to convert the central-ized optimization into smaller distributed sub-problems, dual decompositiontechniques on the original convex problem can be employed. For example,Madan and Lall [65] decompose the standard lifetime maximization problemusing the dual function and Lagrange multipliers on the energy and flowconstraints. In the distributed methods, nodes are required to exchangethe Lagrange multipliers and local flow and lifetime parameters with theirneighbors and update them iteratively until converging to the near-optimalsolution. Similarly, Xi and Yeh [57] investigate a node-based cross-layeroptimization and derive the optimality conditions based on a general linkcost function, and present a distributed power control and routing opti-191.5. Literature Reviewmization to account for scalability to the network size. This distributedalgorithm can be solved in each node by an iterative algorithm based ongradient projection, with a guaranteed convergence to the optimal solutionwith a few control message exchange between neighboring sensor nodes. Inorder to make the dual function differentiable, regularization techniques aresometimes applied to the objectives. For example, [66] further changes theobjective to optimize a weighted sum of lifetime and the routing cost.Usually, the bottleneck nodes, i.e. sensors which are closer to the sink,should forward more data traffic than the other nodes, and are more likely todie first. To mitigate the effect of this problem, the use of multi-commodityflows in the network can help to balance the traffic over the sensor nodes[60, 65], and consequently achieve a longer lifetime. Furthermore, Bloughand Santi [59] argue that a longer lifetime can be achieved by enforcingcooperation between nodes, for example by adjusting their sleep schedulesor participating in data aggregation. In data aggregation, each sensor mergesthe received data from other sensors with its local measurements accordingto the correlation between them. This results in a longer network lifetimedue to reduced volume of exchanged data packets [67, 68].1.5.2.1 Energy Efficient Event DetectionA common class of WSN applications for data collection is event detection,for example in radar, sonar and ultrasound surveillance systems [69, 70],for disaster monitoring and emergency response [71], for example tsunamiand earthquake alarm systems [72], farm protection [73], habitat monitoring[74], and for patient monitoring in health-care facilities [75, 76].201.5. Literature ReviewEnergy efficient routing strategies in WSN specific to event detectionhave been investigated in [69] and [70]. Yang et al.[69] consider active radar-like sensors responsible for detecting the presence of an object, and use theNeyman-Pearson hypothesis test [77, 78] to design their decision variables.They use a Lagrangian relaxation technique to maximize a lower bound forlifetime. In another work, Li and AlRegib [70] derive an upper bound forlifetime as a function of the number of bits used at a node for representingits measurements. This enables nodes to tradeoff accuracy of the reportedmeasurement with energy consumption for communication. Their approachis based on decoupling the problem of quantization from the routing prob-lem. Specifically, each node first minimizes a local cost function to decideon the number of bits that it will generate for detecting an event. Then alinear program is solved to obtain the optimal routes and flows of the en-tire network. The decoupling significantly decreases the complexity of theproblem. The algorithms proposed in [69] and [70] provide useful solutionsfor the energy efficiency problem under event detection requirements.There are a number of related literature on USNs for event detection. Forexample, Bai et al. [79] propose and compare the performance of differentdistributed detection techniques in UWB sensor networks under energy con-straints. However, only the UWB physical layer is considered in this studyand routing layer optimization is left unhandled. Xu et al. [80] provide someupper bounds on the operational lifetime of a general UWB sensor network,and Shi and Hou [81] investigate the UWB maximum rate feasibility prob-lem. They solve this non-linear problem using a linearization relaxationtechnique and devise a heuristic for connecting the source nodes to the sink.211.5. Literature ReviewNone of these works consider the exact lifetime maximization of USNs for agiven detection requirement.In Chapter 2, we provide centralized and distributed lifetime maximiza-tion frameworks for an event-detection USN, and compare their performanceto the algorithms proposed in [69, 70], and [81].1.5.3 Sensor Network LocalizationThe availability of accurate information about the location of nodes is essen-tial in many sensor network applications, for example target tracking anddetection, cooperative sensing, and energy-efficient routing [82–85].The localization problem and its properties, such as computational com-plexity and unique localizability have been investigated in recent studies,e.g. [86–89]. A common approach for sensor localization is to utilize the(noisy) ranging information between sensor nodes and anchor nodes, i.e.nodes with a priori known location, in order to estimate the sensor positions.This ranging information is obtained for nodes which are in the communica-tion range of each other by measuring received signal strength [90, 91], angleof arrival [92], or ToA [93, 94]. In general, D+1 “anchor nodes”, defined asthe nodes with known positions, can triangulate a node in a D-dimensionalspace. Moreover, the availability of more anchors increases the localizationaccuracy at the cost of more computational complexity.It is well-known that the sensor localization problem in its general form,due to the presence of measurement noise, is very difficult to solve. In fact,the exact solution of the localization problem with noisy measurements hasa high computational complexity and belongs to the NP-hard class of al-221.5. Literature Reviewgorithms [95]. A number of approaches have been proposed to reduce thecomplexity of the localization problem in the general case. These meth-ods can be categorized as non-parametric [96, 97] and parametric [98–104]class of algorithms. The non-parametric methods such as [96, 97] commonlyperform localization based on correlating the received signals to a set ofsignatures which are collected from different location and distance config-urations. On the other hand, the parametric approaches are based on anunderlying assumption on the signal propagation and thus may suffer fromthe modeling mismatch, but they do not require offline data collection.An example of the parametric approach is the multi-dimensional scalingapproach (MDS-MAP) by Shang et al. [98], which constructs an approxi-mate map of the network based on the shortest-path distance informationbetween the nodes, and then applies MDS to the map in order to find therelative locations of the nodes. The weighted least square method can bealso used for obtaining approximate closed-form location estimates [104],but this method relies on the availability of a good initial estimate.Another common parametric approach to the localization problem is torelax the original problem to a convex formulation which can be efficientlysolved using algorithms such as interior point methods [10]. The two mainconvex relaxation techniques that have been considered for the sensor local-ization problem are second order cone programming (SOCP) [105, 106], andsemidefinite programming (SDP) [107–109]. Authors in [107] use SDP todetermine and localize the subset of nodes which are uniquely localizable inthe absence of noise. It is shown that if the network is uniquely localizable,SDP can verify and provide the exact solution in a polynomial time. How-231.5. Literature Reviewever, both SDP and SOCP provide suboptimal solutions in the presence ofnoise.Most sensor localization algorithms assume accurate anchor positions inorder to estimate the location of the rest of the sensor nodes. However,in many scenarios anchor positions may not be accurately known. Thisuncertainty in turn significantly affects the quality of the estimated sen-sor positions. Robust sensor localization under anchor position uncertaintyis studied in [110], where a convex relaxation based on SDP is developed.More specifically, a maximum likelihood criterion consisting of two parts isoptimized. The first term reflects the likelihood of measurements, which iscommon in the robust and non-robust optimization. The second term isthe likelihood of anchor positions, which forces the problem to find a reli-able solution despite any errors in the initial measurement(s) of the anchorpositions.Another important issue for the localization problem is the scalabilityto larger networks. In fact, when the number of nodes in the network islarge, the centralized formulations of MDS-MAP, SDP and SOCP includemany optimization variables and constraints, and therefore, solving thementails a high computational complexity. A three-phase distributed refine-ment algorithm is proposed for the SOCP [105] and a distributed MDSapproach is proposed in [111] which uses the local ranging information inthe sensors to calculate their locations. A distributed version of SDP isalso proposed in [109], which can localize large networks by solving SDPon small clusters of nodes. If the anchors are not distributed uniformly,this method requires intelligent clustering to accurately localize nodes that241.5. Literature Revieware connected to only a few anchors (usually at the network boundaries).A different approach for reducing the complexity of SDP is known as theedge-based method [110, 112, 113], which further relaxes SDP by break-ing a large constraint into smaller ones at the cost of reduced localizationaccuracy. Edge-based SDP methods can be also solved in a distributedmanner [114]. In this paper we provide a new distributed algorithm basedon SOCP. Different from the distributed SDP algorithm proposed in [109],it does not require clustering. It is faster compared to the edge-based SDPmethods [114], and also leads to a more accurate localization when comparedto the existing distributed robust approaches [105].Chapter 3 extends the works in [106, 107, 110], and provides more tech-nical details on the properties and relations of robust localization based onSDP and SOCP techniques .1.5.3.1 Localization in Mobile Sensor NetworksMobile sensor networks consist of a group of mobile nodes (robots, un-manned vehicles, sensors, cellphones, etc.) which dynamically change theirlocations, sometimes by posing into a desired formation, to cooperatively ac-complish different tasks such as sensing or event detection [115]. Therefore,localization and tracking are the two inherent challenges in the mobile sensornetworks. Localization and tracking of nodes in mobile sensor networks canbe accomplished with the help of sequential Monte Carlo methods, Bayesianor particle filtering [116–119]. In these tasks, one of the main challenges isthe ambiguity of the initial sensor locations. A solution to this problemis to perform a robust localization prior to (as in [120]) or jointly with (as251.5. Literature Reviewin [118, 121]) the main tracking algorithm. Such approaches may sufferfrom the high complexity of localization algorithms in a large network, andthus convex relaxation techniques may be required for generating a simplersolution, yet with an acceptable accuracy.Formation control, i.e. creating and maintaining a desired shape is anessential part of many cooperative robot systems [122, 123]. In [122], au-thors use a (non-robust) convex optimization to minimize the total nodetraveled distances for forming a desired topology with or without vehiclemotion constraints. Their convex relaxation is based on second order coneprogramming (SOCP), which is known to have a low complexity (e.g. com-pared to semidefinite convex relaxation) and be scalable to the large networksize. Due to this property, it is shown in [122] that the SOCP optimizationis able to control the robot movements to the optimal direction in real-timeand with an acceptable accuracy, if the exact initial locations of the nodesare known. In practice, however, the initial location uncertainty of the mo-bile robots necessitates design of a robust SOCP algorithm for this task, aswill be explained in Section 3.5.1.5.4 Machine-Type Communication over LTEThe inherent differences between the operation of M2M and human-to-human (H2H) wireless communication devices and systems, such as higherdevice density and smaller message lengths for M2M communication, callsfor modifications and optimizations in the physical and higher layers ofMTC [124]. Reference [125] investigates the benefits of optimizing the MTCnetwork for mobility. Environment-aware design of M2M networks for green261.5. Literature Reviewcommunication [126] and secure communication [127] have also been con-sidered in the literature.In recent years, the idea of using cellular technologies for providing reli-able MTC-based services to customers has attracted the attention of manynetwork operators around the globe. Among different cellular technologies,long-term evolution (LTE) leads the way towards regulating MTCNs due toits promising role in the future of cellular communication [5, 11]. To thisend, 3GPP thrives to develop an optimized MTC-enabled LTE architecturesin the near future [7].MTC devices may belong to different access classes of the LTE cell basedon their features, such as low mobility, small data transmission, secure con-nection, and location-specific trigger [128]. Moreover, the high density ofMTC devices makes it difficult for the LTE base station (known as the eN-odeB) to perform access management. In this regard, several device cluster-ing algorithms have been proposed in the literature [129, 130]. In [130, 131],simple and cooperative access management schemes for high-density M2Mnetworks with QoS guarantees have been proposed. Under their model,MTC devices work in clusters and the eNodeB assigns resources to theclusters based on their arrival rate, and deterministic or statistical packetjitter requirements. Also, a non-cooperative game theory framework for dis-tributed rate and admission control in the context of multimedia sharinghas been proposed in [132].In [133], it is argued that the current QoS classes for H2H communica-tion, which are typically delay requirements, are not suitable for the MTCdevices, because of the different nature of their application. They propose271.5. Literature Reviewand analyze new QoS categories for M2M devices based on accuracy, pri-ority, and real-time requirements. In order to enhance the functionality ofdensely-deployed M2M devices in the LTE uplink random access channel,different intelligent random access algorithms can be employed [134–136].It is also essential to ensure the active MTC devices, which have data totransmit, can be covered over the entire cell area. The next section gives anoverview of coverage enhancement literature in LTE-based MTC networks.1.5.4.1 Coverage Enhancement for MTC over LTEIn June 2013, a new coverage enhancement (CE) study item, for LTE ingeneral, has been approved in the 3GPP radio access network technical spec-ification group (RAN TSG) [137]. This study aims at identifying the (uplinkand downlink) LTE channels which have a worse coverage, and to find solu-tions for improving their coverage. By balancing the level of coverage amongdifferent LTE channels, the UEs can have a more reliable communication atthe cell edge.A need for CE is intensified in MTCNs, since different from H2H cellularcommunication, MTC UEs are often immobile and located inside buildingswhich suffer from high penetration loss. The 3GPP work item [138], whichhas also been initiated in June 2013, considers the CE specifically for MTC.The methods that are currently being reviewed in this work item include thesimplifications of the structure of control messages, repetition of data, PSDboosting, and a relaxed false-alarm mode for the contention-based accessof MTC UEs [139]. In addition, as an alternative to the default centralizedmode of operation, some studies propose that when MTC UEs are in low cov-281.5. Literature Reviewerage in an LTE cell, they can form a mesh so that the packets from farthernodes can be relayed to the eNodeB with the help of closer nodes [140–142].We propose a novel CE method based on the data repetition technique inChapter 4.29Chapter 2Lifetime Maximization forUWB Sensor NetworksIn the first technical chapter of our thesis, we address the energy efficiencyaspect of WSNs, which is one the most important challenge in designinga WSN. In this chapter we consider a specific, yet commonly-used, classof UWB sensor networks, namely USNs used for event detection. For ac-complishing an event detection task, UWB sensor nodes should observe thestatus of one or more events at known locations and report their observa-tions (measurements) to a fusion center (sink) through multihop routing.At the sink, a decision about the event status is made using the receivedmeasurement results from reporting sensors.We aim at optimizing the routing of measurement data from nodes tothe sink such as to maximize the operational lifetime of the WSN. Here, theoperational lifetime is defined as the time from the beginning of operationof the WSN until the WSN is unable to perform its task, i.e., until givendetection requirements (DRs) cannot be met any more. Our method jointlyoptimizes routes to detect multiple events, which avoids the overuse of indi-vidual sensor nodes in multiple paths known to decrease operational lifetime.30Chapter 2. Lifetime Maximization for UWB Sensor NetworksFurthermore, nodes send their measurements with different precisions to thesink. For example, a node with a larger/smaller amount of remaining energyrepresents its measurement with larger/smaller number of bits. By consider-ing this degree of freedom in our model, nodes can easily trade off accuracywith energy consumption, leading to an overall increase in network lifetime.The optimization problem is formulated as a convex program, and numericalresults for selected network examples show that the lifetime achieved withthis program are considerably increased compared to those obtained withdifferent routing schemes proposed in the literature, such as the minimumenergy routing with guaranteed detection requirements (MERG) [69], themaximization of the lifetime upper-bound (MLB) [70], and the UWB max-imum rate feasibility problem (URFP) [81].We show that our model improves these works by considering a moregeneral framework as well as providing more effective techniques for maxi-mizing the lifetime. Specifically, we consider and maximize exact networklifetime subject to DRs, compared to the optimization of lower and upperbounds on lifetime in [69] and [70]. We also improve upon [69] by consideringvariable generation rates and balancing them based on the sensor’s locationand available energy. In addition, we overcome the well-known bottlenecknode problem, i.e., fast depletion of a node with a higher amount of flowcompared to other nodes, by jointly optimizing the routes for all event loca-tions, such that the flows can be balanced among different paths to prolonglifetime. A distributed method is also proposed as a solution that shares thecomputational load for optimization among sensors and only requires localcommunication. This distributed method extends the dual decomposition312.1. Event Detection System Modelmethod [65, 66] by taking into account the DRs.This chapter is organized as follows. The event detection system modeland assumptions made are described in detail in Section 2.1. The opti-mization framework for UWB-based sensor network lifetime maximizationis presented in Section 2.2, and its distributed version is explained in Sec-tion 2.3. The performance of the proposed method is then evaluated andcompared by means of simulations in Section 2.4.2.1 Event Detection System ModelWe consider a multiple-event detection UWB-based sensor network, as il-lustrated in Figure 2.1. In this network, N sensors si, i = 1, . . . , N , shouldsense the K events ek, k = 1, . . . ,K, and report their measurements to thesink o. The sensors si are placed at locations (xi, yi), and events ek are ex-pected to occur at locations (x′k, y′k). Throughout this chapter, we assumethat sensors know their locations, for example by employing the localizationmethods that will be explained in Chapter 3. Let dij denote the Euclideandistance between si and sj. Each node si can transmit to or receive from thenodes in its communication rangeD, i.e., its neighboursNi = {sj : dij ≤ D}.Details about the sensing model are provided in Section 2.1.1. After sensingthe events, the measured data is routed to the sink via multipath routingas explained in Section 2.1.3. Energy consumption at the nodes for datatransmission and data flow in the links are determined by the UWB-specifictransmission and link capacity models, as will be described in Section 2.1.2.322.1. Event Detection System ModelSink(o)sjf112eK, sie2, e1, sN,[rKN]s1,[r11]s2,[r12]f2jo f2ijfKjoFigure 2.1: Illustration of the UWB-based sensor network for event detec-tion. N UWB-enabled nodes (circles, si, i = 1, . . . , N) are located around asink (square, o). They measure data from K events (stars, ek, k = 1, . . . ,Kwith parameters θk), quantize the measurements into bki bits, and report itto the sink, where fkij denotes the data flow from si to sj for reporting theevent ek.2.1.1 Sensing ModelConsider the task of sensing in the network for gathering information abouta possible event at a given location. Figure 2.2 illustrates the sensing modelfor an event ek in such a network. The presence of the event ek is indicatedby the parameter θk, which is observed by the sensors. Let Hk1 and Hk0 ,k = 1, · · · ,K, indicate the presence and absence of ek, respectively. Under332.1. Event Detection System ModelQuantizationQuantizationQuantizationsink  owiw1s1ek, θkwNykisiyk1sNbkibkNbk1ykNmk1mkNmkiFigure 2.2: Sensing model under presence of ek.this model, the measured signal at sensor si is given bymki =wi, Hk0 ,θk + wi, Hk1 ,(2.1)where wi is Gaussian measurement noise with variance σ2i . We assume thatthe events occur at locations which are far from each other relative to thecommunication range D. Therefore, in (2.1) it is implied that each sensorobserves at most one event (cf. also [75, 143]). Furthermore, note thatknown attenuation of observations can be easily handled by the sensingmodel in (2.1). Specifically, denoting the attenuation between si and ek byaki , the modelm′ki = aki θk + w′i (2.2)342.1. Event Detection System Modelwith noise variance σ′2i reduces to (2.1) by letting mki = m′ki /aki and σ2i =σ′2i /(aki )2 [70, 144]. We would also like to point out that (2.1) includes theactive sensing framework of [69] as a special case, where sensors should sendsignals to the location of ek with the sensing energy Es and measure thereflected signal. In fact, (2.2) can be specified to the active sensing modelby applying the deterministic value θk =√Es and setting aki =√βik, whereβik is the path loss coefficient between ek and si. Note, however, that in thegeneral model (2.1) the value of θk is unknown, and the sensors are requiredto estimate it when ek is present (Hk1 ).We further assume that the measurement mki is quantized into bki ∈{1, 2, . . . , bmax} bits, i.e., si sends only bki bits for the measurement mki tothe sink. The quantization interval, MR = [−M,M ], with a fixed knownM > 0 which is determined based on the effective signal range that sensorscan observe [70, 145]. In order to provide an unbiased estimate for θk, we usethe probabilistic quantization scheme from [145], whereMR is divided into2bki equal intervals of length ∆ki = 2M2bki, and the measurement n∆ki ≤ mki ≤(n+1)∆ki is mapped to its quantization yki.= Q(mki ) using the probabilitiesP (yki = n∆ki ) = 1−mki − n∆ki∆kiP(yki = (n + 1)∆ki)= 1− P (yki = n∆ki ) . (2.3)The quantization error variance for this method is given by%ki (bki ) =M2(2bki − 1)2. (2.4)352.1. Event Detection System ModelA larger value of bki leads a smaller quantization error variance %ki (bki ) andthus provides a higher accuracy of detection, but at the cost of consumingmore energy and bandwidth for transmitting more data bits to the sink. Forbrevity of notation, we definepiki.= σ2i + %ki (bki ) (2.5)as effective measurement variance and omit the explicit dependence of pikion bki .We assume that each sensor performs sensing at regular intervals oflength Ts. Accordingly, we define the generation rate of node si for event ekasrki.= bki /Ts . (2.6)Clearly, a node can tradeoff between accuracy and energy consumption byvarying its generation rate.As it is shown in [70, 145], the quantized measurements of yki , i =1, . . . , N , generated by mapping (2.3) enable an unbiased estimation of θkunder hypothesis Hk1 . The corresponding quasi-best linear unbiased estima-tor (Q-BLUE) of θk is specified asθk =( N∑i=11σ2i + %ki (bki ))−1 N∑i=1ykiσ2i + %ki (bki ). (2.7)This is essentially the same as the BLUE estimator given un-quantized data,except that the quantization variance %ki (bki ) is added to the noise varianceσ2i .362.1. Event Detection System ModelWe assume that the sensing interval Ts is chosen such that the value ofθk is changing much slower than the sensing rate. Under this assumption,the filtered estimateθˆk(`) = δ θˆk(`− 1) + (1− δ) θk, (2.8)is used for determining the likelihood of hypothesisHk1 in the current sensinginterval `, where θˆk(`−1) is the estimate from the previous interval `−1 andδ < 1 is a forgetting factor to account for dynamics of θk. For brevity, weomit the interval index ` in the following and denote the updated estimateby θˆk.Given the described estimation procedure, deciding between Hk0 and Hk1is performed using the generalized log-likelihood ratio test (GLRT) [78, 146]LkHk1≷Hk0T k0 , (2.9)where Lk is given byLk = log Pr(Hk1 |yk1 , · · · , ykN , θˆk)Pr(Hk0 |yk1 , · · · , ykN ). (2.10)Here, the threshold T k0 is determined by the DRs. More details about thedetection procedure will be provided in Section 2.2.2.1.2 Transmission ModelTransmission of quantized measurements is performed using a TH-IR-UWBphysical layer. As stated earlier, TH-IR-UWB requires a very low transmis-372.1. Event Detection System Modelsion power. In addition, it is fairly robust to interference when time hoppingcodes are used for the transmission of UWB pulses. Based on these prop-erties, it is shown in [39] that power control is not required and each UWBnode should transmit with the maximum permissible power. Motivated bythis result, we assume that all sensors transmit with a fixed transmissionpower Ptx. Furthermore, we make use of the low spectral efficiency prop-erty of TH-IR-UWB and approximate the link capacity as a linear functionof SINR [147]. That is, we express the maximum achievable rate Cij fortransmission from si to sj asCij =Wln 2 µij , (2.11)where W is the bandwidth and µij denotes the SINR for this link. Thelatter is given byµij =Ptx αijσ2j + χ∑l∈Nj\{i} Itxl Ptx αlj, (2.12)where Itxl determines if node l is a potential interferer, i.e., Itxl = 1 if slis transmitting, and Itxl = 0 otherwise. The parameter χ is a constantdepending on the autocorrelation of the UWB pulse, and αij denotes thepath gain between nodes si and sj. For the latter, we adopt the double-slope UWB channel model developed during IEEE 802.15.4a standardization382.1. Event Detection System Model[18, 148], according to whichαij(dij) =g − 10γ1 log10(dij) dij ≤ d0,c0 − 10γ2 log10(dijd0 ) dij > d0,(in dB) , (2.13)where g is the gain for the unit distance, c0 is the gain for the referencedistance d0, and γ1, γ2 are the path-loss exponents. The SINR term in (2.12)along with the path gain model (2.13) are used in this paper for computingthe link capacities. We note, however, that other channel models could beused in our optimization framework.The indicator terms Itxl in (2.12) are determined by the scheduling oftransmissions in the network. The joint scheduling and routing problem inUWB has been investigated in [39, 81, 147]. In these studies, it is shownthat finding the optimal scheduling policy to achieve a given objective, suchas minimum power consumption or maximum throughput, is in general NP-hard to solve, and different techniques for finding an approximate solutionare suggested. The simpler interference-free scheduling, in which separatesubbands or time slots are assigned to links that would otherwise causeinterference to each other, is often assumed when lifetime maximization isdone at the routing layer [65, 69, 70]. In this case, the second term in thedenominator of SINR (2.12) would vanish and a larger capacity would beobtained, at the cost of synchronizing the nodes and providing orthogonalresources (time, frequency, etc.). Since the UWB PHY provides robustness392.1. Event Detection System Modelto interference (see (2.12)), carefully designed interference-free schedulingis not required. However, since including the exact effect of the schedulingpolicy significantly increases the complexity of optimizing the routing layer[39, 81, 147], in this work we resort to consider two extreme cases. The first isthe capacity lower bound CLij assuming maximum interference according toItxl = 1, ∀l ∈ Nj, and the second is the capacity upper bound CUij assumingItxl = 0, ∀l ∈ Nj in (2.12). This simplification allows us (i) to provide asimplified model for lifetime optimization in USNs, (ii) to fairly comparethe proposed framework to the existing literature which implicitly uses thescheduling with no interference (i.e., CUij) [69, 70], and (iii) to adapt thedistributed routing framework [65] to the problem at hand.Finally, we consider dynamic channel coding [37, 41, 43]. This techniqueadaptively adjusts the channel code rate according to the level of interfer-ence. This allows us to express the energy consumed for the transmission ofone bit from si to sj asEtx =PtxCij. (2.14)2.1.3 RoutingLet fkij be the data flow from si to sj for event ek. Then, the flow conserva-tion constraints are given byrki +∑j∈Nifkji −∑j∈Nifkij = 0, ∀i, k. (2.15)402.1. Event Detection System ModelSince all the flow is absorbed by the sink, the flow conservation is valid forthe sink node by definingrko = −N∑i=1rki , (2.16)and noting that fkoi = 0, ∀i, k.It is worth mentioning that the fraction of time taken for the transmissionof each flow is fkji/Cij . Thus, a feasible scheduling can be obtained for thehigh interference case if∑i∑j∑kfkijCLij≤ Ts . (2.17)This is also a sufficient condition for the existence of a feasible schedule inthe interference-free with the capacity upper bound CUij .2.1.4 The Optimization ProcedureBased on the sensing, transmission, scheduling, and routing models ex-plained above, a centralized and a distributed optimization of sensor ratesrki and flows fkij are devised in the next two sections. Figure 2.3 shows aflowchart of the proposed centralized and distributed algorithms. As canbe seen, in both methods the sink performs the GLRT to decide for Hk0or Hk1 , and updates the estimate for θk if the event ek is deemed present.In the centralized scheme, the sink also optimizes all routing variables andgeneration rates. Since the optimization of these parameters depends onthe estimate θˆk of θk, as will be explained in Section 2.2, the sink needs torepeat the optimization whenever the current estimate is notably different412.1. Event Detection System ModelFigure 2.3: Flowchart of the proposed centralized and distributed lifetimemaximization algorithms.422.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)from the estimate used previously for optimization. Since we assume that θkis changing slowly compared to Ts, the optimization by the sink is performedinfrequently. Furthermore, since no a priori model for the dynamics of θk isassumed to be known, the optimization by the sink needs to be performedin a myopic fashion. The routing and generation rate optimizations in thedistributed scheme are performed locally in each sensor, and the optimizedlocal variables only need to be exchanged among the neighboring nodes.However, the sink needs to broadcast the estimates θˆk in the network whennotable changes of these estimates occur.In the next section, we present the centralized UWB maximum lifetimefor joint event-detection (UMLJE) algorithm. Its distributed version, re-ferred to as D-UMLJE, is developed in Section 2.3.2.2 UWB Maximum Lifetime for Joint EventDetection (UMLJE)In UMLJE, the sink determines the generation rates and routing flows suchthat network lifetime is maximized and the DRs are satisfied. In this section,we first make the implementation of the GRLT from (2.10) explicit. Thenwe formalize the DRs as functions of generation rates and map them toequivalent convex constraints. Using these constraints, we devise a convexprogram for the lifetime maximization problem. For the derivation of theGLRT and DRs we closely follow [69], but we note that [69] did not considerquantization of measurements at sensor nodes.432.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)2.2.1 Closed-Form Expression for the GLRTIn order to obtain a closed-form expression for the GLRT, we approximateyki as a Gaussian distributed random variable with variance piki and mean0, if Hk0 , and mean θˆk, if Hk1 , where θˆk is the current estimation for θkgiven by (2.8). Then, according to the sensing model from Section 2.1.1, thegeneralized likelihood ratio Lk in (2.10) can be approximated asLk =N∑i=112piki(2θˆkyki − θˆ2k). (2.18)Therefore, the hypothesis test (2.9) follows asN∑i=1θˆkykipikiHk1≷Hk0T k0 +N∑i=1θˆ2k2piki. (2.19)It is convenient to make the following definitions:ψki.= θˆ2kpiki(2.20)ψk .=∑iψki (2.21)hk .=N∑i=1θˆkykipiki(2.22)T k1.=(T k0 +12N∑i=1ψki). (2.23)Then, the GLRT (2.19) can be expressed in the compact formhkHk1≷Hk0T k1 . (2.24)442.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)2.2.2 Detection RequirementsThe DRs for event-detection applications are given in terms of the proba-bility of detectionpkd.= Pr(Lk > T k0 |Hk1 ), (2.25)if event ek is present (hypothesis Hk1 ) and the probability of false alarmpkf.= Pr(Lk > T k0 |Hk0 ), (2.26)if ek is absent (hypothesis Hk0 ). Specifically, we focus on the Neyman-Pearson detection model [69, 77], where pkf = νk and pkd ≥ ηk should besatisfied for some thresholds νk and ηk. That is, the threshold T k0 in (2.9)is obtained by solving pkf = νk [78]. In the following, we elaborate on thisrelationship, which also relates the DR parameters νk and ηk to the sensorgeneration rates rki .The random variable hk defined in (2.22) has the variance ψk, and zeromean, if Hk0 , and mean θˆkθkpiki , if Hk1 . Since θˆk approximates θk, we assumethat E(hk|Hk1 ) ' ψk. Denoting by ϕ the cumulative distribution function(cdf) of the “standard” hk, i.e., when its mean and variance are adjusted to0 and 1, respectively, and using (2.24) in (2.26), the false alarm probabilitycan be expressed aspkf = 1− ϕ(T k1 − 0√ψk). (2.27)Since ϕ is not a one-to-one function due to the quantization step, we firstneed to define its inverse in an unambiguous manner. Let for values of{x0 < x1 < · · · < xn+1}, {p0 = 0 < p1 < · · · < pn = 1} be the set of values452.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)that ϕ(x) can take, i.e., xi ≤ x < xi+1 ⇔ ϕ(x) = pi. For pi ≤ p < pi+1 wedefine two inverse functions, ϕ−1↓ (p).= xi and ϕ−1↑ (p).= xi+1. Then, settingpkf = νk leads to the detection thresholdT k1 =√ψkϕ−1↑(1− νk), (2.28)where the use of ϕ↑ causes the achieved false alarm probability not to belarger than the desired νk. Similarly, from the demanded detection accuracypkd ≥ ηk it follows that1− ϕ(T k1 − ψk√ψk)≥ ηk . (2.29)This implies that in order to meet the DR constraints, the following condi-tion should be satisfied:ψk ≥ ξ2k.=(ϕ−1↑ (1− νk)− ϕ−1↓ (1− ηk))2, (2.30)where the use of ϕ↓ results in an achieved detection probability which isnever smaller than ηk. The expression in (2.30), through (2.20), (2.21),(2.5), and (2.6), links the generation rates rki to the DRs.Finally, we show that for any given ξ2k, the expression in (2.30) can alsobe written as an equivalent constraint.Proposition 2.1. Defineρk .=( N∑i=11piki)−1, ζk .= θˆ2kξ2k. (2.31)462.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)Then, the DR constraint in (2.30) can be equivalently written asρk ≤ ζk . (2.32)Proof. Introducing the definitions (2.20), (2.21), and (2.31) into the inequal-ity (2.30), we obtainρk =( N∑i=11piki)−1=( N∑i=1ψkiθˆ2k)−1= θˆ2kψk≤ θˆ2kξ2k= ζk .Proposition 2.1 states that the constraints (2.30) and (2.32) can be equiv-alently used to account for the DRs. Note that any value of ζk can bemapped to specific DRs at a given event signal-to-noise ratio (SNR),i.e.,θ2k/σ2i . As the DRs become stricter, ζk becomes smaller and hence sensorsneed to generate more bits per measurement in order to reduce ρk and satisfy(2.32).While constraints (2.30) and (2.32) can be used interchangeably, it turnsout that unlike (2.30), the expression (2.32) leads to a convex formulationof the DRs in the generation rates [149]. This can be verified by computingthe Hessian matrix of ρk with respect to variables rki and noting that it ispositive definite for rki ≥ κ0, where κ0 > 0 is a small threshold. It is alsoworth mentioning that ρk represents an upper bound on the mean squareerror (MSE) of the Q-BLUE estimation in (2.7) [70, 145].472.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)2.2.3 Operational LifetimeWe are interested in finding the maximum time during which the network isable to detect given events with the required detection probabilities, whichwe define as the operational lifetime of the network.Let ti denote the operational lifetime of node si during which it is able toperform sensing and routing for the events before its energy Ei is depleted.We can express ti asti =Ei∑k(Isik EsTs +∑j fkjiErx +∑j fkij(Ep +Etx)) , (2.33)where Es, Erx, and Ep is the energy consumed for sensing, receiving abit, and processing a bit, respectively. In (2.33), Isik = 1 only if si performssensing for the event ek, and the terms in the denominator correspond to theenergy consumed for sensing, receiving, and transmitting data, respectively,in each sensing interval. The operational lifetime of the network T is thendefined as the minimum lifetime among the nodes:T .= miniti . (2.34)Defining the inverse of the lifetime, q .= 1T , lifetime maximization can bewritten as the following optimization problem:minq,rki ,fkijq subject to (2.35a)rki +∑jfkji −∑jfkij = 0 ,∀i, k (2.35b)482.2. UWB Maximum Lifetime for Joint Event Detection (UMLJE)∑kIsikEsTs+∑jfkjiErx +∑jfkij(Ep + Etx) ≤ qEi ,∀i (2.35c)N∑i=11σ2i + M2(2rki −1)2−1≤ θˆ2k(ϕ−1↑ (1− νk)− ϕ−1↓ (1− ηk))2 ,∀k (2.35d)0 ≤ rki ≤bmaxTs,∀i, k (2.35e)0 ≤ q, (2.35f)0 ≤ fkij,∀i, j, k. (2.35g)In (2.35), the constraint (2.35b) ensures flow conservation, and the con-straint (2.35c) gives the local energy consumption in the nodes based on(2.33). Note that in each node, the total energy consumption for detecting,sensing, and reporting of all events is jointly considered. Since this constraintalso considers the total flow for multiple events, the optimal solution willefficiently avoid the bottleneck situations which would occur if single eventdetection methods like [69, 70] were applied. Consequently, the optimal so-lution will balance the energy consumption for sensing and communicatingamong the UWB-enabled sensors to achieve the highest operational lifetime.In addition, the DR constraint (2.35d) ensures that the DRs in (2.30) aresatisfied as well. Numerical evidence and quantitative results of these prop-erties are provided in Section 2.4, specifically, in Figures 2.4, 2.6, and 2.8.Finally, the last three constraints give the range of variables. While (2.35d)is written in terms of optimization variables, for brevity, we will use thecompact form (2.32) in the following.Furthermore, note that in the optimization (2.35), we consider continu-492.3. Extension to Distributed Optimization (D-UMLJE)ous variables rki . From the solution, we obtain bki by rounding to the nearestinteger. Consequently, all the constraints except (2.35d) are linear and sim-ple to handle for optimization routines. These constraints are also typicallyconsidered in existing lifetime maximization frameworks such as [55, 65].Moreover, the DR constraint (2.35d), which is unique to our problem, is alsoconvex in the variables rki . Hence, (2.35) is a convex optimization problemand can efficiently be solved by standard methods. Since the DR constraint(2.35d) depends on the value of θˆk, a new optimization should be performedby the sink if these parameters have notably changed over time.2.3 Extension to Distributed Optimization(D-UMLJE)In this section, we devise a distributed version of UMLJE, which we refer toas D-UMLJE. To this end, we apply a dual decomposition method similarto the one from [65] and [150], which decomposes problem (2.35) into localsubproblems by means of Lagrangian relaxation. These problems are solvedby exchanging Lagrange multipliers between nodes and updating the vari-ables based on the subgradient method. This process is continued until thevariables converge to their global optimal point, i.e., when the subgradientmethod is unable to improve the current values of the local variables.502.3. Extension to Distributed Optimization (D-UMLJE)2.3.1 Distributed UMLJE (D-UMLJE)To explain this in more detail, we start with the regularized objectiveJreg = q2 + ∑i,j,k(fkij)2 , (2.36)where  is the regularization weight. Note that the all terms in the objectivefunction are differentiable. The Lagrangian relaxation can then be used toobtain the following regularized decomposition of the original problem in(2.35):minq,rki ,fkijq2 + ∑i,j,k(fkij)2 +K∑k=1ωk(ρk − ζk)+∑i,kλki−rki −∑jfkji +∑jfkij+∑iτi∑kIsikEsTs+∑jfkjiErx∑jfkij(Ep + Etx)− qEi(2.37a)subject to 0 ≤ rki ≤bmaxTs, ∀i, k (2.37b)0 ≤ q, (2.37c)0 ≤ fkij , ∀i, j, k. (2.37d)where Lagrange multipliers λki , τi, and ωk correspond to constraints (2.35b),(2.35c), and (2.35d) of the original problem, respectively. Problem (2.37)is analogous to the distributed problem in [65, Sec. IV.C], but here thevariables ωk enable us to account for the DR constraints. Note that the512.3. Extension to Distributed Optimization (D-UMLJE)objective (2.37a) is locally separable over flow variables fkij. In other words,nodes can optimize the flow variables by exchanging the Lagrange multipliersλki and τi only between their neighbors. However, this fact does not hold forthe variables q and ρk, and the Lagrange multipliers ωk. Hence, problem(2.37) is a partially separable distributed optimization [65]. In order to map(2.37) to its fully distributed equivalent, we need to define local variables qiand ρki and solve the following optimization:minqi,rki ,fkij∑iq2i + ∑i,j,k(fkij)2 +∑i,kωki (ρki − ζk)+∑i,kλki−rki −∑jfkji +∑jfkij+∑iτi∑kIsikEsTs+∑jfkjiErx∑jfkij(Ep + Etx)−qiEi)+∑i,jΛij(qi − qj) +∑i,j,kΥkij(ρki − ρkj ) (2.38a)subject to 0 ≤ rki ≤bmaxTs, ∀i, k (2.38b)0 ≤ qi, ∀i, (2.38c)0 ≤ fkij, ∀i, j, k, (2.38d)where the objective is summed over the newly-defined local variables, andthe last two terms in the objective are inserted in order to force the localvariables qi and ρki to be equal to their global value. After this modification,every single term in the objective (2.38a) is separable over all variables qi,522.3. Extension to Distributed Optimization (D-UMLJE)rki , fkij and Lagrange multipliers λki , τi, ωki , Λij , Υkij . However, note that thevalue of ζk, which is independent of local variables, needs to be broadcastedto all nodes whenever a significant change in θˆk is observed, and thereforeD-UMLJE is not fully distributed in the strict sense. But since D-UMLJE isdistributed as far as the solution of the optimization problem is concerned,we refer to D-UMLJE as a distributed solution similar to [65].The distributed problem (2.38) is solved using the subgradient method.At each iteration, the sensor si solves the localized part of (2.38) with onlythe terms involving its own variables using the current values of Lagrangianmultipliers obtained from the previous iteration. Mathematically, at itera-tion `qi(`) = argmin0≤qi≤Qq2i − qiEiτi +∑j∈Ni(Λij − Λji) , ∀i,fkij(`) = argmin0≤fkijK∑k=1(fkij)2 +K∑k=1fkij((λki − λkj)+ τi(Ep + Etx) + τjErx) , ∀i, j ∈ Ni,rki (`) = argmin0≤rki ≤ bmaxTsρkiωki +∑j∈Ni(Υkij −Υkji)− rki λki), ∀i, k, (2.39)where Q is a loose upper bound for qi and all the terms in right hand sideare from iteration `−1. Also, according to the definition of ρk in (2.31), thevalues of ρki (`) are updated asρki (`) =( 1ρki (`− 1)− 1piki (`− 1)+ 1piki (`))−1, (2.40)532.3. Extension to Distributed Optimization (D-UMLJE)where piki (`− 1) and piki (`) are the variances corresponding to rki (`− 1) andrki (`) defined in (2.5). We observe that optimization over qi, fkij, and rkitakes place separately. In addition, the optimization for qi and fkij are in theform of a quadratic functions, for which closed-form solutions exist.Finally, the update rules for Lagrange multipliers based on the subgra-dient method are given byωki (`) =(ωki (`− 1) + u(`− 1)(ζk − ρki))+,λki (`) = λki (`− 1) + u(`− 1)rki +∑jfkji −∑jfkij ,τi(`) =(τi(`− 1) + u(`− 1)(qiEi −∑k(IsikEsTs−∑jfkjiErx −∑jfkij(Ep + Etx)+,Λij(`) = Λij(`− 1) + u(`− 1) (qi − qj) ,Υkij(`) = Υkij(`− 1) + u(`− 1)(ρki − ρkj), (2.41)where u(`) is a decreasing function of `, and (.)+ maps the negative values to0 [10, 65]. Note that the Lagrange multipliers are updated using the resultsof optimizations in (2.39) at the same iteration. The convergence of theabove-mentioned subgradient method to the optimal solution of the problem(2.38) can be shown using the same arguments as [65]. Furthermore, strongduality holds between the UMLJE (2.35) and the un-regularized D-UMLJE(i.e., (2.38) with  = 0). Hence, choosing a small regularization weight allows us to closely approximate the optimal solution of the UMLJE. (See542.3. Extension to Distributed Optimization (D-UMLJE)[65, Sections IV and V] and references therein for further details.)2.3.2 Discussion2.3.2.1 Overhead ComparisonAs stated earlier, both UMLJE and D-UMLJE schemes incur signallingoverhead for exchanging the information with the sink or their neighboringnodes. The major overhead in UMLJE comes from the initial collection ofSINR values in the sink. Also, the optimized data need to be sent by the sinkto each node. Hence, we have O(Γ) two-way transmissions between nodesand sink per node, where Γ is the average network depth, i.e., the averagenumber of hops that a node needs for connecting to the sink. On the otherhand, D-UMLJE only requires O(E) communications per node per iterationfor exchanging optimization variables, where E is the average number ofneighbors of a node in the network. For a fixed density, Γ grows with networksize N , but E is independent of N , which renders D-UMLJE scalable withregards to message exchange for optimization, and thus better suited thanUMLJE for larger networks. However, denser topologies would lead to anincreased packet exchange between neighbors for local optimization in D-UMLJE. Finally, as mentioned above, K variables ζk in D-UMLJE and theoptimization results in UMLJE need to be broadcasted by the sink.With regards to computational complexity, the problem (2.35) is morecomputationally-involved than each round of the distributed optimizations(2.39)-(2.41). Specifically, solving the convex optimization (2.35) in a cen-tralized manner has a computational complexity of O(N3), while the com-552.3. Extension to Distributed Optimization (D-UMLJE)plexity of each distributed update iteration is O(1) at every node. Oursimulations indicate that the number of iterations needed for D-UMLJE toconverge is typically O(N). Hence, unless the sink has considerably morecomputational resources than the other sensor nodes, D-UMLJE is prefer-able in terms of complexity.2.3.2.2 Dynamics of θkIf no prior knowledge is available, θˆk can be initialized arbitrarily. (For thenumerical results reported in the next section, we initialize it as 0). Throughthe choice of the forgetting factor δ, we can trade-off speed of convergencetowards the true value θk and steady-state accuracy of the estimate. How-ever, an uninformed initialization of θˆk is only needed at a first acquisition,then this parameter can be tracked. This also means that δ could be chosensmaller during acquisition, and then larger in the tracking phase. Since up-dates of the estimate of θk also lead to broadcasts from the sink for updatingζk in D-UMLJE and of optimization results in UMLJE, there is a tradeoffbetween tracking accuracy of θk and energy consumption for communicatingparameter updates. The coherence time of θk should also be larger than thetime needed for the iterations in D-UMLJE convergence. Assuming thatthe values of θk remain constant during at least one sampling interval, D-UMLJE should converge within a fraction of Ts. Since the iterations involveone-hop communication, the O(N) iterations needed for D-UMLJE conver-gence are fast, and this assumption is practical for a properly chosen valueof Ts based on the event type and the network size.562.4. Performance Evaluation2.4 Performance EvaluationIn this section, we examine the performance of the proposed UMLJE andD-UMLJE approaches and compare them with previously proposed max-imum lifetime and event detection methods, namely, MERG [69, Alg. 2],MLB [70], and URFP [81, Figure 2]. Recall that MERG finds the minimumenergy routes that satisfy the DRs. The best route is obtained by maximiz-ing a lower bound for lifetime. URFP connects the source nodes to the sinkthrough the links with the highest data rates. Finally, MLB tries to maxi-mize an upper bound for lifetime by decoupling the quantization and routingproblems. Since the decoupled routing problem in MLB is identical to therouting problem in URFP, MLB and URFP use the same set of routes. Wealso note that for URFP and MERG, there is no notion of quantization bitsbki , and we equally divide the required bits between the nodes in the sensingrange of an event. In the simulations, we always apply the interference-freescheduling to MERG, MLB and URFP.Table 2.1 summarizes the parameters used for the simulations. For theUWB channel model, the non-line-of-sight (NLOS) indoor office environ-ment is assumed [148]. The energy consumption parameters are chosenaccording to a typical UWB device [41, 151]. In the simulations, the num-ber of nodes varies from N = 10 to N = 50 for detecting K = 2 events.Unless otherwise specified, all sensors are assumed to experience the samenoise variance, and the default detection requirements are set to ηk = 0.90and νk = 0.10. We assume that the parameters θk remain constant withan SNR of θ2kσ2i= 37.0 dB ∀i, k, and are perfectly estimated, i.e., θˆk = θk,572.4. Performance EvaluationTable 2.1: Simulation Parameters for Lifetime MaximizationParameter Value Parameter Valueγ1 2.0 γ2 3.07d0 4 m g −60 dBG 1 D 12 mPtx −14.3 dBm Ts 1 Sec.Erx 2.5 nJ/bit Ep 10 pJ/bitEi 10 J Es 10 nJW 1.0 GHz σ2i −84 dBmK 2 - 5 N 10 - 50δ 0.9 χ 0.08Simulation runs 100 bmax 12 bits max{0.1, exp(−`10 )} u(`) max{0.01, 0.5√`}M2σ2 50.0 dBθ2σ2 37.0 dBk = 1, . . . ,K.2.4.1 A Sample ScenarioWe first consider an example with N = 25 nodes and K = 2 events shownin Figure 2.4. In this figure, sensor nodes are represented by circles, and582.4. Performance Evaluation0 5 10 15 20 25 30051015202530[8](8)[8](8)(24)[8](17)(17)(17)(17)[9](9)[8](17,24)(17,24)(17,24)(17,24)X (m)Y (m)e1e2(a)0 5 10 15 20 25 30051015202530[8](8)(24)(8)(24)(24) (24) [8][8](17,24)(17)(17)(17)(17)[9](8)[8](17)(17)X (m)Y (m)e2e1(b)0 5 10 15 20 25 30051015202530(6,9)(5,8) [8](3)(5)(0,5)(4,2)(2,0)(0,3)(1,1)(0,6)(3,2)[8](0,3)(0,4)(4)(5,2) (3)(0,6) (5)[8](3,4)(3,3)(2)(2)(4)(4,0)(0,3)(3,0)(5,0)(2)(5)(8)(6,0)(0,4)(2,4)[9][8](3,5)(3,3)(5,0)(0,4)(2,0)X (m)Y (m)e1e2(c)Figure 2.4: Comparison between routes (a) URFP, (b) MERG, and (c)UMLJE. N = 25 sensor nodes (circles) detecting K = 2 events e1, e2(squares) with DRs νk = 0.03, ηk = 0.97. The MLB approach in the homo-geneous networks chooses the same routes as URFP. The sink is located at(0,0), and the squares at (30,0) and (30,30) represent the location of events.The numbers in brackets show the optimal number of quantization bits bkiat each node and the numbers in the parentheses show the amount of flow inthe link for each event. Each line’s thickness is proportional to the amountof flow on the corresponding link. In (c), arrows are used for indicating theflow directions in the network.the events, which are located at the right corners, are identified by thesquares. The sink is located at the lower left corner. For this example,592.4. Performance Evaluationwe apply the interference-free scheduling with detection requirements of(ηk = 0.97, νk = 0.03). The set of routes found by URFP, MERG, and theproposed UMLJE are shown in Figures 2.4(a), 2.4(b), and 2.4(c), respec-tively. As stated previously, URFP routes also represent the MLB routes.The numbers in the brackets in Figure 2.4 show the number of quantizationbits bki at each node and the numbers in the parentheses show the amountof flow in the link for each event. Each line’s thickness is proportional tothe amount of flow on the corresponding link. In Figure 2.4(c), arrows areused for indicating the direction of flows in the network.As can be seen from Figure 2.4(c), the total flow for jointly detecting e1and e2 is completely distributed between the nodes in the network core, i.e.,the nodes in the transmission range of the sink. Specifically, in UMLJE thereare 4 nodes that transmit to the sink, while in Figures 2.4(a) and 2.4(b)only 1 node transmits to the sink. The balance of flows in the networkcore causes this nodes to run out of energy almost at the same time, andthus avoids the bottleneck problem. Note that, following the arrows inFigure 2.4(c), it can be observed that UMLJE directs a fair proportion offlow generated from e1 downwards, in order to balance the flow between thethree core nodes that carry traffic from this part of the network. Note that inUMLJE, the number of quantization bits for estimating an event may varyamong sensors. This is because UMLJE jointly optimizes the quantizationand routing problems, hence quantization bits are adjusted according tothe optimal routes. On the other hand, MLB decouples the quantizationproblem and thus the quantization bit assignments are independent of theroutes. Since the network is homogeneous, i.e., noise variances are the same,602.4. Performance EvaluationMLB assigns the same number of quantization bits to different sensors.2.4.2 Lifetime ComparisonFigure 2.5 compares the maximum lifetime obtained from UMLJE and D-UMLJE with K = 2 events when the number of nodes vary from 10 to20 under the interference-free scheduling CU. In D-UMLJE, a node stopsits local updates if for all variables the difference between the updated andprevious value is less than 0.1% in ten consecutive iterations. This stoppingcriterion could be relaxed for an earlier stop, and to tradeoff complexityand energy consumption for optimization with performance and lifetime forevent detection. As can be seen, the optimal value of D-UMLJE is very closeto that for UMLJE. This fact is expected due to the strong duality betweenUMLJE and un-regularized D-UMLJE [65]. The small gap is due to theregularization weight. Hence, we provide a powerful lifetime maximizationsolution that can be implemented in a distributed manner.It is worth mentioning that the absolute values of the reported lifetimein Figure 2.5 and other figures in this section are based on the parame-ters listed in Table 2.1, in particular the sensing interval of Ts = 1 secondand the initial available energy of Ei = 10 Joules at the sensor batteries.These values are provided as an example for the purpose of performancecomparison, and vary when the parameters are adjusted depending on theapplication. For example, changing the sensing interval to 1 hour providesa gain of 3600 in the lifetime. There are also other parallel approaches thatcan be employed to further improve the lifetime, for example, by providingsleeping mechanisms for the sensors [49], and/or by energy harvesting from612.4. Performance Evaluation10 12 14 16 18 2022.052.12.152.22.25 x 104Number of nodes, NLifetime (sec.)UMLJE (CU)D−UMLJE (CU)Figure 2.5: Network lifetime of UMLJE and D-UMLJE as a function ofnumber of nodes for K = 2 events.the environment [152]. UMLJE and D-UMLJE can also support these ex-tensions by solving a new optimization based on the updated set of activesensors, and/or their updated values of Ei.For network sizes of 10 to 50 nodes, we compare the performance of D-UMLJE with URFP (also MLB) and MERG in Figure 2.6. In this figure, thelifetime of D-UMLJE with both lower and upper bounds of link capacities(CL, CU) are shown. We observe from Figure 2.6 that the lifetime obtainedusing D-UMLJE is significantly improved by increasing the number of nodesand thus node density, since in a network with larger number of nodes, theoptimization is able to find more paths towards the sink and balance energyconsumption among them. On the other hand, MERG fails to grab this op-portunity, since after satisfying the DRs, MERG always chooses a minimumenergy route regardless of its load, which is clearly not a lifetime-optimal622.4. Performance Evaluation10 20 30 40 5000.511.522.533.54 x 104Number of nodes, NLifetime (sec.)D−UMLJE (CU)D−UMLJE (CL)URFP and MLBMERGFigure 2.6: Network lifetime of MERG, URFP and D-UMLJE as a functionof network size N for K = 2 events.approach in the presence of multiple events. Although the lifetime in URFP(also MLB) is slightly improved by increasing N from 40 to 50, the overalllifetime is significantly lower than that for D-UMLJE due to the fact thatURFP sacrifices the lifetime by finding the routes with higher capacities.This also shows the disadvantage of MLB, which tries to maximize a looseupper bound on lifetime based on the MSE requirements.It can also be seen from Figure 2.6 that the lifetime of the proposedmethod with interference-free scheduling (CU) is larger than that for maxi-mum interference scenario (CL), since in the latter the consumed transmis-sion energy per bit is higher.Figure 2.7 compares the lifetime of D-UMLJE, URFP (also MLB), andMERG for different DRs ζk in a network with N = 25 nodes and K = 2events under interference-free scheduling. Note that, as explained in Sec-632.4. Performance Evaluation−62 −60 −58 −56 −540.81.11.41.722.32.6 x 104ζk (dBm)Lifetime (Sec.)D−UMLJE (CU)URFP and MLBMERG(0.99,0.01) (0.95,0.05) (0.90,0.10)(0.86,0.14) (0.82,0.18)Figure 2.7: Network lifetime as a function of DRs for N = 25 nodes andK = 2 events. A smaller value of ζk corresponds to a stricter DR, which isshown as (ηk, νk) for each point.tion 2.2.2, any value of ζk can be mapped to a specific DR at a given eventSNR based on (2.31). These corresponding values for each ζk are also shownin this figure. Note that a larger ζk corresponds to a looser DR and hence asmaller generation rate. Therefore, lifetime increases as ζk increases. As canbe further seen from Figure 2.7, for a given DR, the lifetimes of URFP, MLB,and MERG are significantly lower than that for D-UMLJE. This shows thatD-UMLJE is able to find the best routing and quantization strategy for thegiven DR.Figure 2.8 shows the detection rate achieved in a network. The detectionrate should ideally match to the desired ηk assigned in the optimization,but because of the quantization of observation variables, it deviates from itsideal value. As can be seen in Figure 2.8, the achieved detection rate in oursimulations is larger than the assigned value of ηk and is very close to ηk for642.4. Performance Evaluation10−2 10−110−210−11−ηk1−P d  AchievedFigure 2.8: Achieved detection rate as a function of the desired detectionprobability ηk. Dotted line shows the 45◦ line for reference.higher values, because more bits are used for reporting an event, and thusthe Gaussian approximation is tighter.2.4.3 Convergence of D-UMLJEIn this section, we present some simulation results to illustrate the conver-gence properties of D-UMLJE. Considering network of sizes of N = 10, 25,and 50, and K = 2 events, we plot the variables qi and ρki , normalized totheir final values, as a function of the iteration number in Figure 2.9. Fig-ure 2.9(a) shows the evolution of qi for two selected sensors for each networksize, and Figure 2.9(b) provides plots of ρki for one selected sensor for eachnetwork size. As can be seen, ρki generally converges faster than qi. In par-ticular, after about 100 iterations, the values for ρki are practically convergedto their final value, regardless of the network size. This is because the vari-ables ρki are only updated by the nodes in the sensing range of ek, and thus652.4. Performance Evaluation0 100 200 300 400 500 600 700012345Iteration NumberNormalized q iN=10, s2N=10, s3N=25, s2N=25, s3N=50, s2N=50, s3(a)0 20 40 60 80 1000.90.920.940.960.981Iteration numberNormalized ρik  N=10, s2N=25, s2N=50, s2(b)100 200 300 400 500 600 7000.20.40.60.811.2Iteration NumberNormalized dual function valueN=10N=25N=50(c)Figure 2.9: Convergence of (a) qi, (b) ρki , and (c) value of dual function insample networks of sizes N = 10, 25, 50, and with K = 2. The values arenormalized to their optimal value.there is no scalability issue with regards to network size N . Compared tothis, the convergence of qi requires a larger number of iterations and theconvergence time increases with network size. Balancing the network trafficby adjusting the local variables qi through local message passing eventuallyinvolves an information exchange throughout the entire network.Figure 2.9(c) shows the convergence of the dual value (2.38a) normalized662.5. Conclusionsto its optimal for three scenarios of network sizes of N = 10, 25, and 50.As can be seen, the convergence is fairly fast, i.e. nodes can find a solutionclose to the optimal one after few iterations. As expected, more numberof iterations is needed for convergence in larger networks. Figures 2.9(a)to 2.9(c) also indicate that, since only local communications are performedin each iteration, the time needed for the convergence of the dual functionand variables would be less than the coherence time of the events.2.5 ConclusionsWe have investigated the optimization of operational lifetime in event de-tection sensor networks using UWB communication. The specific sensornetwork task considered assumed sensing events with known locations un-der given detection requirements. We have assumed UWB signal propertiesand a simple MAC layer (no power control, random access), and we haveconsidered variable generation bit rates at the sensors, which made it possi-ble to tradeoff detection accuracy with energy consumption for transmission.Given this setup, we have formulated a convex optimization problem, whichcan be solved using standard methods at a central node, preferably the net-work sink. Moreover, we have provided a distributed method, which sharesthe computational load among the network nodes and requires mostly lo-cal communication among neighboring nodes. Numerical results show thatour UWB-based maximum-lifetime joint event detection (UMLJE) approachand its distributed version are able to efficiently find the routes for maxi-mum operational lifetime and achieve significant performance gains over672.5. Conclusionspreviously proposed methods.68Chapter 3Robust Localization inWireless Sensor NetworksAfter considering the lifetime maximization in Chapter 2, we now focus onthe WSN localization problem. The location estimates obtained from theformulations in this chapter are a pre-requisite for many WSN enhance-ments, including the algorithms presented in Chapter 2.As explained in Section 1.4.1, ranging information can be easily obtainedin USNs using a two-way ranging technique between two nearby UWB sen-sors (see Figure 1.3 and Equation (1.2) for details). These ranging measure-ments can then be passed to a localization algorithm in order to determinethe location of sensors [153]. Hence, the algorithms presented in this chap-ter for a general WSN model are also applicable to the USN model used inChapter 2.Node localization is in general a difficult task in WSNs in which the rang-ing measurements are subject to errors and anchor positions are subject touncertainty. In this chapter, the robust localization problem is formulatedusing the maximum likelihood criterion under an unbounded uncertaintymodel for the anchor positions. To overcome the non-convexity of the result-69Chapter 3. Robust Localization in Wireless Sensor Networksing optimization problem, convex relaxations leading to either semi-definiteprogramming (SDP) [110] or second order cone programming (SOCP) [106]can be obtained.The comprehensive study by Tseng [106] investigates the SOCP andSDP formulations for the localization problem and studies several interestingproperties, such as the relation of the SOCP and SDP solutions to the convexhull of anchors, conditions on uniqueness of the solutions, characterizing theoptimal objective values, and how to make the formulations distributed.Tseng further shows that there is a tradeoff between SDP and SOCP interms of complexity and localization accuracy. While SDP provides a tighterrelaxation and hence results in a better localization accuracy compared toSOCP, SOCP has a lower computational complexity and takes a shorter timeto solve. The lower complexity of SOCP is because for a given problem, thenumber and size of variables and constraints required for solving SOCPare smaller than those required for solving SDP. This tradeoff motivatesthe design of mixed SDP-SOCP algorithms which benefit from the betteraccuracy of SDP and the lower complexity of SOCP.This chapter essentially follows the model in the SDP localization [110]and provides robust SOCP algorithms with significantly lower computa-tional complexities compared to their SDP counterpart. In doing so, ourwork specifically extends [106, 107, 110] by exploring tradeoffs between therobust versions of SDP and SOCP. Based on this extension, a mixed robustSDP-SOCP localization framework is proposed which benefits from the bet-ter accuracy of SDP and the lower complexity of SOCP. Since the centralizedoptimization involves a high computational complexity in large networks,70Chapter 3. Robust Localization in Wireless Sensor Networkswe also derive the distributed implementation of the proposed robust SOCPconvex relaxation. Moreover, we propose an iterative optimization based onthe expectation maximization (EM) algorithm for the cases where anchoruncertainty parameters are unavailable. An analysis is performed in orderto identify the set of nodes which are accurately positioned using robustSOCP, and to establish a relation between the solution of the proposed ro-bust SOCP optimization and the existing robust optimization using SDP.Finally, we utilize the properties of robust SOCP localization towards mo-bile sensor network applications, such as formation control and detection ofboundary trespassing.The rest of this chapter is organized as follows. The SOCP formulationwith unbounded anchor position uncertainty and its unambiguous localiz-ability property are presented respectively in Sections 3.1 and 3.2. We thenshow the relation between robust SOCP formulation and robust SDP andpropose a localization method based on mixing these two methods in Sec-tion 3.3. In Section 3.4, the robust SOCP formulation is extended to itsdistributed form, and an EM method for the case of unknown uncertaintycovariance is proposed. We then present another extension of SOCP formobile sensor network applications in Section 3.5. Extensive simulationsare finally presented in Section 3.6 to confirm that the robust SOCP andmixed robust SDP-SOCP provide tradeoffs between localization accuracyand computational complexity that render them attractive solutions, espe-cially in networks with a large number of nodes.713.1. Sensor Localization Framework3.1 Sensor Localization FrameworkWe consider a sensor network that consists of a set of anchors, Na, and a setof general sensor nodes Ns. We denote N = Ns ∪Na as the set of all nodesin the network, and xoi as the vector that contains the actual coordinates ofa node i ∈ N . Furthermore, we denote the number of anchors by k .= |Na|and the total number of nodes by m .= |N |. Although we assume two-dimensional coordinates in this paper, the extension to higher dimensions isstraightforward.The sensor network can be represented by an undirected graph G =(N , E), where N is the set of all sensors as defined above, and E is the setof links. A link (i, j) ∈ E if nodes i, j are neighbors, i.e. they are in thecommunication range, Rc, of each other: doij.= ‖xoi − xoj‖ ≤ Rc. Similar to[110], we assume that E does not include anchor-anchor links. Because oferrors in the ranging measurements, the estimated distance between nodesi and j can be written asdij = doij + eij . (3.1)The measurement error eij is modeled as a zero-mean Gaussian randomvariable with variance σ2ij [110]. We denote D as the set of all availablenoisy measurementsD = {dij | (i, j) ∈ E}.3.1.1 Localization with Perfectly Known Anchor PositionsLet us first assume a sensor network in which the anchor positions are per-fectly known. Given the anchor positions xoi , i ∈ Na, and the set of noisy723.1. Sensor Localization Frameworkmeasurements D, the goal of node localization is to obtain estimates of gen-eral sensor node positions, xi, i ∈ Ns, that minimize the sum of squaredmeasurement errors based on the maximum likelihood criterion:minxi,i∈Ns∑(i,j)∈E( ‖xi − xj‖ − dij )2 . (3.2)Since this optimization problem is non-convex and in its general form NP-hard to solve [88], convex SOCP and SDP relaxation techniques have beenapplied to (3.2) and its variants in [105, 106, 108–110, 114].3.1.2 Localization with Anchor Position UncertaintyIn practice, perfect knowledge of anchor positions may not be available. Inmany scenarios, the anchor positions are obtained using global positioningsystem (GPS) and thus subject to estimation errors, which usually are mod-eled as Gaussian random variables [104, 110, 154, 155]5. Accordingly, theuncertain anchor positions are given byai = xoi +wi, i ∈ Na, (3.3)where the position uncertainty of the ith anchor, wi, is a zero-mean Gaussianrandom vector with covariance matrix Ψi.Using the anchor position uncertainty model in (3.3), our goal is to obtaina robust counterpart of the localization problem in (3.2) that explicitly takes5For example, the GPS performance standard [155, Section A.5.4] argues that thelong-term user ranging errors can be reasonably approximated by a zero-mean normaldistribution.733.1. Sensor Localization Frameworkinto account the uncertainty in the anchor positions. We note that the robustproblem involves the refinement of the anchor positions. Following [110], weconsider a maximum likelihood estimation (MLE) approach for xoi , i ∈ N ,and examine the probabilityP (D, {ai} | {xi}) = P (D| {xi}) × P ({ai} | {xi})=∏(i,j)∈E1√2piσijexp(− ( ‖xi − xj‖ − dij )22σ2ij)×∏i∈Na1√2pi |Ψi|exp(− (ai − xi)T Ψi−1 (ai − xi)2)(3.4)By taking the logarithm of (3.4), the robust localization problem can bewritten asminxi, i∈N∑(i,j)∈E( ‖xi − xj‖ − dij )2σ2ij+∑i∈Na(ai − xi)TΨi−1(ai − xi). (3.5)Similar to the optimization problem in (3.2), the robust localization problem(3.5) is non-convex. To obtain an SOCP relaxation of (3.5), we first writethe optimization problem in the following equivalent form:min{xi},{tij},{si}∑(i,j)∈Et2ij +∑i∈Nas2i (3.6a)subject to gij |‖xi − xj‖ − dij| ≤ tij, (i, j) ∈ E , (3.6b)‖Ψ−1/2i (ai − xi)‖ ≤ si, i ∈ Na, (3.6c)where gij .= 1σij . By defining a vector u as the concatenation of variables in743.1. Sensor Localization Frameworkthe objective, i.e.,u.= [tij (i, j) ∈ E , si i ∈ Na] ,we can write (3.6) as the following equivalent epigraph form:vsocp .= min{xi},u,{qij},vv (3.7a)subject to ‖u‖ ≤ v, (3.7b)gij |qij − dij | ≤ tij, (i, j) ∈ E , (3.7c)‖Ψ−1/2i (ai − xi)‖ ≤ si, i ∈ Na, (3.7d)‖xi − xj‖ = qij , (i, j) ∈ E . (3.7e)Finally, a convex SOCP relaxation of the robust localization problem in(3.7) can be obtained by relaxing the equality constraint (3.7e) to inequality‖xi − xj‖ ≤ qij, (i, j) ∈ E . (3.8)Substituting (3.7e) with (3.8) results in a standard SOCP program whichcan be solved using an interior point algorithm [10].In the special case of perfectly known anchor positions, i.e. xi = ai =xoi , i ∈ Na, (3.7) reduces6 to the standard SOCP formulation in [106]. Thebounded uncertainty model in [114] is another special case of (3.7) by settingΨi = I2 and si = δ, where δ is the given uncertainty bound. Also note thatSOCP location estimates always lie within the convex hull of the anchorpositions, which is not in general true for the SDP solution [106]. It is also6We should point out that the objective function of SOCP relaxation in (3.5) followsthe MLE approach [110] and is slightly different from that of [114].753.2. Unambiguously Localizable Nodesworth mentioning that the sensors in (3.7) can be viewed as anchors withno prior information.3.2 Unambiguously Localizable NodesHaving formulated the robust SOCP localization problem (3.7), in this sec-tion we provide necessary and sufficient conditions for identifying the set ofuniquely localizable nodes in the robust SOCP case.A node i is called unambiguously localizable if the minimum value of(3.7) is achieved for only a unique value of xi. In other words, unambiguouslocalizability of a sensor node i means that its estimated location is invariantover all solutions, which is in fact a property of the convex optimization thatis being used. Note that this definition is different from the definition of“unique localizability” from the viewpoint of network rigidity in the absenceof noise, for example in [87, 88]. Here, the term unambiguously localizablerefers to the set of nodes whose estimated locations are invariant over allsolutions of the robust SOCP problem (3.7) [106, 107].Let B = {(i, j) ∈ E s.t. ‖xi−xj‖ = qij} be the set of links which satisfythe SOCP relaxed constraint (3.8) with equality for every relative interiorsolution7 to the robust SOCP problem. We hereafter refer to the links inB as tight links, and to the corresponding nodes as tightly-connected nodes.We also denote the convex hull of anchors as C{Na} , or more generally theconvex hull of a set of points S as C{S}. The set of tightly-connected nodes7A relative interior solution lies inside the relative interior of the solution set. In ourcase, all solutions which satisfy the remaining constraints corresponding to E − B withstrict inequality are relative interior solutions.763.2. Unambiguously Localizable Nodesis denoted byM.Tight links are essentially indicators of less uncertainty in the optimiza-tion problem, since the optimization has found a unique optimal value fortheir corresponding nodes. In fact, Tseng [106] shows that the tightly-connected nodes are accurately localized in the sense that their localizationerror is less than the square root of their average link measurement errors.Furthermore, it is mathematically proved that, for the case of perfectlyknown anchor positions, the set of unambiguously-localizable nodes are ex-actly those which are tightly-connected. In other words, the optimizationsolution for not tightly-connected nodes is not unique. In these situations,the localization algorithm can return any of the solutions, for example (andas in our simulations) the analytic center solution which corresponds to thecenter of the solution set. Mathematically, the product of all slack vari-ables corresponding to non-tight constraints is maximized at the analyticcenter solution. Geometrically, the analytic center solution has the maxi-mum “distance” to the solution set boundaries. The nodes which are nottightly-connected, and hence their location estimates are not unique, can befurther re-localized using the combined method presented in Section 3.3.2for more accuracy.In order to extend the above-mentioned relation between uniqueness ofthe solution and tightly-connected nodes to the robust case, we note that inthe robust SOCP the ith anchor position can vary in an area around ai andthe proof of [106] for unambiguous localization does not directly apply. Infact, here we first need to establish that all of the anchors are unambiguouslylocalizable.773.2. Unambiguously Localizable NodesProposition 3.1. a) All anchors are unambiguously localizable in (3.7).b) A sensor node i is unambiguously localizable in (3.7) if and only if it istightly-connected, i.e., xi is invariant over all solutions⇔ i ∈ M.c) At the analytic center solution, the estimated location of all nodes lieinside the convex hull of the estimated anchor locations, i.e., all nodes onthe convex hull of the analytic center solution are anchors.Proof. See Appendix A.Proposition 3.1a) states that solving (3.7) leads to an unambiguous lo-cation for anchors. This is due to the availability of a prior on the anchorpositions. In fact, if we also had a prior of the same form for sensors,Ψ−1/2i (ai − xi), i ∈ Ns, then all sensors would have been unambiguouslylocalizable as well. This property follows from the fact that the point atwhich the contour defined by the convex prior touches the convex solutionset of xi, i ∈ Ns, is unique [10]. In other words, adding the informationai,Ψi, i ∈ Ns to the problem leads to the selection of a unique solutionfor xi, i ∈ Ns, which has the smallest Mahalanobis distance8 to ai, withregard to Ψi. Part b) shows that the the set of tight nodes in the robustSOCP have similar properties to those in the original SOCP. An importantcorollary from combining parts b) and c) is that the sensor nodes that lieoutside the convex hull of the anchors are not tightly-connected. Moreover,part c) provides a useful characteristic for the analytic center solution ofrobust SOCP which is not in general true for its SDP counterpart.8The Mahalanobis distance of xi from ai with regard to the covariance matrix Ψi isdefined as ‖Ψ−1/2i (ai − xi)‖.783.3. Tradeoffs between Accuracy and Complexity3.3 Tradeoffs between Accuracy and ComplexityIn this section, we first analyze the relation between (3.7) and the existingrobust SDP formulation [110] in Section 3.3.1, and then devise an optimiza-tion problem for mixing the robust SOCP and SDP in Section 3.3.2 whichenables a flexible tradeoff between accuracy and complexity.3.3.1 Relation of Robust SOCP and Robust SDPRelaxationsIn general, SOCP is a special case of SDP, in the sense that we can alwaysfind an equivalent SDP for a given SOCP formulation [156]. The reversedoes not always hold, and hence we may be able to find an SDP formulationfor a problem which provides a tighter relaxation compared to the SOCP.For the non-robust localization problem, this relation is studied in [106],where it is shown that the set of all possible solutions obtained from the(tighter) SDP relaxation is a subset of all possible solutions that can beobtained by SOCP. In this section we show a similar relation between therobust formulation of SOCP (3.7) and the robust SDP in [110].Introducing X as a 2 ×m matrix whose ith column is set to xi, Y =[XTX XTX I2], γij = ‖xi − xj‖2, and Ξi = xixTi , and applying the SDPrelaxations [110] obtains the following robust SDP formulation:vsdp .= minX,Y ,{Ξi},{γij},{rij}∑(i,j)∈Eg2ij (γij − 2dijrij)+∑i∈Na(tr(Ψ−1i Ξi)− 2aTi Ψ−1i xi)(3.9a)793.3. Tradeoffs between Accuracy and Complexitysubject to γij = yii + yjj − yij − yji, (i, j) ∈ E , (3.9b)r2ij ≤ γij , (i, j) ∈ E , (3.9c)tr(Ξi) = yii, i ∈ Na, (3.9d)xi = [yim+1 yim+2]T , i ∈ N , (3.9e)ym+1m+1 ym+1m+2ym+2m+1 ym+2m+2= I2, (3.9f)Ξi xixTi 1 03, i ∈ Na, (3.9g)Y  0m+2, (3.9h)where tr(.) is the trace of a matrix, ‘ 0n’ stands for positive semidefinite-ness of an n× n matrix, and yij denotes the element in the ith row and jthcolumn of Y . The objective (3.9a) is obtained by removing the constanttermv0 .=∑(i,j)∈Eg2ijd2ij +∑i∈NaaTi Ψ−1i ai, (3.10)from the log-likelihood (3.5). The following proposition, whose proof is pro-vided in Appendix B, explains in detail the relation between robust SOCP(3.7) and robust SDP (3.9) feasible sets.Proposition 3.2. Let Ssdp = {X,Y , {Ξi} , {γij} , {rij}} be a feasible so-lution for robust SDP constraints (3.9b)-(3.9h). Then, the set of variables803.3. Tradeoffs between Accuracy and ComplexitySsocp = {{x′i} , {qij} , {tij} , {si} , v} defined asx′i = xi,qij =√γij , (i, j) ∈ E ,tij = gij |qij − dij | = gij∣∣√γij − dij∣∣ , (i, j) ∈ E , (3.11)M i = Ξi + aiaTi − aixTi − xiaTi , i ∈ Na,si =(tr(Ψ−1i M i)) 12 , i ∈ Na,v =∑(i,j)∈Et2ij +∑i∈Nas2i12,forms a feasible solution for the robust SOCP constraints (3.7b)-(3.7d) and(3.8). Furthermore, there exists a robust SDP formulation equivalent to (3.9)whose optimum value is v′sdp =√vsdp + v0 and this adjusted optimum valueis always greater than or equal to the robust SOCPs optimum value (3.7a),i.e.,vsocp ≤√vsdp + v0, (3.12)where v0 is defined in (3.10).Proof. See Appendix B.Proposition 3.2 states that the robust SDP solution set is contained inthe robust SOCP solution set if (3.12) holds with equality. Note that theequivalent SDP formulation in Proposition 3.2 is obtained by applying themapping Ξi → M i in (3.11) to (3.9), as explained in Appendix B. Themain importance of this proposition is that it extends the results of [106]for the non-robust case to the robust case. In general, robust SDP provides813.3. Tradeoffs between Accuracy and Complexitya tighter relaxation for the localization problem compared to robust SOCP.We close this section by noting that the authors in [110] have calculatedthe Cramer-Rao lower bound (CRLB) for robust localization problem. Sincethe CRLB is independent of the solution being used and we have the samenoise model as [110], the same formulation can be used here. Specifically, theCRLBs for the location variables are given by the corresponding diagonalelements of the inverse of the Fisher information matrixF (2m×2m) = Ha blkdiag−1({Ψi, i ∈ Na}) HTa+ Hs diag−1({σ2ij , (i, j) ∈ E}) HTs , (3.13)where Ha, (2m×2k).= [I(2k) 0(2k×2m−2k)]T , andHs, (2m×2|E|).= cat({[ 0 . . . (xoi − xoj)T /doij︸ ︷︷ ︸(2i−1)st and 2ith element. . .0 . . . (xoj − xoi )T /doij︸ ︷︷ ︸(2j−1)st and 2jth element. . . 0]T , (i, j) ∈ E}).That is, each column of Hs contains only 2 non-zero elements correspondingto an edge, and 0, diag(.), blkdiag(.), and cat(.) denote all-zero, diagonal,block diagonal, and column-wise-concatenated matrices, respectively.3.3.2 Combination of Robust SOCP and SDPAs suggested by Tseng [106], the SOCP and SDP problems can be mixed inorder to provide an accuracy-complexity tradeoff for the localization prob-lem. Such a combination is possible by dividing the set of nodes into two823.3. Tradeoffs between Accuracy and Complexitysets Nsocp and Nsdp and running SOCP and SDP for these sets with thecorresponding ranging information, respectively. Specifically, we haveminX,Y , {Ξi}, {γij},{rij}, {xi},u, {qij}, vv +∑(i,j)∈Esdpg2ij (γij − 2dijrij)+∑i∈Na,sdp(tr(Ψ−1i Ξi)− 2aTi Ψ−1i xi)(3.14)subject to (3.9b)-(3.9h) for Nsdp, Esdp,Dsdp,(3.7b)-(3.7d) and (3.8) for Nsocp, Esocp,Dsocp,where subscripts ‘sdp’ and ‘socp’ on N , E ,D indicate the sets of nodes,links and ranging measurements belonging to SDP and SOCP sub problems,respectively. Note that in general there is no reason to force completelyseparate problem sets, i.e. one can have Nsocp ∩Nsdp 6= ∅.The main task here is to efficiently assign the nodes to these two prob-lem sets so that the overall performance, which can be a function of bothcomputational complexity and localization accuracy, is optimized. Here wepropose a simple hybrid algorithm which is faster than robust SDP andprovides a better accuracy compared to robust SOCP.• Step 1: Solve robust SOCP problem (3.7) for the set of all sensors andanchors Nsocp = N .• Step 2: Let B be the set of tight links in the SOCP solution as definedin Section 3.2. Then, construct Nsdp = {i s. t. ∀(i, j) ∈ E : (i, j) /∈B} ∪ Na. In other words, the robust SDP is solved over the subset of833.4. Extensions of the SOCP Formulationnodes without tight links, as well as anchors.Note that the method in (3.14) is more general than the idea proposedin [106], in the sense that we allow combined optimizations where Nsdp ∩Nsocp 6= ∅. In fact, what is novel about the proposed combined method isthat we use the SOCP result over Nsocp = N to determine Nsdp. We shouldalso mention that for sparse networks, a subset of tight nodes can be keptfor step 2 to avoid graph disconnectivity [157]. This technique is howevernot used in our simulations for the combination algorithm since we haveconsidered sufficiently dense topologies.3.4 Extensions of the SOCP FormulationIn this section we provide different extensions to the SOCP formulation in(3.7) We first give a distributed version of the problem (Section 3.4.1) andcompare the complexity of different centralized and distributed localizationmethods (Section 3.4.2). Then, we consider the case that the covariancematrices of the uncertainty model, Ψi, are unknown, and propose an EMalgorithm to iteratively estimate these parameters (Section 3.4.3). Finally,we mention a gradient-based refinement algorithm which can be applied tothe results obtained by the robust SOCP or SDP methods in order to reducetheir positioning error (Section 3.4.4).843.4. Extensions of the SOCP Formulation3.4.1 Distributed SOCP-based Robust LocalizationAlgorithmAnother attractive feature of the SOCP relaxation for the robust localizationproblem is its potential for distributed implementation, which allows theoptimization problem to be divided into a number of smaller sub problemsthat can be solved locally at each node. These sub problems will dependon the position of the neighboring nodes. Hence, after the step of solvingthe sub problems locally, the nodes exchange the estimates of their positionswith neighbor nodes.A distributed algorithm was proposed for network localization with per-fectly known anchor positions in [105]. In this case, the local sub problemsare solved only at the general sensor nodes and not at the anchors. We gen-eralize this distributed algorithm to the robust localization problem withuncertain anchor positions. Consider the robust localization problem in(3.5). It can be written asminxi,i∈N∑(i,j)∈Eg2ij (qij − dij)2 +∑i∈Na(ai − xi)TΨi−1(ai − xi) (3.15a)subject to ‖xi − xj‖ = qij, (i, j) ∈ E , (3.15b)where constraint (3.15b) can be replaced by an inequality constraint forthe SOCP relaxation. Using the barrier function approach, cf. [105, 114,158], the relaxed constrained problem can be approximated as the following853.4. Extensions of the SOCP Formulationunconstrained problem:minxi,i∈N ,qij,(i,j)∈E∑(i,j)∈Eg2ij (qij − dij)2 +∑i∈Na(ai − xi)TΨi−1(ai − xi)+∑(i,j)∈EB(‖xi − xj‖2 − q2ij), (3.16a)where B(.) is a properly chosen barrier function, such as the logarithmicbarrier function B(z) = −1c log(−z) for a large constant c  1. Now, theproblem in (3.16) is partially separable and each term in the summation canbe minimized independently at each node i using only information about thepositions xj and ranging information dij of the set of its neighbor nodes,Ki [105]. Using an approach similar to the one used in the previous section,we can formulate the local sub problems to be solved at each anchor orgeneral sensor node. Specifically, for each general node i ∈ Ns, the local subproblem can be approximated by iteratively solving9minxi,tij ,qij ,vi,vi (3.17a)subject to ‖ut,i‖ ≤ vi, (3.17b)gij |qij − dij | ≤ tij, j ∈ Ki, (3.17c)‖xi − xj‖ ≤ qij , j ∈ Ki, (3.17d)where ut,i .= [tij j ∈ Ki]. Moreover, for each anchor node i ∈ Na, the local9In general, there is no analytical proof that iteratively solving (3.17), (3.18) convergesto the optimal solution of (3.7) [159], but this is usually the case in the simulations.863.4. Extensions of the SOCP Formulationsub problem can be approximated by solvingminxi,tij ,qij ,si,vivi (3.18a)subject to ‖ut,s,i‖ ≤ vi, (3.18b)‖Ψ−1/2i (ai − xi)‖ ≤ si, (3.18c)gij |qij − dij | ≤ tij, j ∈ Ki, (3.18d)‖xi − xj‖ ≤ qij, j ∈ Ki, (3.18e)where ut,s,i .= [tij j ∈ Ki, si]. We observe that the local sub problem ofeach anchor is different from that of a general sensor node due to the robustformulation of the problem. However, these two formulations can be unifiedin the same way as the centralized version, i.e. by adding priors for sensors.In an attempt to treat the case of uncertain anchor positions, the dis-tributed algorithm for the case of known anchor positions in [105] suggestedincluding the anchors in solving local sub problems. In their method, thesensors first perform a local SOCP phase to find their locations assumingperfect anchor positions. Then, the anchors use these estimations to refinetheir location information. In the third phase, the general sensors run a newround of local SOCP based on the refined location of anchors. However, thesub problems at sensors are run without taking into account the anchoruncertainty, and the sub problems at anchors are run without taking intoaccount the prior information. Hence, a better performance of the proposeddistributed robust approach is expected, as will be demonstrated in Section3.6.873.4. Extensions of the SOCP FormulationAs the final remark, we should note that the combined robust SOCPand SDP in Section 3.3.2 can be made distributed. In fact, the SOCPpart of the proposed hybrid method (3.14) can be solved in a distributedmanner using (3.17) and (3.18) above, and the SDP part can be also solvedby following the existing distributed SDP methods e.g. [109]. However,distributed SDP would require clustering for a good accuracy and can stillhave a higher complexity in a highly-connected network. Hence, we focuson the distributed robust SOCP in our simulations and provide results onlyfor the centralized combined method. When more accuracy is desired forthe boundary nodes, the proposed distributed SOCP may be replaced bythe distributed SDP with appropriate clustering methods and/or heuristicanchor refinements at the cost of a higher complexity.3.4.2 Complexity AnalysisTable 3.1 shows the number of variables and constraints for robust andnon-robust versions of SDP and SOCP in terms of number of optimiza-tion variables, and equality and inequality constraints. Also, the numberof variables and constraints for the robust edge-based SDP (ESDP) [110]and SOCP (ESOCP) [114] are shown. Since the complexity is an increasingfunction of both number and size of the constraints, for an easier comparisonwe also show a combined metric for constraints which is the product of theirsize and their number in the last column. In this table, |Ki| denotes thenumber of neighbours of node i, and |E| is the number of links in the graph.883.4.ExtensionsoftheSOCPFormulationTable 3.1: Complexity of robust and non-robust SDP and SOCP.Method Variables Equality constraints Inequality constraints Total Constraintsand their size and their size (Number × Size)Standard 2 |E|+ |N | − |Na| 0 |E| of size 2,SOCP [106] +1 |E| of size 3, 6|E|+1and 1 of size |E|+ 1Robust 2 |E|+ |N |+ |Na| 0 |E|+ |Na| of size 2,SOCP (3.7) +1 |E| of size 3, and 6|E|+3|Na|+1Continued on next page893.4.ExtensionsoftheSOCPFormulationMethod Variables Equality constraints Inequality constraints Total Constraintsand their size and their size (Number × Size)1 of size |E|+ |Na|+ 1DistributedRobust SOCP 2|Ki|+ 2 0 |Ki| of size 2,Sensors (3.17) |Ki| of size 3, and 6 |Ki|+11 of size |Ki|+ 1Continued on next page903.4.ExtensionsoftheSOCPFormulationMethod Variables Equality constraints Inequality constraints Total Constraintsand their size and their size (Number × Size)2|Ki|+ 3 0 |Ki|+ 1 of size 2,Anchors (3.18) |Ki| of size 3, and 6 |Ki|+31 of size |Ki|+ 2Distributed Robust 2|Ki|+ 3 0 2 of size 3,|Ki| of size 4,ESOCP [114], and 1 of size |Ki|+ 2 5 |Ki| +8each nodeContinued on next page913.4.ExtensionsoftheSOCPFormulationMethod Variables Equality constraints Inequality constraints Total Constraintsand their size and their size (Number × Size)Standard 2 |E| 1 of size 2, |E| of size 5, |E| of size 2, 7|E| + 4 |N |SDP [108] +(|N | − |Na|)2 and |N | − |Na| of size 3 and 1 of size |N |+ 2 - 3 |Na| +2+(|N | − |Na|)Robust SDP (3.9) 2 |E| 1 of size 2, |E| of size 5, |E| of size 2, 7 |E| + 4 |N |[110] +(|N |+ 2)2 and |N |+ |Na| of size 3 |Na| of size 3, and + 6 |Na| + 4+4 |Na|+ |N | 1 of size |N |+ 2Continued on next page923.4.ExtensionsoftheSOCPFormulationMethod Variables Equality constraints Inequality constraints Total Constraintsand their size and their size (Number × Size)Robust ESDP 2 |E| |E| of size 5, |E| of size 2,[110] +(|N |+ 2)2 and |Na| of size 3 |Na| of size 3, and 11 |E| + 6 |Na|+4 |Na|+ |N | |E| of size 4933.4. Extensions of the SOCP FormulationAs can be seen from Table 3.1, the robust SDP approach (3.9) whichconsiders anchor uncertainty [110], has 2 |E| + (|N | + 2)2 + 4 |Na| + |N |variables, while the proposed robust SOCP in (3.7) has only 2 |E| + |N | +|Na| + 1 variables. Since typically we have |E| = Ω(|N |) [106], the numberof variables grow linearly with the number of nodes (Ω(|N |)) compared to aquadratic growth (Ω(|N |2)) for robust SDP [106, 108]. This enables SOCPto solve large problems with e.g. |N | > 200 nodes.In general, interior point methods can solve SOCP more efficiently thanSDP. According to [160], each iteration of SOCP entails a cubic computa-tional complexity (O(|N |3)), while this is quartic (O(|N |4)) for SDP. Thenumbers of variables and constraints in the second and sixth rows of Ta-ble 3.1 also show that when the network is sparse, the complexity is signifi-cantly lower for robust SOCP (RSOCP) compared to robust SDP (RSDP).In the other extreme case of a highly dense network, i.e. |E| = Ω(|N |2),the number of RSOCP variables become asymptotically similar to thoseof RSDP, but the constraint metric still remains smaller by an asymptoticfactor of 6 to 7.It can be also observed from Table 3.1 that the distributed SOCP (3.17)reduces the number of variables and constraints to the order of the numberof neighbouring nodes (node connectivity). Specifically, we have |Ns| dis-tributed general node sub problems (3.17) with 2|Ki| + 2 variables and theconstraint metric of 6|Ki| + 1; and |Na| anchor sub problems (3.18) with2|Ki|+ 3 variables and the constraint metric of 6|Ki|+ 3. Since these smallsub problems are solved in parallel at different nodes, the distributed robustSOCP is scalable to the network size. This fact also holds for the robust943.4. Extensions of the SOCP FormulationESOCP [114], which has almost similar number of variables and constraintmetric to our method. We also observe that the robust SOCP has a smallernumber of variables and constraint metric compared to the robust ESDP.3.4.3 An Expectation Maximization (EM) Approach forGaussian Uncertainty with Unknown CovarianceWe have formulated the robust SOCP (3.7) for anchor position uncertaintiesassuming known covariances, Ψi, i ∈ Na. In practice, however, the sensors’knowledge about the anchor position errors may be limited, and thus thecovariance matrices might be unknown. In this case, given nm ≥ 2 mea-surements {ai,1, . . . ,ai,nm} are available, we can iteratively estimate Ψi bythe EM method as explained in the following. The nm measurements canbe obtained prior to the start of the robust localization by inquiring the un-derlying anchor location provider, e.g. GPS, cellular towers or buoys [110].The log-likelihood of the observed data given the current anchor locationand covariance matrix approximations, Ψi, can be written asLi .= log P ({ai,n} |Ψi,xi) =− nm2 log(2pi∣∣Ψi−1∣∣)− 12nm∑n=1(ai,n − xi)T Ψi−1 (ai,n − xi)(3.19)In the EM algorithm, the complete log-likelihood is first computed for agiven set of observations (E step), and then the parameters are maximizedbased on this expression (M step). These steps are iteratively executed untilthey converge to a local optimum point for the likelihood.The E step: Let Ψ`i be the estimated covariance matrix of wi at it-953.4. Extensions of the SOCP Formulationeration `. The expectation of the complete log-likelihhod function can bewritten asQi(Ψi,Ψ`i).= Exi|{ai,n},Ψ`i{logP(xi, {ai,n} |Ψ`i)}(3.20)In order to calculate the expectation in (3.20), a probability distributionof xi given ai,n and Ψ`i is needed. However, such a distribution might ingeneral be difficult to find since in our problem xi also depends on thedistance measurements in D. In order to simplify the problem, we proposethat this distribution can be approximated as δ(xi − x`+1i ), where δ is theDirac delta function and x`+1i is the anchor estimate obtained by runningthe robust SOCP optimization (3.7)10.Another possible simplification on (3.20) can be applied by writing thecomplete log-likelihood aslogP(x`+1i , {ai,n} |Ψ`i)= logP({ai,n} |Ψi,x`+1i)+ log P (x`+1i |Ψi),(3.21)and noting that the term P (x`+1i |Ψi) can be treated as a constant, since thecovariance matrix does not reveal information about the mean. Therefore,we can use (3.19) as the likelihood in the maximization step.TheM step: The maximization step involves maximizing the Q-functionafter the above-mentioned E-step,Ψ`+1i = argmaxΨ Qi = argmaxΨ(Li|xi = x`+1i)(3.22)10Note that RSOCP also requires a location estimate for anchors as input, and thus wepass our current estimates x`i as well as Ψ`i to RSOCP to obtain x`+1i .963.4. Extensions of the SOCP FormulationM stepGiven ai,1, · · · , ai,nmE stepFind x(`+1)i from robust SOCPΨ(`)i = 1nmnm∑n=1(ai,n − x(`)i )(ai,n − x(`)i )Tandx(1)i = 1nmnm∑j=1ai,jwith x(`)i and Ψ(`)iFigure 3.1: A schematic of the proposed EM algorithm. In each E step,a robust SOCP is executed and then the covariance is estimated in the Mstep.This can be performed by taking the derivative of Li with respect to Ψi andfinding the corresponding root. This results inΨ`+1i =1nmnm∑n=1(ai,n − xi) (ai,n − xi)T , (3.23)where xi is the expected location of ai which is obtained from the robustSOCP algorithm in the E step.We stop the EM algorithm at iteration `0 when L`0+1i − L`0i <  = 0.1,where the log-likelihood Li for each EM iteration is obtained from (3.19).Furthermore, the EM complexity can be approximated as O(`0 O(RSOCP)),where O(RSOCP) is the RSOCP complexity from Table 3.1. Figure 3.1shows the flowchart of the EM algorithm. As can be seen, the robust SOCPiteratively calculates new the anchor position estimations in the E step,which is utilized in the M step (3.23) for finding a better approximation973.4. Extensions of the SOCP Formulationfor Ψi. The iterations continue until the values of Li converge to a localoptimum point. As it is typical in EM, random restart points for Ψ0i canbe considered to find different local optima and choose the best. We willuse the sample covariance of measurements as the initial value of Ψ0i . It isinteresting to note that the proposed EM algorithm can be also viewed asan offline decision feedback method for estimating the covariance [161].3.4.4 Gradient Descent Refinement MethodIt is worth pointing out that an iterative gradient-descent (GD) method canbe employed in order to further refine the results obtained by the robustSDP or SOCP convex optimizations [108, Sec. V]. In each iteration ` of theGD method, the location of a sensor node is updated11 by moving in theopposite direction of the gradient. Specifically, letf(x`i) =∑j∈Ki,g2ij(‖x`i − x`j‖ − dij)2be the local value of objective for sensor i, i.e. the summation of termsin (3.5) which depend on xi, at iteration `. Then,x`+1i = x`i − α∂f(x`i)∂x`i, i ∈ Nswhere α is the step size, and the gradient is given by,∂f(x`i)∂x`i=∑j∈Ki,2g2ij(x`i − x`j)(1−dij‖x`i − x`j‖).11For simplicity, anchors are excluded from the GD refinement.983.5. Robust Localization in Mobile Sensor NetworksIt is shown in [108] that GD can refine the location of sensor nodes foundby the convex optimization. However, GD fails to provide a good solutionif a good initial solution is unavailable.3.5 Robust Localization in Mobile SensorNetworksIn this section we extend our robust SOCP solution to improve the local-ization and tracking accuracy of mobile sensor networks. These extensionsfollow from interesting properties of the robust SOCP proved in Proposi-tion 3.1, which further give rise to the following properties:Property 1: All nodes are estimated within the convex hull of theirneighbours. This fact follows from the proof of Proposition 3.1 c) and sug-gests that the localization error of a node is also a function of its neighbor’serrors. If the neighbours have a high localization error, the surroundingconvex hull is looser and thus the node may have a high error as well. Onthe other hand, a node which is estimated within a convex hull of its tightneighbours is expected to have a small localization error. We will see in Sec-tion 3.5.1 that this fact can help achieving a higher accuracy in formationcontrol.Property 2: According to the same proposition, the estimated locationof all nodes are inside the convex hull of anchors, denoted by C, at thesolution of RSOCP. More generally and less rigorously, it is observed inthe simulations that the nodes which are actually inside the convex hull,especially those in the center of convex hull, have a high probability of993.5. Robust Localization in Mobile Sensor Networksbeing tightly-connected. This is also supported by our simulations and weexpress it as a general rule of thumb without providing a mathematical proof.Section 3.5.2 uses this observation for detecting boundary trespassing in amobile sensor network.We now focus on two specific applications for mobile sensor networks,namely formation control and tracking the nodes on the boundaries, anduse the properties which are specific to SOCP in order to adjust and predictthe location of nodes for a better localization and tracking accuracy. Weperform several numerical simulations to confirm the effectiveness of ourheuristic algorithms.3.5.1 Robust Formation ControlWe now consider a mobile network in which mobile sensors should achieve adesired formation after a sequence of coordinated movements. Here, the aimis controlling the movement of sensor nodes rather than detecting it. Thecore part of formation control, form, is the SOCP formulation (8) in [122] inwhich a shape is defined by a linear constraint Ax = 0 and the objective is tominimize the total traveled distance. Note that the definition of a shape bythis constraint allows for 4 degrees of freedom, namely 2-D translation, scaleand rotation. Additional constraints for forcing a specific translation, scaleand rotation are also derived in [122]. In this formation control setting, it ishighly desirable that the nodes are initially unambiguously-localizable [115,122]. In order to do so, we provide the following solution.1003.5. Robust Localization in Mobile Sensor Networks3.5.1.1 The Tightening ProcedureWe now show that our robust SOCP can be used for providing an unam-biguous localization with low complexity. Specifically, we use the Property1 in the previous section to direct a sensor node i which is ambiguouslylocalized, or equivalently i /∈ M(t), to a location which has a better chanceof being unambiguously localized.We propose a heuristic movement to this end, in which every non-tight node moves towards the center mass of its unambiguously localizedneighbors, while tight nodes remain at their place. Mathematically, nodei /∈ M(t) chooses its velocity vector asvi(t+ 1) =1|Ji(t)|∆t∑j∈Ji(t)xj(t)− xi(t), (3.24)where ∆t is the time unit, and Ji(t) = {j : (i, j) ∈ E and j ∈ M(t)} is theset of neighbor nodes of i which are tightly-connected12 at time t. Note thatif there is a limit for speed of movement, vmax, then if ||vi(t + 1)|| > vmax,the velocity vector in (3.24) should be further normalized asvi(t+ 1)←vmax||vi(t+ 1)||vi(t+ 1).As we will see in the simulation results, this strategy is able to make almostall of the mobile sensors unambiguously localizable after only a few roundsof movements.12In the special case when |Ji(t)| = 0, i.e. node i does not have any tight neighbors, itcan move towards the center of convex hull, i.e. by setting Ji(t) = C(t).1013.6. Performance Evaluation3.5.2 Detecting Boundary TrespassingProperty 2 suggests that for a node whose actual location is outside the con-vex hull of anchors, the estimated location would be close to the boundariesof C(t). Therefore, it is reasonable to assume that if a sensor node is nottightly-connected and its estimated location is near the border of the convexhull, there is a high probability that the node is actually located outside theconvex hull. This important observation about the SOCP solution impliesthat we can distinguish those nodes which enter or exit the convex hull ofanchors in a mobile scenario. Specifically, a node is marked as “exiting” theconvex hull at time t ifi ∈ M(t− 1) and i /∈M(t) and δi(t) ≤ d,where δi(t) is the minimum distance of a node’s location estimates at timet from the edges of the current convex hull of anchors, C(t), and d is athreshold chosen according to the desired false alarm and missed detectionprobability as a function of maximum speed. Similarly, a sensor is markedas “entering” the convex hull at time t ifi /∈ M(t− 1) and i ∈M(t) and δi(t) ≤ d.3.6 Performance EvaluationIn this section we examine the performance of the proposed localizationmethods by means of simulations. We use the CVX Matlab toolbox [162] for1023.6. Performance Evaluationsolving the devised robust SOCP (RSOCP, (3.7)) and the benchmark robustSDP (RSDP, (3.9)) optimizations. The distributed method is consideredonly in the last sub-section. Simulations are performed on a computer witha 3.07 GHz processor and 8.0 GB of RAM. For the simulations, nodes arelocated in a 40 m × 40 m area. Unless specified otherwise for a simulationsetting, the communication range Rc in each topology is adjusted based on|N | for obtaining the average connectivity of |Ki| = 4 in the network. Weapply a fixed link error model with equal noise variances σ2ij for all links(i, j) ∈ E , and also a variable link error model where σ2ij = σ2d d2ij, and σ2dis the noise variance for the unit distance, i.e., a link with a longer distancehas a larger noise variance [110]. We consider the positioning mean squarederror (MSE) in dBm2,η = 10 log10(1|N |∑i∈N‖xi − xoi ‖2),as the performance criterion. A smaller positioning MSE indicates a betterlocalization performance.3.6.1 Performance of the Robust SOCPFigure 3.2 shows the RSOCP and RSDP localization results for a samplescenario from [110] with |Ns| = 10 general sensors and |Na| = 8 anchorsand the communication range of Rc = 25 m (|Ki| = 8.7). Also, the noisevariance parameter and the anchor uncertainty covariance matrix are setto σ2d = −20 dBm2 and Ψi = −10I2 dBm2, respectively. As can be seen,both robust methods are able to locate anchors and general sensors with1033.6. Performance Evaluation−20 −10 0 10 20−30−20−100102030X (m)Y (m)  Anchors, actualSensors, actualAnchors, RSDPSensors, RSDPAnchors, RSOCPSensors, RSOCPFigure 3.2: Location of nodes found by the RSDP and RSOCP relaxationsfor a sample scenario with |Na| = 8 anchors, |Ns| = 10 general sensors,Rc = 25 m (|Ki| = 8.7), σ2d = −20 dBm2, and Ψi = −10 I2 dBm2. Theblue circles and diamonds represent the actual position of general nodes andanchors, respectively; the red asterisks and plus signs show the estimatedlocations of general nodes and anchors by RSDP, respectively; and the blackdots and crosses show the estimated locations of general nodes and anchorsby the proposed RSOCP (3.7), respectively.a small error. For the nodes located close to the origin (0, 0), the RSOCPestimations are slightly more accurate than those for RSDP. For the nodescloser to the perimeter, the RSOCP error increases and becomes larger thanthe RSDP error. This trend is consistent with the fact that the nodes locatedcloser to the center of the anchors’ convex hull are generally localized moreaccurately in RSOCP. Note that this property is because of the specialstructure in RSOCP optimization and is generally not true for RSDP. For1043.6. Performance Evaluationexample, the minimum RSDP localization error in Figure 3.2 belongs tothe node located at (−11.6,−10.8) m, which is far from the origin. Inthis scenario, the total MSE for RSOCP is ηRSOCP = 1.35 dBm2, whichis somewhat higher than that for RSDP (ηRSDP = 0.50 dBm2) due to thetighter relaxation by RSDP.Table 3.2 shows the positioning MSE η, number of variables and con-straints, and the CPU time spent in different robust optimizations methodsfor solving the network in Figure 3.2. As can be seen, SOCP-based methodsare faster while SDP-based methods are more accurate. Note that althoughrobust ESDP (RESDP, [110]) has more constraints than RSDP, it is fasterbecause the constraint sizes, i.e. number of variables involved in each con-straint, are smaller.Figure 3.3 shows the average value of positioning MSE as a functionof σ2ij, for RSOCP, RESDP, and RSDP in 1000 uniformly-random networktopologies with |Ns| = 35 sensors and |Na| = 15 anchors. In order to observethe effect of anchor position uncertainties on the performance, we also plotthe MSE of the standard SOCP, which does not take into account the anchorposition uncertainties [105, 106]. We also show the MSEs after performing 50iterations of refinement using gradient descent (GD) with step size α = 10-4.Finally, the CRLB (3.13) is also shown. The value of σ2ij varies from −35 to−5 dBm2 and the uncertainty covariance is set to Ψi = −10I2 dBm2.As can be seen, RSOCP outperforms the standard SOCP in terms ofMSE. While RSDP performs better than RSOCP due to the tighter relax-ation on the problem, we also observe that for lower values of noise (i.e.σ2ij ≤ −20 dBm2), none of the convex relaxations can achieve the CRLB.1053.6. Performance EvaluationTable 3.2: Performance and complexity comparison of different robust lo-calization methods for the network in Figure 3.2. CPU runtime is definedas the time spent for solving the CVX problem, and it is measured usingMatlab’s tic and toc commands.Method Positioning MSE, Number of Number of CPU runtimeη (dBm2) variables constraints (Sec.)Standard 1.84 151 141 1.80SOCPRSOCP 1.35 167 149 2.00RESDP 0.87 590 226 2.25RSDP 0.50 590 176 2.74This trend has also been observed in other SDP and SOCP-based local-ization methods, e.g., [110, Figure 5]. The gap between the CRLB andthe MSE achieved by RSDP and RSOCP can be somewhat reduced by theGD method. Not surprisingly, the RESDP performance is in between thoseof RSOCP and RSDP. For larger values of noise, the MSEs of all robustmethods converge to the CRLB performance limit.Figure 3.4 shows the average value of η as a function of σ2d with |Ns| = 18sensors and |Na| = 12 anchors for Ψi = κ2i I2 with κ2i = {−10, 0, 10} dBm2.Also, 8 of the anchors are located at the corners similar to Figure 3.2. Asexpected, the positioning MSE is an increasing function of noise variance inall methods. The RSOCP performance is notably improved compared to the1063.6. Performance Evaluation−35 −30 −25 −20 −15 −10 −5−12.5−12−11.5−11−10.5−10−9.5−9Positioning MSE, η (dBm2)Noise variance, σ2ij  (dBm2)  Standard SOCPStandard SOCP+ GDRSOCPRSOCP + GDRESDPRSDPRSDP + GDCRLBFigure 3.3: The positioning MSE of the standard SOCP, RSOCP, and RSDPwith and without gradient descent (GD) refinement as well as the positioningMSE of RESDP in random topologies with |Ns| = 35 sensors, |Na| = 15anchors, and Ψi = −10 I2 dBm2. The CRLB are also shown.standard SOCP. Furthermore, since RSOCP is able to adjust the locationof anchors, the gap between the standard and robust SOCP becomes largerby increasing anchor position uncertainties.In order to verify the performance of the robust methods in larger scaleswe perform simulations in a 1 km × 1 km area with |Ns| = 105 sensorsand |Na| = 45 anchors and show the value of η for RSOCP and RSDP inFigure 3.5. In order to make the simulations closer to a real-life experiment,we also consider 30% chance of link failures in this scenario. In the presenceof a link failure, no ranging data is used for the corresponding link in theoptimization, i.e. nodes are not neighbours anymore. For this scenario, our1073.6. Performance Evaluation−40 −35 −30 −25 −20−15−10−50510Noise variance factor, σ2d (dBm2)Positioning MSE (dBm2 )  Standard SOCP RSOCP RSDPκ2i  = 0 dBm2κ2i  = 10 dBm2κ2i  = −10 dBm2Figure 3.4: The positioning MSE, η, as a function of noise variance factorσ2d in random topologies with |Ns| = 18 sensors, |Na| = 12 anchors, andΨi = κ2i I2, κ2i = {−10, 0, 10} dBm2. 8 of the anchors are located at thecorners.RSOCP is able to localize the network in an average of 37 seconds and ismore than twice faster than RSDP, which takes 84 seconds on average. Theresults of RSOCP MSE error provide an acceptable localization accuracy,always within 2.5 dBm2 of that for RSDP. This translates to an increase ofonly 1.4 m in the standard deviation of localization error. Note that thelocalization algorithms would run faster in a network with a lower densitycompared to the results shown above, for example when the same numberof sensors are deployed in a larger area.1083.6. Performance Evaluation20 22 24 26 28 30 32 34323334353637383940Noise variance, σ2ij  (dBm2)Positioning MSE (dBm2 )  RSOCP            (κi2 = 37.5 dBm2)RSDPRSOCP             (κi2 = 34 dBm2)RSDPFigure 3.5: The positioning MSE in a 1 km × 1 km area with |Ns| =105 sensors and |Na| = 45 anchors. A link failure probability of 30% isconsidered. The link noise variance σ2ij changes from 20 to 34 dBm2 (i.e. 10to 50 m of noise standard deviation) and Ψi = κ2i I2, κ2i = {34, 37.5} dBm2(i.e. a radius of 50 or 75 m uncertainty around anchors). The anchorpositions are randomly chosen based on a uniform distribution.3.6.2 Combination of RSOCP and RSDPNext we examine the performance of the combined RSOCP and RSDP al-gorithm introduced in Section 3.3.2.Figure 3.6 shows a sample network with |Ns| = 11 sensors and |Na| = 6anchors, displayed as blue circles and diamonds, respectively. First, RSOCPis executed over the entire network, resulting in the sensor and anchor esti-mations shown by the red squares and crosses, respectively. A threshold of10−5 is used for determining the tight links. Note that the RSOCP sensor1093.6. Performance Evaluation0 2 4 6 8 10−2024681012X (m)Y (m)  Anchors, actualSensors, actualAnchors, RSOCPSensors, RSOCPSensors, RSDPAnchors, RSDPTight linksConvex hull of RSOCP anchorsFigure 3.6: Illustration of the RSOCP-RSDP combination algorithm in asample scenario. Communication range is Rc = 5 m (|Ki| = 7.4), andthe noise variance factor and uncertainty are set to σ2d = −20 dBm2, andΨi = −10I2 dBm2, respectively.estimations always lie within the convex hull of estimated anchor positions(solid lines), based on Proposition 3.1 c). Seven of the sensors are preciselylocalized using RSOCP since they are tightly-connected. The total position-ing MSE of RSOCP is −4.07 dBm2. From the remaining four sensors whichare not tight, two are located inside the convex hull. This fact shows thata node inside the convex hull is not necessarily unambiguously localizable,while the reverse is always true according to Proposition 3.1. The remainingfour sensors, along with anchors, are re-localized using RSDP leading to theblack triangle and plus signs for sensors and anchors, respectively, and a1103.6. Performance Evaluation0.04 0.1 0.2 0.3 0.4 0.5−505101520Positioning MSE, η, (dBm2)  2442607896114CPU Time (s)Fraction of anchors |Na| / |N|RSDP (MSE)Comb. (MSE)RSOCP (MSE)RSDP (Time)Comb. (Time)RSOCP (Time)Figure 3.7: Average positioning MSE (solid lines) and time taken (dashedlines) for solving centralized RSDP, RSOCP and their combination for |N | =200 nodes as a function of the fraction of anchors, |Na||N | , with Rc = 6 m(|Ki| = 9.3), σ2ij = −35 dBm2, and κ2i = 0 dBm2. The anchor positions arerandomly chosen based on a uniform distribution.total positioning MSE of −6.22 dBm2 for the network.To further demonstrate the complexity advantage of mixed RSOCP-RSDP over pure RSDP, we also investigate a network with |Ns| = 105sensors and |Na| = 45 anchors (not shown here). In this scenario, RSOCPtakes 33.88 seconds, and unambiguously localizes 83 sensors. The remaining22 sensors along with anchors are passed through RSDP, resulting in thetotal MSE of η = 0.38 dBm2 in only 6.70 seconds. In the same scenario, pureRSDP over all network takes 75% more time than the combined algorithm(71.39 seconds) and its positioning MSE is ηrsdp = −2.46 dBm2.The average positioning MSE (solid lines) and the total time spent1113.6. Performance Evaluation(dashed lines) for RSOCP, RSDP, and the combined robust SDP-SOCPmethod in larger networks with |N | = 200 sensors are shown in Figure 3.7.Here, the percentage of anchors |Na||N | varies from 4% to 50%. Since, un-like for the results in Figure 3.4, all sensors and anchors are located basedon a uniform random distribution (i.e., no anchors are necessarily placedat the corners), RSOCP has a large MSE for small numbers of anchors.In this situation, the combination of RSOCP and RSDP performs signifi-cantly better than RSOCP taking twice as much time, while RSDP has thebest performance with three times the computation time of RSOCP. Hence,the proposed combined method is an interesting alternative to RSOCP andRSDP, especially in sensor networks with many nodes and a relatively smallnumber of anchors. It can be also observed from Figure 3.7 that as per-centage of anchors increases, both positioning MSE and computation timefor all three methods decrease. The former is due to availability of more in-formation (i.e. anchor priors) about the network, and the latter is becauseof the smaller |E| after removing anchor-anchor links which leads to fewervariables and constraints.3.6.3 The Distributed RSOCP MethodNow we consider larger network sizes for which it is preferable to use thedistributed methods for solving the localization problem. In Figure 3.8,we compare the performance of the distributed RSOCP for |N | = 100 to500 nodes with the three-phase iterative distributed method in [105]. Weconsider 10 different topologies for each value of |N | and show the scatterplots for η and computation time in Figures 3.8(a) and 3.8(b), respectively.1123.6. Performance Evaluation−7 −6.5 −6 −5.5 −5 −4.5−7−6.5−6−5.5−5−4.5η for distributed RSOCP (dBm2)η for three−phase distributed SOCP (dBm2 )  |N|=100|N|=200|N|=300|N|=400|N|=500(a)0 10 20 30 40 50 60020406080100  Time for distributed RSOCP (Sec.)Time for three−phase distributed SOCP (Sec.)m=100m=200m=300m=400m=500(b)Figure 3.8: Comparison between the proposed distributed RSOCP and thethree-phase heuristic. The scatter plots for (a) η and (b) time are shownfor 50 scenarios with |N | = 100 to 500, 40% of which are anchors, σ2d =−20 dBm2, and Ψi = −10I2 dBm2. The diagonal solid and dashed linesare the x = y identity lines.For obtaining results in this figure, Rc = 8 m, 40% of the nodes are randomlyselected as anchors, σ2d = −20 dBm2 and Ψi = −10I2 dBm2. For a faircomparison of time complexity, both algorithms are iteratively executedfor only six rounds before they converge, i.e. the three-phase algorithm isrun twice and our sensor-anchor refinement procedure in (3.17), (3.18) isexecuted three times. Note that for both distributed methods, only anchorswhich are reasonably inside the convex hull of their neighbors update theirlocations [105]. For measuring the computation time, we sum the maximumtime taken by the nodes to solve their local problems during each phase.Note that the time for communicating variables to neighbors is not takeninto account.As can be seen from Figure 3.8, in almost all cases, the proposed dis-tributed RSOCP algorithm outperforms the three-phase algorithm both in1133.6. Performance Evaluationterms of η and computation time. The former is due to the fact that ouranchor refinement step takes into account the uncertainty and is able toprovide a better position estimates for anchors. The latter is because of thesimpler structure of our anchor update problem compared to the proposedheuristic in [105]. Note that for obtaining the results in Figure 3.8, we haveused (0, 0) as the initial location of nodes. Given a sufficient number ofanchors, the distributed algorithm converges to good location estimates infew iterations, as can be seen from Figure 3.8.3.6.4 EM PerformanceFinally, we investigate the performance of the EM algorithm when the an-chor uncertainties have unknown covariance matrices. Figure 3.9 comparesthe value of η for the EM method, after different numbers of iteration withthat for the standard and robust SOCP (with known covariance). There are|Ns| = 35 sensors and |Na| = 15 anchors in the network with nm = 5 initialreadings for each anchor, σ2ij = −20 dBm2, and Ψi = κ2i I2, where κ2i variesfrom −15 to 15 dBm2. The initial readings are obtained by generating 5noisy versions of the actual anchor positions based on the actual Ψi. Ascan be seen, the positioning MSE of EM after convergence is very close tothat of RSOCP, which indicates that the EM algorithm is able to correctlyestimate the covariance matrices. On the other hand, the standard SOCPleads to a larger error, especially for larger values of uncertainty since it isunable to refine the anchor positions. For example, in Figure 3.9, the EMMSE after 3 to 5 iterations is close to its optimal value when κ2i ≥ 0 dBm2,while additional iterations are needed for smaller uncertainties.1143.6. Performance Evaluation−15 −10 −5 0 5 10 15−15−10−50510152025κ2i  (dBm2)Positioning MSE, η, (dBm2)  Standard SOCPEM, 1 iterationEM, 2 iterationsEM, 3 iterationsEM, 5 iterationsEM, 10 iterationsEM, 25 iterationsEM, convergedRSOCP with known covarianceFigure 3.9: Positioning MSE, η, for EM after 1, 2, 3, 5, 10, 25 iterations andafter convergence, compared to the standard and robust SOCP. Number ofsensors and anchors are |Ns| = 35 and |Na| = 15, respectively, and nm = 5initial readings are used in EM for each anchor. σ2ij = −20 dBm2, andΨi = κ2i I2.3.6.5 Formation ControlTo show the effectiveness of the tightening procedure in making the networkunambiguously localized, we consider mobile sensor networks with |N | ={50, 100, 150, 200} and 40% of anchors. Nodes are located in a 40 m× 40 marea, and the communication range Rc = 8m. The noise variance for rangingmeasurements is σ2d,ij = −20 dBm2, and the anchor uncertainty covariancematrix is Ψi = −10 I2 dBm2.Figure 3.10 shows the average and standard deviation of the number ofiterations, over 100 topologies for each |N |, needed for ambiguously-localized1153.6. Performance Evaluation50 100 150 2000510152025303540Network Size, |N|Number of iterationsFigure 3.10: Average and standard deviation of number of mobility iter-ations needed for making the entire network unambiguously localizable.σ2d,ij = −20 dBm2, Ψi = −10 I2 dBm2, and Rc = 8 m, |N | =50, 100, 150, 200, and 40% of nodes are static anchors.nodes to move based on equation (3.24) in order to make the entire networkunambiguously localizable. As can be seen, only a few iterations, alwayssmaller than 40, is required for making the whole network unambiguouslylocalizable. This result shows that RSOCP can be efficiently used for achiev-ing more reliability in formation control applications. Note that the nodesoutside the convex hull will eventually move into the convex hull. Moreover,the number of iterations is a decreasing function of network size, due to thefact that the level of connectivity is higher in a denser network and thus,there are fewer unambiguous spots left in the convex hull. We should pointout that according to our simulations for smaller networks in the order of20 nodes or less, not shown here, the movements based on (3.24) might1163.6. Performance Evaluation−0.04 −0.02 0 0.02 0.04 0.06 0.08−0.03−0.02−0.0100.010.020.030.040.050.06XY  perfectformloc−>formloc−>move−>loc−>formFigure 3.11: Formation of |N | = 200 mobile sensors, into a rotation of theletter G. The sensors are initially uniformly-randomly distributed in a unitsquare around (0,0). The formation with and without prior localization isshown with different colors and markers, and their corresponding perfor-mance are provided in Table 3.3.converge to a configuration where 90% or larger number of nodes in thenetwork, but not necessarily all of them, are unambiguously localized.We now use the tightening procedure for a robust formation control, asshown in Figure 3.11. We force a rotation constraint [122] (θ = 3pi4 ) butallow free scaling and translation in the formation. The sensors are initiallyuniformly-randomly distributed in a unit square around (0,0). The corre-sponding traveled time and mean square error (MSE) values for differentformation control strategies are provided in Table 3.3.In Figure 3.11, the blue crosses indicate the perfect formation that wouldhave been established if all nodes knew their actual locations. In the pres-ence of ranging noise with σ2d,ij = −50 dBm 2,∀(i, j) ∈ E , we compare the1173.6. Performance EvaluationTable 3.3: Performance of formation control with and without prior local-ization and tightening.Method Traveled distance (m) Number of MSE (dB)(tightening + formation) tight nodesDirect Formation 74.53 (0.00 + 74.53) unknown -12.29(Form.)Loc. → Form. 74.14 (0.00 + 74.14) 168 -9.78Loc. → Tight. 75.88 (2.29 + 73.59) 186 -59.91→ Loc → Form.performance of three strategies. First, directly performing the optimizationin [122] leads to the formation of red circles, with an observable deviationfrom the desired formation.Second, performing only one localization with 13 anchors (on the convexhull) and 187 sensors without performing the tightening procedure (black+ points in Figure 3.11) slightly decreases the total traveled distance buthas an adverse effect on the final formation MSE. This can be due to thefact that the number of non-tight nodes with a high error in their locationestimate is high (19 out of 168).Third, performing one round of the tightening procedure followed bythe second round of localization, the number of tight nodes is increasedfrom 168 to 186. This leads to an almost perfect formation (−59.91 dB),1183.6. Performance Evaluationand the only node (out of 187) which is not tight can be clearly seen asthe only green diamond outlier point at (0.08, 0.045) in Figure 3.11 whichfurther confirms the importance of being a tight node for a good formation.We should also mention that the formed shape in this case (green diamondpoints) is slightly shifted and scaled compared to the shape resulted fromperfect measurements (blue + points), which is possible due to the degreesof freedom in the shape constraint Ax = 0, but the rotation angle is fixedbecause of the applied rotation constraint.3.6.6 Boundary Trespassing DetectionFigures 3.12(a) and 3.12(b) show the performance of the RSOCP optimiza-tion for detecting mobile nodes which enter and exit the convex hull ofanchors, respectively. For obtaining the results, |Na| = 40 static anchorsare randomly placed in a 40 m × 40 m square area, and |Ns| = 60 sensors,with randomly selected initial locations in the same area, move for 2000 sec-onds according to a random way-point model [163], where a node choosesa uniformly-random velocity vector every 10 seconds. The communicationrange is Rc = 8 m which translates to an average node connectivity of 8.6.The maximum speed of a sensor is set to vmax = 4 m/s, and border close-ness threshold is set to d = 5 m. In these figures, the squares show theactual times where nodes enter and exit the convex hull of anchors, whilethe crosses show the detections based on RSOCP which is executed aftereach round of movement. As can be seen, RSOCP is able to detect manyof the occurrences of nodes passing the borders with a few false alarms.Quantitatively, the probability of a successful detection (both entering and1193.6. Performance Evaluation40 50 60 70 80 90 1000500100015002000Node IDTime(a)40 50 60 70 80 90 1000500100015002000Node IDTime(b)Figure 3.12: Detecting trespassing of |Ns| = 60 mobile nodes on the convexhull of |Na| = 40 static anchors, a) entering b) exiting. Squares show actualtrespassing and crosses are detections made by RSOCP. σ2d = −20 dBm2,Ψi = −10 I2 dBm2.exiting) is 83%, while the false alarm probability is 13%. As stated previ-ously, d can be adjusted for a tradeoff between probability of detection and1203.7. Conclusionsfalse alarm. To show this fact, we also tried a smaller threshold, d = 2 m,leading to a smaller probability of false alarm (7%), and a smaller probabilityof detection (60%).3.7 ConclusionsWe proposed robust and distributed algorithms for solving the localizationproblem based on an SOCP relaxation, which is computationally more effi-cient than the similar SDP methods. We analyzed the relation between therobust SOCP and robust SDP methods and provided a hybrid robust SDP-SOCP approach, which benefits from the lower complexity of robust SOCPand the better accuracy of robust SDP. The necessary and sufficient condi-tions for unambiguous localizability were also derived. Furthermore, an EMalgorithm was proposed for estimating the locations in situations where thecovariance matrices of the anchor uncertainties are unknown. Simulationresults confirmed that the proposed robust, distributed, and hybrid meth-ods based on the SOCP relaxation can be effectively used for localization inlarge networks with anchor position uncertainties.121Chapter 4Coverage Enhancement forLTE MTCAfter addressing the challenges of lifetime and localization in ad hoc WSNsin the previous two chapters, in this chapter we focus on the related conceptof machine-to-machine communications (M2M). We choose the centralizedarchitecture of LTE, and investigate the important problem of LTE coveragefor M2M.As explained in Section 1.1, M2M communication is one of the fastest-growing technologies in the field of telecommunications, and it is expectedthat the number of devices that need an M2M interface reaches hundredsof millions in the near future [5–8]. Wireless devices for M2M communica-tion generally serve applications whose quality-of-service requirements aredifferent from those handled by conventional (human-operated) LTE userequipment (UE). For example, many M2M applications require transmit-ting only infrequent and short messages (low average data rate per device)and are often more delay-tolerant compared to the human-to-human (H2H)and human-to-machine (H2M) applications. At the same time, the densityof machine-type communication (MTC) UEs can be high. Finally, due to122Chapter 4. Coverage Enhancement for LTE MTCmany similarities between M2M and WSN applications often involving (alarge number of) inexpensive battery-operated equipment without mainte-nance for long periods of time, MTC UEs need to be low cost and operatewith low power consumption.Against this background, the 3GPP standardization process has recog-nized the need for extending the LTE standard to open the network forM2M applications and to meet the specific requirements of MTC devices.In particular, 3GPP has started to integrate machine-type communication(MTC) into LTE-A starting from the tenth release (Rel-10) of the stan-dard in 2010 [137]. Additional new enhancements have been introducedin the latest release (Rel-12) to improve the performance of MTC in LTE.In particular, the definition of several service requirement classes for dif-ferent M2M applications, efficient handling of small data transmission re-quests, and device triggering have been included into LTE Rel-12. Also,several work items are in the final stages of investigation and will poten-tially appear in Rel-12 [7, 164]. These include the introduction of a new UEcategory equipped with a single antenna, limited operational bandwidth,half-duplexing frequency-division duplex, and lower transport bock sizes inorder to reduce cost.Table 4.1 shows some of the properties of the new UE category 0 (CAT0)designed for MTC in comparison to legacy UE categories in LTE. We observethat CAT0 UEs lack some of the LTE features and transmission capabili-ties for the benefit of low-cost design. While estimate cost savings are onthe order of 50% compared to CAT1 devices [164], the required signal-to-noise ratio (SNR) for achieving a desired error rate will be higher and thus123Chapter 4. Coverage Enhancement for LTE MTCTable 4.1: Comparison of some features for different LTE UE categories andLTE MTC UEs (category 0 (CAT0) devices).Category 1 2 3 4 5 0Peak rate DL 10 50 100 150 300 1-2(Mbps) UL 5 25 50 50 75 1-2Capability for physical layer functionalitiesDL QPSK, 16QAM, 64QAM AllModulation QPSK,UL QPSK, 16QAM 16QAM, QPSK,64QAM 16QAMMulti-antenna2 Rx Assumed in performance Notdiversity requirements required2× 2 MIMO Not Mandatory Notsupported required4× 4 MIMO Not Mandatory Notsupported requiredcoverage is reduced for CAT0 UEs. Coverage is particularly critical in thecontext of MTC though, as some MTC UEs are installed inside buildingsor structures with large penetration losses. Since these UEs are not mobile,124Chapter 4. Coverage Enhancement for LTE MTCmethods for coverage enhancement are necessary to provide LTE connectiv-ity. In response to this, a new coverage enhancement work item has beenapproved in the 3GPP radio access network technical specification group(RAN TSG) in June 2013 [138].In this chapter we review the coverage enhancement (CE) targets spec-ified in this group and extend one of the CE techniques that are beingconsidered for the inclusion in the standardization. For the former, we firstprovide a brief description of the LTE resource structure and the coverage inits uplink (UL) and downlink (DL) channels in Section 4.1. Then we focuson the LTE channel with the worst coverage and propose a novel method inSection 4.2 that can provide flexible CE under different network conditions,such as instantaneous link quality and number of active MTC UEs. Imple-mentation of this method does not require modifications of legacy LTE UEsand has little effect on their performance (e.g. by way of limitations to re-source scheduling), which is decisive for coexistence of legacy and MTC UEs.Overall cell spectral efficiency is also not compromised, which is importantfrom a cost per bit perspective for mobile network operators. The coverageenhancement and spectral efficiency of the proposed method is evaluatedthrough simulation results in Section 4.3.While the CE methods discussed in the following are rooted in CE forMTC, we note that their application is by no means limited to LTE CAT0UEs, and they can also be implemented for other UE categories.1254.1. Overview of Coverage in Uplink and Downlink LTE Channels4.1 Overview of Coverage in Uplink andDownlink LTE ChannelsWe first briefly review LTE physical uplink and downlink channels andpresent a summary of the current coverage in these channels. This setsthe stage for the coverage enhancement methods presented thereafter.In both of the UL and DL directions, there are different physical chan-nels which are transmitted in specific RBs of the time and frequency radioresources. The physical DL and UL shared channels (PDSCH and PUSCH)are dedicated to data exchange between the eNodeB and the UEs. The sizeof the data which is transmitted in each data transaction is called the trans-port block size (TBS), and the time taken for this transmission is referredto as the data transmission time interval (TTI). The TTI is typically equalto the duration of one subframe. The data channels are complemented bya number of control channels, including the physical DL control channel(PDCCH) for allocating physical resource blocks (PRBs) to PDSCH andPUSCH, the physical UL control channel (PUCCH) for transmitting UEresource requests and link quality information, the physical broadcast chan-nel (PBCH) in the DL, which broadcasts the information required at a UEfor joining a cell, and the UL physical random access channel (PRACH),which is used for contention-based random access for requesting a resourceallocation from the eNodeB.1264.1. Overview of Coverage in Uplink and Downlink LTE Channels4.1.1 LTE and MTC Coverage RequirementsMaximum coupling loss (MCL) is a measure for coverage in LTE channels.It is defined as the difference between maximum transmission power in thechannel and its corresponding receiver sensitivity [137]. A higher MCL valueindicates a smaller required SNR for a target block error rate (BLER), whichtranslates into a better coverage for that channel.The 3GPP study item [137] focused on identifying the LTE channels withcritical MCLs. For this, the study item considered medium data rata andVoIP applications. Table 4.2 summarizes the MCL of the above-mentionedchannels in LTE as reported in [137, 164]. It can be seen that the MCLvalues vary for different LTE channels and that the UL channels have, ingeneral, a worse coverage compared to the DL channels. The issue of cover-age imbalance is less pronounced when we consider MTC UEs. In particular,since MTC UEs will be equipped with only one receive antenna as shown inTable 4.1, a 4 dB penalty has been applied to the MCL of downlink channelsin Table 4.2. Although the study [137] targeted 20 dB of coverage improve-ment, to reduce complexity it was agreed in work item [138] that only 15 dBof CE would be targeted. This means that all MTC channels should achievean MCL of 155.7 dB. The required CEs for CAT0 devices are summarizedin the last row in Table 4.2.We have proposed different MTC CE methods for PUSCH in [165], forPDCCH in [166], and for PBCH in [167]. In the remainder of this chapter,we only focus on the PUSCH and present a transmission strategy based onspreading and bundling the data in order to achieve 15 dB CE in PUSCH.1274.1. Overview of Coverage in Uplink and Downlink LTE ChannelsTable 4.2: MCL for UL and DL LTE channels in FDD mode. eNodeB in2 transmit and 2 receive antenna configuration. UE with 1 transmit and 2receive antennas, and UE CAT0 with 1 transmit and 1 receive antenna.UL channels DL channels(valuesin dB) PUCCH PRACH PUSCH PDCCH PBCH PDSCHMCL forCategory 1 147.2 141.7 140.7 146.1 149.0 145.4Legacy UEMCL for 147.2 141.7 140.7 142.1 145.0 141.4MTC UEMCL for 155.7 155.7 155.7 155.7 155.7 155.715 dB CERequired 8.5 14.0 15.0 13.6 10.7 14.3CE forMTC UEThe reason for choosing PUSCH is two-fold. First, PUSCH is the channelwhich requires the largest CE. Second, the MTC UEs tend to send UL datamuch more often than receiving the DL data.1284.2. Coverage Enhancement in PUSCH4.1.2 LTE Channel ModelBefore moving on to the CE methods, we would like to mention that mostof the deep coverage holes in a system are due to in-building insertion lossand in this situation almost stationary MTC UEs is assumed. Therefore, inthe 3GPP RAN1 working groups, the extended pedestrian type-A channel(EPA) is used as appropriate channel model for numerical evaluations andcomparisons of results, usually with a Doppler frequency of 1, 3 or 5 Hz toaccount for a slight degree of mobility.4.2 Coverage Enhancement in PUSCHData transmitted over PUSCH is encoded with a rate-1/3 turbo encoder.The encoder output is rate-matched and arranged in four redundancy ver-sions (RVs), each of which matches the TBS. Based on this, incremental-redundancy automatic repeat request (ARQ) can be performed after eachTTI. That is, the receiver acknowledges the receipt of data, and in case of anegative acknowledgment, the next RV of the current data will be transmit-ted. The default schedule for PUSCH transmission is to transmit one RVin one TTI, and to only transmit another RV if requested via negative ac-knowledgment (NACK). Reference [137] tackles the issue of CE for PUSCHthrough TTI bundling. In TTI bundling, all RVs are transmitted at once,without waiting for a NACK. This leads to CE for delay-limited application,in particular VoIP. The current LTE standard assumes a fixed bundling sizeof 4.Since M2M applications are often delay-tolerant, we can think of combin-1294.2. Coverage Enhancement in PUSCHing bundling with repetition for CE. For example, increasing the bundlingsize from 4 to 8 means that the UE would send each RV twice. Furthermore,bundling size could be adjusted dynamically, considering the UEs need forCE and its delay tolerance [137].Given the often low data-rate and latency requirements for MTC UEs,data repetition is a generally acceptable solution to improve coverage. Butwhile a trade-off between spectral and power efficiency is mandated by prin-ciples of communication theory, repetition is often far from optimal in thesense of spectrum efficiency. An alternative to repetition is the use of spread-ing. The advantage of spreading is that it enables multiple UEs to transmitconcurrently, i.e., to perform code-division multiple-access (CDMA). There-fore, the system spectral efficiency would not be affected by using CDMA ifall code indices are used for transmission. CDMA is already used in LTE,namely for PUCCH format 3 to provide multiple user access on the controlchannel [11].In the following, we explain a method for simultaneous use of adaptiveTTI bundling and spreading for MTC CE, and we present a signalling pro-cedure for the flexible assignment of PUSCH resources to a variable numberof UEs.4.2.1 Flexible TTI Bundling with CDMA SupportOur method extends conventional LTE TTI bundling by adjusting the bundlingsize and the spreading factor used by UEs, according to the instantaneouscellular network conditions. These are defined through number of “active”MTC UEs, i.e., UEs which have data to transmit, their channel quality and1304.2. Coverage Enhancement in PUSCHFigure 4.1: A TTI bundle in our invention consists ofNB “spreading blocks”.Spreading codes of length NS are used for spreading A symbols over one ormore (F ) subframes, enabling concurrent transmission of up to NS UEs.Different spreading blocks may be scheduled non-consecutively over timeand/or frequency. Note that 2 out of 14 OFDM symbols in each subframeare unavailable for spreading since they are dedicated to transmission ofdemodulation reference symbols (DMRS) for channel estimation.thus instantaneous coverage, and the available PUSCH resources. The mainadvantage of using flexible bundling and spreading is that CE is achievedwithout overly compromising network spectral efficiency. Spreading is per-formed over REs at the same frequency, which simplifies despreading assum-ing the channel remains essentially constant over the spreading interval.Figure 4.1 shows a unit of the code-spread TTI bundling for this newPUSCH sub-frame structure. In this new structure, the coverage gain is1314.2. Coverage Enhancement in PUSCHbased on:• The spreading gain, which results from spreading a symbol over NSsingle-carrier frequency division multiple access (SC-FDMA) symbols.• The coding gain, which is achieved by bundlingNB “spreading blocks”.The value of NB can be dynamically chosen for achieving the desiredcode rate given the TBS, as it will be explained later.Spreading blocks allow us to enhance coverage based on the spreadinggain. A spreading block is defined as F ≥ 1 subframes over which a variablenumber of SC-FDMA data symbols (denoted by A) are spread, over time,using spreading codes of length NS . It can be also observed from Figure 4.1that 2 symbols per sub-carrier are reserved for demodulation reference sym-bols (DMRS) in each PUSCH subframe. Consequently, there are 14−2 = 12SC-FDMA data symbols available per sub-carrier (i.e. we have a total of144 data REs per RB), and thus we haveF = lcm(NS , 12),i.e., F is the least common multiplier (LCM) of NS and 12. Also,A = 144 MPUSCHRB F/NS ,where MPUSCHRB is the number of allocated PRBs assigned by eNodeB forPUSCH transmission.Using NS (possibly orthogonal) spreading codes, up to NS UEs canbe scheduled to transmit over the proposed structure. The value of NS is1324.2. Coverage Enhancement in PUSCHdynamically adjusted by the eNodeB based on the required coverage and thenumber of active users. Moreover, increasing NB leads to more coding andrepetition gain. Mathematically, the coverage gain offered by the flexibleTTI bundling and spreading can be lower bounded as,G = 10 log10 (NBNS) . (4.1)The exact gain in coverage is somewhat larger when combining different RVsfrom the turbo code contained in TTI bundles.Unlike spreading, coverage enhancement provided by NB block repeti-tions comes at the cost of decreasing the spectral efficiency. To see this,note that for a given modulation order (i.e. bits per symbol) of M andTBS, the code rate of bundling can be calculated as cr(NB) = TBSAMNB . Inthe special case when NB = 1, i.e. in the normal PUSCH transmission withno bundling, the code rate is TBSAM . Therefore, bundling size NB decreasesthe spectral efficiency by a factor of NB .4.2.1.1 Realistic Channel Estimation in CDMAWhen CDMA is used for simultaneous transmission of multiple users, chan-nel estimations for each individual MTC UEs is required at the receiver(eNodeB) prior to despreading and decoding the data. Since the legacy RBstructure is designed to accommodate the DMRS for only one user, we needto modify the RB structure to allow transmissions of DMRS from multipleusers. There are different solutions for achieving this functionality. For in-stance, we can introduce new REs for DMRS and assign them separately to1334.2. Coverage Enhancement in PUSCHdifferent MTC UEs. This reduces the overall spectral efficiency, since theREs that used to carry data are now assigned to reference symbols. Alter-natively, the reference symbols can be spread over the available DMRS REs.Applying this method is possible if the bundling size is large enough and ac-commodates at least NS reference symbols. Under the assumption that thechannel remains constant over the spreading interval, we can first despreadthe DMRS and use it for despreading the actual MTC UE data. In general,this assumption may not hold for the large values of NS , and the practicalgains of spreading would be less than the predicted 10 log10 (NS) due to theeffect of noise on the loss in the orthogonality between the CDMA codes.4.2.2 Protocol for Flexible TTI bundling and CDMAIn order to successfully schedule the active MTC UEs to transmit on thebundling and spreading blocks, the eNodeB should first adjust the values ofNS and NB based on the number of active UEs and the required coveragegain, respectively. Then, it informs the MTC UE of values of NB and NSand its assigned codes. To minimize the impact of this procedure on thecurrent LTE standard, we note that some of the existing control flags in thePDCCH uplink grant are unlikely to be used in the MTC mode and thuscan be reused to inform the UE to obtain its TBS, bundling size, spreadinglength and their code index. This would be done based on a configurationtable for flexible TTI bundling and CDMA, which is a modified version ofthe TBS lookup table used in legacy UEs.Using a modified TBS table, transmission with flexible TTI bundlingand CDMA can be scheduled as follows.1344.2. Coverage Enhancement in PUSCH1. When data is available for transmission, the MTC UE sends a schedul-ing request on PUCCH.2. The eNodeB waits for a predefined time, collecting requests of MTCUEs as in Step 1, and estimates their required coverage gain from thereceived channel quality index (CQI).3. The eNodeB sets NS to the closest spreading length that is availablein the configuration table such that the current number of active MTCUEs can be accommodated.4. The eNodeB chooses NB based on the required coverage gain (4.1)with the computed NS from Step 3.5. Based on Steps 3 and 4 and available resources, eNodeB assigns re-sources to UEs. It sends a PDCCHDCI format 0 for PUSCH allocationand sets a flag to indicate that the modified TBS table needs to beused.Waiting and collecting requests in Step 2 is done to utilize as much ofthe available CDMA codes as possible, which maximizes system spectralefficiency while providing CE through spreading for individual MTC UEs.Steps 3 and 4 can further be refined to account for MTC UEs in good cov-erage, which may not need the full spreading gain. For example, those UEscould be assigned shorter spreading sequences, or multiple longer spreadingsequences.1354.3. Performance Evaluation4.3 Performance EvaluationAccording to LTE coverage enhancement study [137], we evaluate the CEachieved with flexible bundling and CDMA by measuring the SNR requiredfor 2% BLER after jointly decoding all the CDMA blocks in the bun-dle, which is also known as the residual BLER (rBLER). For CDMA, weuse Walsh-Hadamard and discrete Fourier transform (DFT) orthogonal se-quences [22, 23] for the even and odd values of NS , respectively. We chooseTBS of 104 bits to be transmitted in one RB (i.e., MPUSCHRB = 1 in 180 kHzbandwidth) using QPSK modulation (i.e. M = 2). Figure 4.2 compares therBLER obtained in simulations for different bundling and spreading config-urations compared to the legacy PUSCH transmission. We show the resultsboth in perfect and imperfect (abbreviated by “im” in the figure) channelstate information scenarios. As can be seen from this figure, the proposedtransmission based on bundling and spreading can achieve different valuesof gain by changing the configurations of (NS , NB). For example, the (22, 2)configuration, and in general any configuration whose NSNB is larger than32 =⌈10 15.010⌉, reaches the target CE of 15.0 dB.The first five columns of Table 4.3 compare the results shown in Fig-ure 4.2 with the expected theoretical gain (4.1). As can be seen, the theo-retical and simulated gains match well, where the latter include the effect ofcombing RVs in the turbo decoder, which gives only another about 0.4 dBgain compared to pure repetition due to the already low code rate for onlyone RV. In addition, it can be observed that the imperfect channel estima-tion decreases the gain by around 1 to 2 dB. In general, the performance1364.3. Performance Evaluation−20−19−18−17−16−15−14−13−12−11−10−9−8−7−6−5−4−3−2−1 0 1 2 3 410−310−210−1100  SNR (dB)rBLER(1,1)(6,2)(2,6)(22,2)(66,1)(1,66)(1,72)(12,9)(6,2) im(2,6) im(1,72) im(12,9) imFigure 4.2: Comparison of rBLER as a function of SNR for the legacy (1, 1)PUSCH transmission and different spreading and bundling configurations(Ns, NB). The rBLER curves are shown for both perfect and imperfect (im)channel estimations.1374.3. Performance EvaluationTable 4.3: Achieved coverage gain, spectral efficiency, and MTC data ratesfor flexible TTI bundling and spreading. Simulated CE, spectral efficiencyand data rate for TBS=104 in one RB using QPSK (M = 2).Theoretical Simulated Simulated Spectral DataCE CE CE Efficiency RateNS NB from (4.1) (perfect (Imperfect over all per MTCCSI) CSI) MTC UEs UE(dB) (dB) (dB) (bps/Hz) (kbps)1 1 0.0 0.0 0.0 0.578 104.02 6 10.8 11.2 10.7 0.097 8.76 2 10.8 10.7 9.7 0.290 8.722 2 16.4 16.4 15.2 0.289 2.412 9 20.3 20.6 19.9 0.067 1.01 66 18.2 18.6 17.9 0.009 1.666 1 18.2 18.1 16.2 0.578 1.61 72 18.6 19.0 18.1 0.008 1.41384.4. Conclusionsdifference between the perfect and imperfect channel estimation scenarios islarger for higher coverage gains, because the channel estimation is a morechallenging task in the presence of more noise in the low SNR values.The last two columns of Table 4.3 show the spectral efficiency (over allMTC UEs) and data rate (per MTC UE). As can be seen, system spectralefficiency is affected by bundling but not by spreading, assuming that allspreading codes are used, so that no resources are wasted while benefitingfrom spreading gain. Note that the amount of spreading that can be appliedis also limited by the need for either an essentially time-invariant channelover NS PRBs, or extra reference symbols for channel estimation. Finally,it can be observed that the achieved data rates are about a few kilo bits persecond (kbps) per MTC UE, which is suitable for many M2M applications.4.4 ConclusionsWe addressed the coverage enhancement of low-cost machine-type commu-nication (MTC) user equipments (UEs) in LTE. We focused on the channelwith the lowest coverage, namely physical uplink shared channel (PUSCH),and presented a novel transmission method on this channel by combiningTTI bundling and CDMA repetition. The coverage enhancement of thismethod is a function of both the coding gain of turbo codes used in the TTIbundles and the repetition gain of CDMA. Moreover, CDMA transmissiongives us the advantage of scheduling multiple MTC UEs at the same time.Therefore, the base station (eNodeB) can flexibly adjust the size of the pro-posed transmission blocks to provide the desired coverage to the active MTC1394.4. ConclusionsUEs. To this end, a simple scheduling protocol was also presented. Thisprotocol reuses the current LTE standard’s downlink control informationthat are unlikely to be used in the MTC mode. Using this protocol, MTCUEs can coexist with the current LTE legacy UES without requiring theLTE specification changes. We performed simulations to confirm that theachieved coverage gains compared to the normal PUSCH transmission reachthe desired 15 dB of CE.140Chapter 5ConclusionsPerforming optimization in wireless sensor networks and their successors,machine-type communication networks, is essential for developing energy-efficient, reliable, and cost-effective solutions. In this thesis, we addressedthree important aspects of WSN and MTCN operations, and provided opti-mization frameworks to improve their performance. We provided algorithmswith low complexity, for example by using convex optimization, and alsoachieved scalability by presenting the distributed version of our algorithms.First, we formulated the lifetime of an ultra-wideband (UWB) event-detection sensor network as a function of sensing and routing parametersin Chapter 2. We derived centralized and distributed convex optimizationframeworks for maximizing the lifetime. Detection requirement constraintswere added in the optimization to ensure that the sensing task can be ac-complished over the span of network lifetime. Our software simulationsshowed that the network lifetime achieved by solving the proposed convexformula is significantly improved compared to the similar formulations inthe literature.Second, a comprehensive study of different convex formulations for sen-sor network localization was presented in Chapter 3. We derived a robust1415.1. Directions for Future Researchlocalization framework, where the nodes can be localized in the presence ofuncertainty in the location of anchors. Moreover, an algorithm capable oftrading off localization accuracy with computational complexity were pre-sented. We also presented a distributed version of our robust localizationsolution to provide scalability to the network size. We performed extensivecomputer simulations to quantify the localization errors of our algorithms,and confirmed their high accuracy, low complexity and resilience to uncer-tainty.Third, we turned our attention to the newer type of sensor networks,namely machine-type communication over LTE cellular networks, and ad-dressed the coverage enhancement problem. We focused on the LTE uplinkdata channel which has the worst coverage, and designed a new transmissionstrategy based on data repetition and code division multiple access (CDMA)for coverage enhancement. We also presented a scheduling algorithm whichcan be controlled by the LTE base station (eNodeB) to provide the neces-sary coverage to the MTC UEs. In designing this protocol, we took intoaccount the coexistence criteria by making sure that our algorithm requiresminimal changes to the current LTE specifications.5.1 Directions for Future ResearchLifetime of a network can be further improved by means of data aggrega-tion [59, 67]. This would require analysis of correlation between data gener-ated by the nearby sensors to find out how packets can be merged togetherto achieve the maximum compression ratio and the minimum transmission1425.1. Directions for Future Researchpower. Similarly, data aggregation and cooperative routing among MTCUEs in an LTE cell can significantly reduce the workload of the eNodeB,and at the same time improve the coverage [140].Robust localization problems can benefit from a control on outliers, i.e.the nodes which generate extremely inaccurate ranging information due tofor example, their completely asynchronous clocks [100]. Discarding outliers’data from the localization formulation can significantly reduce the final lo-calization error.Establishing secure connections is another important challenge for bothWSNs and MTCNs. In fact, there has been a great interest recently onphysical-layer security for UWB [168] andMTC-enabled LTE [169]. Physical-layer security exploits the information present in the channel, e.g. delays andamplitudes of the taps in the channel impulse response, to generate a securekey that is only shared between the transmitter-receiver pair. An advantageof this type of key agreement is that it has a lower complexity comparedto the traditional cryptographic key exchange protocols. Providing privacyand security in Internet of Things and MTCNs is another important andrelated uprising research topic [170].143Bibliography[1] I. F. Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, “Wire-less sensor networks: a survey,” Computer Networks, vol. 38, no. 4,pp. 393 – 422, Mar. 2002.[2] “First Report and Order: In the matter of Revision of Part 15 ofthe Commissions Rules Regarding Ultra-Wideband Transmission Sys-tems,” Federal Communications Commision (FCC) 02-48, Tech. Rep.,Apr. 2002.[3] Z. Ahmadian, “Multiuser Pre-Filtered Ultra-Wideband Systems,”Ph.D. dissertation, The University of British Columbia (Vancouver),Dec. 2013.[4] International Telecommunication Union (ITU) , Objec-tives, Characteristics, and Functional Requirements of Wide-Area Sensor and/or Actuator Network (WASN) Systems,www.itu.int/rec/R-REC-M.2002-0-201203-I/en, Std. M.2002, Mar.2012.[5] D. Boswarthick, O. Elloumi, and O. Hersent, M2M Communications:a Systems Approach. John Wiley & Sons, 2012.144Bibliography[6] “GSMA Predicts 250 Million M2M Connec-tions in 2014,” Feb. 2014. [Online]. Available:http://www.gsma.com/newsroom/gsma-predicts-250-million-m2m/[7] Third Generation Partnership Project (3GPP), “Standardization ofMachine-Type Communication, LTE Rel-12,” Tech. Rep. [Online].Available: http://tinyurl.com/mv9ymkp[8] “Machine to machine (M2M) market global forecast & analysis (2012-2017),” Sep. 2012. [Online]. Available: http://tinyurl.com/pg3xa2a[9] G. B. Dantzig, Linear programming and extensions. Princeton Uni-versity Press, 1965.[10] S. Boyd and L. Vandenberghe, Convex Optimization, 4th ed. Cam-bridge University Press, 2004.[11] S. Sesia, I. Toufik, and M. Baker, LTE, The UMTS Long Term Evo-lution: From Theory to Practice, 2nd ed. John Wiley & Sons, 2011.[12] M.-G. Di Benedetto, UWB communication systems: a comprehensiveoverview. Hindawi Publishing Corporation, 2006, vol. 5.[13] J. Wang, High-Speed Wireless Communications: Ultra-wideband, 3GLong Term Evolution, and 4G Mobile Systems. Cambridge UniversityPress, 2008.[14] A. Parihar, L. Lampe, R. Schober, and C. Leung, “Equalization forDS-UWB systemspart I: BPSK modulation,” IEEE Transactions onCommunications, vol. 55, no. 6, pp. 1164–1173, June 2007.145Bibliography[15] ECMA Standard, “368: High Rate Ultra Wideband PHY and MACStandard.” 2005. [Online]. Available: http://tinyurl.com/256ja4[16] M. Win and R. Scholtz, “Impulse Radio: How It Works,” IEEE Com-mun. Lett., vol. 2, no. 2, pp. 36–38, 1998.[17] J.-Y. Lee and R. A. Scholtz, “Ranging in a dense multipath environ-ment using an UWB radio link,” Selected Areas in Communications,IEEE Journal on, vol. 20, no. 9, pp. 1677–1683, 2002.[18] “IEEE standard part 15.4a: Wireless medium access control (MAC)and physical layer (PHY) specifications for low-rate wireless personalarea networks (WPANs),” IEEE Std 802.15.4a-2007 (Amendment toIEEE Std 802.15.4-2006), pp. 1–203, 2007.[19] S. Gezici, Z. Tian, G. B. Giannakis, H. Kobayashi, A. F. Molisch,H. V. Poor, and Z. Sahinoglu, “Localization via ultra-wideband ra-dios: a look at positioning aspects for future sensor networks,” SignalProcessing Magazine, IEEE, vol. 22, no. 4, pp. 70–84, 2005.[20] J. R. Fernandes and D. Wentzloff, “Recent advances in ir-uwbtransceivers: An overview,” in Circuits and Systems (ISCAS), Pro-ceedings of 2010 IEEE International Symposium on. IEEE, 2010, pp.3284–3287.[21] B. Radunovic and J.-Y. Le Boudec, “Power control is not required forwireless networks in the linear regime,” in Proceedings of the IEEE In-ternational Symposium on a World of Wireless Mobile and MultimediaNetworks (WoWMoM), June 2005, pp. 417–427.146Bibliography[22] L. Hanzo, M. Mu¨nster, B. Choi, and T. Keller, OFDM and MC-CDMA. John Wiley & Sons, 2004.[23] K. Fazel and S. Kaiser, Multi-Carrier and Spread Spectrum Systems:From OFDM and MC-CDMA to LTE and WiMAX, 2nd ed. JohnWiley & Sons, 2008.[24] H. Holma and A. Toskala, LTE for UMTS: Evolution to LTE-Advanced. John Wiley & Sons, 2011.[25] K. S. Low, W. N. N. Win, and M. J. Er, “Wireless sensor networksfor industrial environments,” in IEEE International Conference onComputational Intelligence for Modelling, Control and Automation,vol. 2, 2005, pp. 271–276.[26] A. Wheeler, “Commercial applications of wireless sensor networks us-ing ZigBee,” Communications Magazine, IEEE, vol. 45, no. 4, pp.70–77, 2007.[27] I. F. Akyildiz, T. Melodia, and K. R. Chowdury, “Wireless multimediasensor networks: A survey,” IEEE Wireless Communications, vol. 14,no. 6, pp. 32–39, 2007.[28] C. Otto, A. Milenkovic, C. Sanders, and E. Jovanov, “System archi-tecture of a wireless body area sensor network for ubiquitous healthmonitoring,” Journal of Mobile Multimedia, vol. 1, no. 4, pp. 307–326,2006.[29] J. Stankovic, Q. Cao, T. Doan, L. Fang, Z. He, R. Kiran, S. Lin,147BibliographyS. Son, R. Stoleru, and A. Wood, “Wireless sensor networks for in-home healthcare: Potential and challenges,” in High confidence medi-cal device software and systems (HCMDSS) workshop, 2005, pp. 2–3.[30] C. S. Raghavendra, K. M. Sivalingam, and T. Znati, Wireless sensornetworks. Springer, 2004.[31] T. Arampatzis, J. Lygeros, and S. Manesis, “A survey of applicationsof wireless sensors and wireless sensor networks,” in IEEE Interna-tional Symposium on Intelligent Control, 2005, pp. 719–724.[32] S. Kumar and S. Chauhan, “A survey on scheduling algorithms forwireless sensor networks.” International Journal of Computer Appli-cations, vol. 20, 2011.[33] A. Manjeshwar and D. P. Agrawal, “Teen: A routing protocol forenhanced efficiency in wireless sensor networks.” in IPDPS, vol. 1,2001, p. 189.[34] K. Akkaya and M. Younis, “A survey on routing protocols for wirelesssensor networks,” Ad hoc networks, vol. 3, no. 3, pp. 325–349, 2005.[35] S. Biswas and R. Morris, “Exor: opportunistic multi-hop routing forwireless networks,” in ACM SIGCOMM Computer CommunicationReview, vol. 35, no. 4. ACM, 2005, pp. 133–144.[36] M. Win and R. Scholtz, “Ultra-wide bandwidth time-hopping spread-spectrum impulse radio for wireless multiple-access communications,”IEEE Trans. Commun., vol. 48, no. 4, pp. 679–689, 2000.148Bibliography[37] R. Merz, J. Widmer, J. Y. Le Boudec, and B. Radunovic, “A jointPHY/MAC architecture for low-radiated power TH-UWB wireless ad-hoc networks,” Journal of Wireless Communication and Mobile Com-puting, vol. 5, no. 5, pp. 567–580, Jul. 2005.[38] H. Jiang and W. Zhuang, “Effective packet scheduling with fairnessadaptation in Ultra-wideband wireless networks,” IEEE Trans. Wire-less Commun., vol. 6, no. 2, pp. 680–690, Feb. 2007.[39] B. Radunovic and J. Y. Le Boudec, “Optimal power control, schedul-ing, and routing in UWB networks,” IEEE J. Sel. Areas Commun.,vol. 22, no. 7, pp. 1252–1270, Sep. 2004.[40] I. Oppermann, L. Stoica, A. Rabbachin, Z. Shelby, and J. Haapola,“UWB wireless sensor networks: UWEN - a practical example,” IEEECommun. Mag., vol. 42, no. 12, pp. S27–S32, Dec. 2004.[41] J. Zhang, P. Orlik, S. Z., A. Molisch, and P. Kinney, “UWB systemsfor wireless sensor networks,” Proc. IEEE, vol. 97, no. 2, pp. 313 –331,Feb. 2009.[42] H. Yang and W. Wu, “UWB-assisted real-time localization in wirelesssensor networks,” in Industrial Electronics Society, IECON 2013-39thAnnual Conference of the IEEE. IEEE, 2013, pp. 4500–4505.[43] T. Melodia and I. F. Akyildiz, “Cross-layer QoS-aware communica-tions for ultra wide band wireless multimedia sensor networks,” IEEEJ. Sel. Areas Commun., vol. 28, no. 5, pp. 653–663, Jun. 2010.149Bibliography[44] J. Fu and S. Pan, “Fiber-connected uwb sensor network for high-resolution localization using optical time-division multiplexing,” Op-tics express, vol. 21, no. 18, pp. 21 218–21 223, 2013.[45] F. Cuomo, C. Martello, A. Baiocchi, and F. Capriotti, “Radio re-source sharing for ad hoc networking with UWB,” IEEE J. Sel. AreasCommun., vol. 20, no. 9, pp. 1722–1732, Dec. 2002.[46] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero III, R. L. Moses,and N. S. Correal, “Locating the nodes: cooperative localization inwireless sensor networks,” Signal Processing Magazine, IEEE, vol. 22,no. 4, pp. 54–69, 2005.[47] J. Hill, M. Horton, R. Kling, and L. Krishnamurthy, “The platformsenabling wireless sensor networks,” Communications of the ACM,vol. 47, no. 6, pp. 41–46, 2004.[48] W. Ye, J. Heidemann, and D. Estrin, “An energy-efficient MAC proto-col for wireless sensor networks,” in INFOCOM, Twenty-First AnnualJoint Conference of the IEEE Computer and Communications Soci-eties, vol. 3, 2002, pp. 1567–1576.[49] ——, “Medium access control with coordinated adaptive sleeping forwireless sensor networks,” IEEE/ACM Transactions on Networking,vol. 12, no. 3, pp. 493–506, June 2004.[50] G. Lu, B. Krishnamachari, and C. S. Raghavendra, “An adaptiveenergy-efficient and low-latency MAC for data gathering in wireless150Bibliographysensor networks,” in Parallel and Distributed Processing Symposium,2004. Proceedings. 18th International. IEEE, 2004, p. 224.[51] S. Bandyopadhyay and E. J. Coyle, “An energy efficient hierarchi-cal clustering algorithm for wireless sensor networks,” in INFOCOM,Twenty Second Annual Joint Conference of the IEEE Computer andCommunications Societies, vol. 3. IEEE, 2003, pp. 1713–1723.[52] D. Tian and N. D. Georganas, “A coverage-preserving node schedulingscheme for large wireless sensor networks,” in Proceedings of the 1stACM international workshop on Wireless sensor networks and appli-cations. ACM, 2002, pp. 32–41.[53] S. Soro and W. B. Heinzelman, “Cluster head election techniques forcoverage preservation in wireless sensor networks,” Ad Hoc Networks,vol. 7, no. 5, pp. 955–972, 2009.[54] G. Naddafzadeh Shirazi and L. Lampe, “Outage optimal node place-ment in ultra wideband sensor networks,” in IEEE International Con-ference on Ultra-Wideband (ICUWB), 2009, pp. 343–347.[55] J.-H. Chang and L. Tassiulas, “Maximum lifetime routing in wirelesssensor networks,” IEEE/ACM Transactions on Networking, vol. 12,no. 4, pp. 609–619, 2004.[56] H. Wang, N. Agoulmine, M. Ma, and Y. Jin, “Network lifetime opti-mization in wireless sensor networks,” IEEE Journal on Selected Areasin Communications, vol. 28, no. 7, pp. 1127–1137, Sep. 2010.151Bibliography[57] Y. Xi and M. Yeh, “Node-based optimal power control, routing, andcongestion control in wireless networks,” IEEE Trans. Inf. Theory,vol. 54, no. 9, pp. 4081–4106, Sep. 2008.[58] Q. Dong, “Maximizing system lifetime in wireless sensor networks,”in Proc. Fourth International Symposium on Information Processingin Sensor Networks (IPSN), Apr. 15, 2005, pp. 13–19.[59] D. M. Blough and P. Santi, “Investigating upper bounds on networklifetime extension for cell-based energy conservation techniques in sta-tionary ad hoc networks,” in Proceedings of the 8th annual interna-tional conference on Mobile computing and networking. ACM, 2002,pp. 183–192.[60] A. Sankar and Z. Liu, “Maximum lifetime routing in wireless ad-hocnetworks,” in INFOCOMM, Twenty-third Annual Joint Conference ofthe IEEE Computer and Communications Societies, 2004.[61] C. Pandana and K. R. Liu, “Robust connectivity-aware energy-efficient routing for wireless sensor networks,” Wireless Communica-tions, IEEE Transactions on, vol. 7, no. 10, pp. 3904–3916, 2008.[62] S. Olariu and I. Stojmenovic, “Design guidelines for maximizing life-time and avoiding energy holes in sensor networks with uniform distri-bution and uniform reporting.” in INFOCOM, Twenty Fifth AnnualJoint Conference of the IEEE Computer and Communications Soci-eties, 2006, pp. 1–12.152Bibliography[63] H. Kim, Y. Seok, N. Choi, Y. Choi, and T. Kwon, “Optimal multi-sinkpositioning and energy-efficient routing in wireless sensor networks,” inInformation Networking. Convergence in Broadband and Mobile Net-working. Springer, 2005, pp. 264–274.[64] E. I. Oyman and C. Ersoy, “Multiple sink network design problem inlarge scale wireless sensor networks,” in Communications, 2004 IEEEInternational Conference on, vol. 6. IEEE, 2004, pp. 3663–3667.[65] R. Madan and S. Lall, “Distributed algorithms for maximum lifetimerouting in wireless sensor networks,” IEEE Trans. Wireless Commun.,vol. 5, no. 8, pp. 2185–2193, Aug. 2006.[66] V. Shah-Mansouri and V. W. Wong, “Distributed maximum lifetimerouting in wireless sensor networks based on regularization,” in IEEEGlobal Telecommunications Conference (GLOBECOM), Washington,DC, USA, Nov. 2007.[67] C. Hua and T.-S. P. Yum, “Optimal routing and data aggregation formaximizing lifetime of wireless sensor networks,” IEEE/ACM Trans-actions on Networking, vol. 16, no. 4, pp. 892–903, Aug. 2008.[68] T. Q. S. Quek, M. Z. Win, and M. Chiani, “Distributed diversityin ultrawide bandwidth wireless sensor networks,” in Proc. VehicularTechnology Conference (VTC-Spring), vol. 2, May 30–Jun. 1, 2005,pp. 1355–1359.[69] Y. Yang, R. S. Blum, and B. M. Sadler, “Energy-efficient routing153Bibliographyfor signal detection in wireless sensor networks,” IEEE Trans. SignalProcess., vol. 57, no. 6, pp. 2050–2063, Jun. 2009.[70] J. Li and G. AlRegib, “Network lifetime maximization for estimationin multihop wireless sensor networks,” IEEE Trans. Signal Process.,vol. 57, no. 7, pp. 2456–2466, Jul. 2009.[71] K. Lorincz, D. Malan, T. Fulford-Jones, A. Nawoj, A. Clavel,V. Shnayder, G. Mainland, M. Welsh, and S. Moulton, “Sensor net-works for emergency response: challenges and opportunities,” Perva-sive Computing, IEEE, vol. 3, no. 4, pp. 16 – 23, Oct. 2004.[72] N. Kurata, S. Saruwatari, and H. Morikawa, “Ubiquitous structuralmonitoring using wireless sensor networks,” in Intelligent Signal Pro-cessing and Communications, 2006. ISPACS’06. International Sym-posium on. IEEE, 2006, pp. 99–102.[73] Y. Wang, L. Huang, J. Wu, and H. Xu, “Wireless sensor networks forintensive irrigated agriculture,” in Fourth Consumer Communicationsand Networking Conference (CCNC). IEEE, 2007, pp. 197–201.[74] A. Mainwaring, D. Culler, J. Polastre, R. Szewczyk, and J. Anderson,“Wireless sensor networks for habitat monitoring,” in Proceedings ofthe 1st ACM international workshop on Wireless sensor networks andapplications, ser. WSNA ’02, 2002, pp. 88–97.[75] A. Milenkovic, C. Otto, and E. Jovanov, “Wireless sensor networks forpersonal health monitoring: Issues and an implementation,” ComputerCommunications, vol. 29, no. 13-14, pp. 2521 – 2533, 2006.154Bibliography[76] H. Alemdar and C. Ersoy, “Wireless sensor networks for healthcare:A survey,” Computer Networks, vol. 54, no. 15, pp. 2688–2710, 2010.[77] J. Neyman and E. S. Pearson, “On the problem of the most efficienttests of statistical hypotheses,” Royal Society of London PhilosophicalTransactions Series A, vol. 231, pp. 289–337, 1933.[78] H. V. Poor, An introduction to signal detection and estimation (2nded.). New York, NY, USA: Springer-Verlag New York, Inc., 1994.[79] K. Bai and C. Tepedelenlioglu, “Distributed detection in UWB wire-less sensor networks,” IEEE Trans. Signal Process., vol. 58, no. 2, pp.804–813, Feb. 2010.[80] J. Xu, Y. Hong, and L. Chen, “Bound on the operational lifetime ofultra wideband sensor network,” in Proc. of the First InternationalConference on Innovative Computing, Information and Control (ICI-CIC), 2006, pp. 80–84.[81] Y. Shi, Y. T. Hou, H. D. Sherali, and S. F. Midkiff, “Optimal routingfor UWB-based sensor networks,” IEEE Journal on Selected Areas inCommunications, vol. 24, no. 4, pp. 857–863, Apr. 2006.[82] R. Szewczyk, E. Osterweil, J. Polastre, M. Hamilton, A. Mainwaring,and D. Estrin, “Habitat monitoring with sensor networks,” Commu-nications of the ACM, vol. 47, pp. 34–40, Jun. 2004.[83] L. Blazevic, J. Y. Le-Boudec, and S. Giordano, “A location-based155Bibliographyrouting method for mobile ad hoc networks,” IEEE Trans. MobileComput., vol. 4, pp. 97–110, Mar. 2004.[84] J. Wang, R. Ghosh, and S. K. Das, “A survey on sensor localization,”Journal of Control Theory and Applications, vol. 8, no. 1, pp. 2–11,2010.[85] J. Ibriq and I. Mahgoub, “Cluster-based routing in wireless sensornetworks: issues and challenges,” in SPECTS, vol. 4, 2004, pp. 759–766.[86] T. Eren, O. Goldenberg, W. Whiteley, Y. Yang, A. Morse, B. D. O.Anderson, and P. Belhumeur, “Rigidity, computation, and random-ization in network localization,” in INFOCOM, Twenty Third AnnualJoint Conference of the IEEE Computer and Communications Soci-eties, Mar. 2004, pp. 2673 – 2684.[87] J. Aspnes, T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley,Y. R. Yang, B. D. O. Anderson, and P. N. Belhumeur, “A theory ofnetwork localization,” IEEE Trans. Mobile Comput., vol. 5, no. 12,pp. 1663–1678, Dec. 2006.[88] Z. Zhu, A. M. So, and Y. Ye, “Universal rigidity: Towards accurateand efficient localization of wireless networks,” in INFOCOM, TwentyNinth Annual Joint Conference of the IEEE Computer and Commu-nications Societies, Mar. 2010, pp. 1–9.[89] Z. Yang, Y. Liu, and X.-Y. Li, “Beyond trilateration: On the localiz-156Bibliographyability of wireless ad hoc networks,” IEEE/ACM Trans. Netw., vol. 99,no. 99, pp. 1–9, May 2010.[90] N. Patwari, J. N. Ash, S. Kyperountas, A. O. Hero, R. L. Moses,and N. S. Correal, “Locating the nodes: cooperative localization inwireless sensor networks,” IEEE Signal Process. Mag., vol. 22, no. 4,pp. 54–69, Jul. 2005.[91] P. Bahl and V. N. Padmanabhan, “RADAR: An in-building RF-baseduser location and tracking system,” in INFOCOM, Nineteenth An-nual Joint Conference of the IEEE Computer and CommunicationsSocieties, Mar. 2000, pp. 775–784.[92] P. Rong and M. Sichitiu, “Angle of arrival localization for wirelesssensor networks,” in IEEE Sensor and Ad Hoc Communications andNetworks (SECON), Sept. 2006, pp. 374 – 382.[93] G. Mao, B. Fidan, and B. D. O. Anderson, “Wireless sensor networklocalization techniques,” Computer Networks, vol. 51, no. 10, pp. 2529– 2553, Jul. 2007.[94] X. Cheng, A. Thaeler, G. Xue, and D. Chen, “TPS: A time-basedpositioning scheme for outdoor wireless sensor networks,” in IEEEInfocom, Mar. 2004, pp. 2685 – 2696.[95] J. Aspnes, D. Goldenberg, and Y. R. Yang, “On the computationalcomplexity of sensor network localization,” in Proc. ALGOSENSORS,ser. Lecture Notes in Computer Science. Springer-Verlag, 2004, pp.32–44.157Bibliography[96] M. Jadliwala, S. Upadhyaya, and M. Taneja, “ASFALT: A SimpleFault-Tolerant Signature-based Localization Technique for EmergencySensor Networks,” in IEEE International Symposium on Reliable Dis-tributed Systems (SRDS), Oct 2007, pp. 3–12.[97] M. Meurer, S. Heilmann, D. Reddy, T. Weber, and P. Baier, “A sig-nature based localization technique relying on covariance matrices ofchannel impulse responses,” in Proc. 2nd Workshop Positioning Nav-igation and Communication (WPNC), 2005, pp. 31–40.[98] Y. Shang, W. Ruml, Y. Zhang, and M. Fromherz, “Localization fromconnectivity in sensor networks,” IEEE Trans. Parallel Distrib. Syst.,vol. 15, no. 11, pp. 961–974, Nov. 2004.[99] J. Zheng and Y.-C. Wu, “Robust joint localization and time synchro-nization in wireless sensor networks with bounded anchor uncertain-ties,” in IEEE International Conference on Acoustics, Speech, andSignal Processing (ICASSP), Apr. 2009, pp. 2793–2796.[100] J. S. Picard and A. J. Weiss, “Bounds on the number of identifiableoutliers in source localization by linear programming,” IEEE Trans.Signal Process., no. 5, pp. 2884–2895, May 2010.[101] L. Doherty, K. S. J. Pister, and L. El Ghaoui, “Convex position esti-mation in wireless sensor networks,” in INFOCOM, Twentieth AnnualJoint Conference of the IEEE Computer and Communications Soci-eties, vol. 3, Apr. 2001, pp. 1655–1663.158Bibliography[102] S. Zhu and Z. Ding, “A simple approach of range-based positioningwith low computational complexity,” IEEE Trans. Wireless Commun.,vol. 8, no. 12, pp. 5832–5836, Dec. 2009.[103] C. Feng, W. S. A. Au, S. Valaee, and Z. Tan, “Compressive sensingbased positioning using RSS of WLAN access points,” in INFOCOM,Twenty Ninth Annual Joint Conference of the IEEE Computer andCommunications Societies, Mar. 2010, pp. 1–9.[104] L. Yang and K. C. Ho, “An approximately efficient TDOA localizationalgorithm in closed-form for locating multiple disjoint sources with er-roneous sensor positions,” IEEE Trans. Signal Process., vol. 57, no. 12,pp. 4598–4615, Dec. 2009.[105] S. Srirangarajan, A. Tewfik, and Z.-Q. Luo, “Distributed sensor net-work localization using SOCP relaxation,” IEEE Trans. WirelessCommun., vol. 7, no. 12, pp. 4886–4895, Dec. 2008.[106] P. Tseng, “Second-order cone programming relaxation of sensor net-work localization,” SIAM Journal on Optimization, vol. 18, no. 1, pp.156–185, Feb. 2007.[107] A. M.-C. So and Y. Ye, “Theory of semidefinite programming forsensor network localization,” Math. Program., vol. 109, no. 2, pp. 367–384, Jan. 2007.[108] P. Biswas, T.-C. Liang, K.-C. Toh, Y. Ye, and T.-C. Wang, “Semidef-inite programming approaches for sensor network localization with159Bibliographynoisy distance measurements,” IEEE Trans. Autom. Sci. Eng., vol. 3,no. 4, pp. 360–371, Oct. 2006.[109] P. Biswas and Y. Ye, “A distributed method for solving semidefiniteprograms arising from ad hoc wireless sensor network localization,”Multiscale optimization methods and applications, vol. 82, pp. 69–84,Jan. 2006.[110] K. Lui, W.-K. Ma, H. So, and F. Chan, “Semi-definite programmingalgorithms for sensor network node localization with uncertainties inanchor positions and/or propagation speed,” IEEE Trans. Signal Pro-cess., vol. 57, no. 2, pp. 752–763, Feb. 2009.[111] J. A. Costa, N. Patwari, and A. O. Hero, “Distributed weighted-multidimensional scaling for node localization in sensor networks,”ACM Trans. Sensor Networks, vol. 2, no. 1, pp. 39–64, Feb. 2006.[112] Z. Wang, S. Zheng, Y. Ye, and S. Boyd, “Further relaxations of thesemidefinite programming approach to sensor network localization,”SIAM J. on Optimization, vol. 19, no. 2, pp. 655–673, Jul. 2008.[113] T. K. Pong and P. Tseng, “(robust) edge-based semidefinite program-ming relaxation of sensor network localization,” Mathematical Pro-gramming, ser. A, 2010.[114] Q. Shi, C. He, H. Chen, and L. Jiang, “Distributed wireless sensornetwork localization via sequential greedy optimization algorithm,”IEEE Trans. Signal Process., vol. 58, no. 6, pp. 3328–3340, Jun. 2010.160Bibliography[115] P. gren, E. Fiorelli, and N. E. Leonard, “Cooperative control of mobilesensor networks: Adaptive gradient climbing in a distributed environ-ment,” IEEE Trans. Autom. Control, vol. 49, no. 8, Aug. 2004.[116] L. Hu and D. Evans, “Localization for mobile sensor networks,” inProc. ACM MobiCom, 2004, pp. 45–57.[117] S. Zhang, J. Cao, L. Chen, and D. Chen, “Accurate and energy-efficient range-free localization for mobile sensor networks,” IEEETrans. Mobile Comput., vol. 9, no. 6, Jun. 2010.[118] J. Teng, H. Snoussi, C. Richard, and R. Zhou, “Distributed variationalfiltering for simultaneous sensor localization and target tracking inwireless sensor networks,” IEEE Trans. Veh. Technol., vol. 61, no. 5,pp. 2305–2318, 2012.[119] S. Thrun, D. Fox, W. Burgard, and F. Dellaert, “Robust monte carlolocalization for mobile robots,” Artificial Intelligence, vol. 128, no. 1-2,pp. 99–141, 2000.[120] Z. Zhong, T. Zhu, D. Wang, and T. He, “Tracking with unreliable nodesequences,” in INFOCOMM, Twenty Eighth Annual Joint Conferenceof the IEEE Computer and Communications Societies, 2009, pp. 1215–1223.[121] X. Chen, A. Edelstein, Y. Li, M. Coates, M. Rabbat, and A. Men,“Sequential monte carlo for simultaneous passive device-free trackingand sensor localization using received signal strength measurements,”161Bibliographyin Proc. 10th Int Information Processing in Sensor Networks (IPSN)Conf., 2011, pp. 342–353.[122] J. C. Derenick and J. R. Spletzer, “Convex optimization strategiesfor coordinating large-scale robot formations,” IEEE Trans. MobileComput., vol. 23, no. 6, Dec. 2007.[123] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups ofmobile autonomous agents using nearest neighbor rules,” IEEE Trans.Autom. Control, vol. 48, no. 6, pp. 988–1001, 2003.[124] S.-Y. Lien, K.-C. Chen, and Y. Lin, “Toward ubiquitous massive ac-cesses in 3GPP machine-to-machine communications,” IEEE Com-mun. Mag., vol. 49, no. 4, pp. 66–74, 2011.[125] S. Lucero. Maximizing Mobile Operator Opportunities in M2M TheBenefits of an M2M-Optimized Network. White Paper. ABI Research- Cisco. [Online]. Available: http://tinyurl.com/kt345s9[126] R. Lu, X. Li, X. Liang, X. Shen, and X. Lin, “Grs: The green, relia-bility, and security of emerging machine to machine communications,”IEEE Commun. Mag., vol. 49, no. 4, pp. 28–35, 2011.[127] Y. Liang, H. V. Poor, and L. Ying, “Secure communications over wire-less broadcast networks: Stability and utility maximization,” IEEETrans. Inf. Forensics Security, vol. 6, no. 3, pp. 682–692, 2011.[128] Third Generation Partnership Project (3GPP), “Service requirementsfor machine-type communications (MTC); stage 1,” Technical Spec-162Bibliographyification Group Services and System Aspects;, Tech. Rep. 22.368V12.3.0, Dec. 2013.[129] K.-R. Jung, A. Park, and S. Lee, “Machine-Type-Communication(MTC) Device Grouping Algorithm for Congestion Avoidance of MTCOriented LTE Network,” in Security-Enriched Urban Computing andSmart Grid, 2010, vol. 78, pp. 167–178.[130] S.-Y. Lien and K.-C. Chen, “Massive access management for QoS guar-antees in 3GPP machine-to-machine communications,” IEEE Com-mun. Lett., vol. 15, no. 3, pp. 311–313, 2011.[131] S.-Y. Lien, T.-H. Liau, C.-Y. Kao, and K.-C. Chen, “Cooperativeaccess class barring for machine-to-machine communications,” IEEETrans. Wireless Commun., vol. 11, no. 1, pp. 27–32, 2012.[132] R. Yu, Y. Zhang, Y. Chen, C. Huang, Y. Xiao, and M. Guizani, “Dis-tributed rate and admission control in home M2M networks: A non-cooperative game approach,” in Proc. IEEE Conf. Computer Commu-nications Workshops (INFOCOM WKSHPS), 2011, pp. 196–200.[133] R. Liu, W. Wu, H. Zhu, and D. Yang, “M2M-Oriented QoS Catego-rization in Cellular Network,” in Proc. 7th Int Wireless Communica-tions, Networking and Mobile Computing (WiCOM) Conf, 2011, pp.1–5.[134] J. Zhou, M. Li, L. Liu, X. She, and L. Chen, “Energy source awaretarget cell selection and coverage optimization for power saving in163Bibliographycellular networks,” in Proc. Physical and Social Computing (CPSCom)Green Computing and Communications (GreenCom) IEEE/ACM Int’lConf. & Int’l Conf. Cyber, 2010, pp. 1–8.[135] G. Wang, X. Zhong, S. Mei, and J. Wang, “An adaptive medium ac-cess control mechanism for cellular based machine to machine (M2M)communication,” in Proc. IEEE International Wireless InformationTechnology and Systems (ICWITS) Conference, 2010, pp. 1–4.[136] M. Hasan, E. Hossain, and D. Niyato, “Random access for machine-to-machine communication in LTE-advanced networks: issues and ap-proaches,” Communications Magazine, IEEE, vol. 51, no. 6, 2013.[137] Third Generation Partnership Project (3GPP), “LTE coverage en-hancements,” Technical Specification Group Radio Access Network(RAN), Tech. Rep. 36.824 V11.0.0, 2012.[138] Third Generation Partnership Project (3GPP) Work Item Description,“Low Cost and Enhanced Coverage MTC UE for LTE,” Tech. Rep.RP-130848, Jun. 2013.[139] J. Berglund, “Extended LTE coverage for indoor machine type com-munication,” Master’s thesis, Ericsson Research, Jun. 2013.[140] S. Andreev, O. Galinina, and Y. Koucheryavy, “Energy-efficient clientrelay scheme for machine-to-machine communication,” in Proc. IEEEGlobal Telecommunications Conf. (GLOBECOM 2011), 2011, pp. 1–5.[141] R. Schoenen, W. Zirwas, and B. H. Walke, “Capacity and coverage164Bibliographyanalysis of a 3gpp-lte multihop deployment scenario,” in Communi-cations Workshops, 2008. ICC Workshops’ 08. IEEE InternationalConference on. IEEE, 2008, pp. 31–36.[142] T. Beniero, S. Redana, J. Hamalainen, and B. Raaf, “Effect of re-laying on coverage in 3GPP LTE-Advanced,” in Vehicular TechnologyConference (VTC-Spring). IEEE, 2009, pp. 1–5.[143] T. Banerjee, B. Xie, and D. P. Agrawal, “Fault tolerant multiple eventdetection in a wireless sensor network,” J. Parallel Distrib. Comput.,vol. 68, pp. 1222–1234, Sep. 2008.[144] J. Li and G. AlRegib, “Rate-constrained distributed estimation inwireless sensor networks,” IEEE Trans. Signal Process., vol. 55, no. 5,pp. 1634–1643, May 2007.[145] J.-J. Xiao, S. Cui, Z.-Q. Luo, and A. J. Goldsmith, “Power schedulingof universal decentralized estimation in sensor networks,” IEEE Trans.Signal Process., vol. 54, no. 2, pp. 413–422, Feb. 2006.[146] H. L. V. Trees, Detection, Estimation, and Modulation Theory: Radar-Sonar Signal Processing and Gaussian Signals in Noise. Melbourne,FL, USA: Krieger Publishing Co., Inc., 1992.[147] A. Rajeswaran, G. Kim, and R. Negi, “Joint power adaptation,scheduling, and routing for ultra wide band networks,” IEEE Trans.Wireless Commun., vol. 6, no. 5, pp. 1964–1972, May 2007.[148] A. F. Molisch, K. Balakrishnan, D. Cassioli, C. Chong, S. Emami,165BibliographyA. Fort, J. Karedal, J. Kunisch, H. Schantz, U. Schuster, and K. Si-wiak, “IEEE 802.15.4a channel model-final report,” IEEE 802.15.4a,Tech. Rep., 2005.[149] A. Krasnopeev, J.-J. Xiao, and Z.-Q. Luo, “Minimum energy decen-tralized estimation in a wireless sensor network with correlated sensornoises,” EURASIP J. Wirel. Commun. Netw., vol. 2005, no. 4, pp.473–482, 2005.[150] L. Xiao, M. Johansson, and S. Boyd, “Simultaneous routing and re-source allocation via dual decomposition,” IEEE Trans. Commun.,vol. 52, no. 7, pp. 1136–1144, Jul. 2004.[151] J. Ryckaert et al., “A CMOS Ultra-Wideband Receiver for Low Data-Rate Communication,” IEEE J. Solid-State Circuits, vol. 42, no. 11,pp. 2515–2527, Nov. 2007.[152] W.-G. Seah, Z. A. Eu, and H. Tan, “Wireless sensor networks poweredby ambient energy harvesting (WSN-HEAP) - survey and challenges,”in First International Conference on Wireless Communication, Vehic-ular Technology, Information Theory and Aerospace Electronic Sys-tems Technology (VITAE), May 2009, pp. 1–5.[153] K. Yu, J. P. Montillet, A. Rabbachin, P. Cheong, and I. Opper-mann, “UWB location and tracking for wireless embedded networks,”Elsevier Signal Processing, Special Section: UWB Communications,vol. 86, no. 9, pp. 2153 – 2171, Sept. 2006.166Bibliography[154] C. Hide, T. Moore, and M. Smith, “Adaptive Kalman filtering for lowcost INS/GPS,” The Journal of Navigation, vol. 56, pp. 143–152, Jan.2003.[155] Global Positioning System (GPS), Stan-dard Positioning Service Performance Standard,www.gps.gov/technical/ps/2008-SPS-performance-standard.pdf,Std. Ed. 4, Sep. 2008.[156] F. Alizadeh and D. Goldfarb, “Second-order cone programming,”Mathematical Programming, vol. 95, pp. 3–51, 2001.[157] T. K. Pong, “Edge-based semidenite programming relaxation of sensornetwork localization with lower bound constraints,” Journal of Com-putational Optimization and Applications, vol. 53, pp. 23–44, 2010.[158] J. Nocedal and S. Wright, Numerical Optimization. Springer, 1999.[159] P. Tseng, “Convergence of a block coordinate descent method for non-differentiable minimization,” Journal of Optimization Theory and Ap-plications, vol. 109, pp. 475–494, 2001.[160] M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret, “Applicationsof second-order cone programming,” Linear algebra and its applica-tions, vol. 284, no. 1, pp. 193–228, 1998.[161] A. Logothetis and V. Krishnamurthy, “Expectation maximization al-gorithms for map estimation of jump markov linear systems,” IEEETrans. Signal Process., vol. 48, no. 7, pp. 2139–2156, Aug. 1999.167Bibliography[162] M. Grant and S. Boyd., MATLAB software for disciplinedconvex programming (web page and software). [Online]. Available:http://stanford.edu/∼boyd/cvx[163] T. Camp, J. Boleng, and V. Davies, “A survey of mobility models forad hoc network research,” Wireless Communications & Mobile Com-puting (WCMC), vol. 2, pp. 483–502, 2002.[164] Third Generation Partnership Project (3GPP), “Study on provisionof low-cost MTC UEs based on LTE,” Technical Specification GroupRadio Access Network (RAN), Tech. Rep. 36.888 V12.0.0, Jun. 2013.[165] G. Naddafzadeh-Shirazi, L. Lampe, G. Vos, and S. Bennett, “En-hancement for LTE communication systems,” Patent United StatesApp. No. 14/046 733, International App. No. PCT/CA2013/050 749,(Filed October 4, 2013).[166] G. Vos, G. Naddafzadeh-Shirazi, S. Bennett, L. Lampe, andR. Khalona, “Method and system for hybrid automatic request com-bining on an LTE downlink control channel,” Patent United StatesApp. No. 13/730 244, International App. No. PCT/CA2013/730 244,(Filed December 28, 2012).[167] G. Vos, S. Bennett, L. Lampe, and G. Naddafzadeh-Shirazi, “Methodand apparatus for broadcast channel decoding,” Patent United StatesApp. No. 61/807 641, (Filed April 2, 2013).[168] R. Wilson, D. Tse, and R. A. Scholtz, “Channel identification: Secret168sharing using reciprocity in ultrawideband channels,” IEEE Trans.Inf. Forensics Security, vol. 2, no. 3, pp. 364–375, Sep. 2007.[169] C. Lai, H. Li, R. Lu, X. Shen, and J. Cao, “A unified end-to-endsecurity scheme for machine-type communication in LTE networks,”in IEEE/CIC International Conference on Communications in China(ICCC), Aug. 2013, pp. 698–703.[170] R. H. Weber, “Internet of things–new security and privacy challenges,”Computer Law & Security Review, vol. 26, no. 1, pp. 23–30, Jan. 2010.169Appendix AProof of Proposition 3.1We can write (3.7) with the relaxation (3.8) in the form:v∗socp.= min{xi},{qij}‖[[gij |qij − dij |](i,j)∈E ; [‖Ψ−1/2i (ai − xi)‖]i∈Na]‖(A.1a)subject to ‖xi − xj‖ ≤ qij , (i, j) ∈ E , (A.1b)where intermediate variables tij , si,u, v are removed.a) Since the Euclidean norm is strictly convex, the problem (A.1) must havea unique optimal with regard to all variables that appear in the norm [10].Hence, xi, i ∈ Na, is unique at the optimal. Note that xi, i ∈ Ns does notappear in the norm in the objective.b) The proof of this part is identical to [106, Proposition 5.1c], and we brieflyshow it here for completeness. Note that according to part a) qij, (i, j) ∈ E ,is unique over all solutions. For a tight link (i, j) ∈ B, i ∈ Ns,12‖xi−xj‖2+ 12‖x′i−x′j‖2 = ‖xi + x′i2 −xj + x′j2 ‖2+‖xi − x′i2 −xj − x′j2 ‖2,(A.2)170Appendix A. Proof of Proposition 3.1with (x′i,x′j) being another optimal solution. Since the solution set of aconvex problem is convex [20], (xi+x′i2 ,xj+x′j2 ) must be another optimalsolution, and thus (A.2) implies that q2ij/2+ q2ij/2 = q2ij + ‖xi−x′i2 −xj−x′j2 ‖2,and thusxi − x′i = xj − x′j , ∀j ∈ Ji, (A.3)where Ji is the set of nodes which are directly connected to node i throughtight links. Now, denote the set of all nodes which are connected to nodei through tight links, possibly through multiple hops, by Ti. Accordingto [106, Proposition 5.1b], there is at least one anchor xk, k ∈ Na in Ti.We can then apply (A.3) to this anchor and its immediate tight neighborxl ∈ Ns in Ti, and conclude that xl = x′l since xk = x′k holds accordingto part a). We can repeat the same procedure between the nodes that areproven to be invariant and their immediate neighbours to conclude that allnodes in Ti are invariant over all solutions. Now, since j ∈ Ti, (A.3) impliesthat xi is also invariant over all solutions of the robust SOCP.For the proof of the reverse part, note that for a node xi i ∈ Ns with‖xi − xj‖ < qij, ∀j ∈ Ki, another distinct relative interior solution can beobtained as x′i = xi + ∆x with ∆x small enough such that ‖(x′i − xj)‖ <qij, ∀j ∈ Ki, and all other variables remain unchanged.c) We first show that for the analytic center solution, each sensor node isestimated within the convex hull of its neighbours, i.e. xi ∈ C{xj}j∈Ki , ∀i ∈Ns. Similar to [106, Proposition 6.2], we argue by contradiction. Supposethat at the analytic center solution, for a sensor node i ∈ Ns, xi is outsidethe convex hull of its neighbours. Then, let pi be its projection on this171Appendix A. Proof of Proposition 3.1convex hull and thus for each neighbor j ∈ Ki we can write,‖pi − xj‖ < ‖xi − xj‖ ⇒ log(qij − ‖pi − xj‖) > log(qij − ‖xi − xj‖)⇒∑(i,j)∈E−Blog(qij − ‖pi − xj‖) >∑(i,j)∈E−Blog(qij − ‖xi − xj‖),where the second clause follows from the uniqueness of qij over all solutions,and in the third clause, summation is taken overall non-tight links. Thereforexi can not be the analytical center solution of node i. Thus, xi must beinside the convex hull of its neighbours. Now, since, only anchor nodes areallowed to be localized outside the convex hull of their neighbours, it followsthat anchors form the convex hull of the analytic center solution.172Appendix BProof of Proposition 3.2In order to prove Proposition 2, we first construct a variation of the robustSDP optimization problem (3.9):v′sdp.= minX,Y ,{M i},{γij},{rij}∑(i,j)∈Eg2ij(γij − 2dijrij + d2ij)+∑i∈Natr(Ψ−1i M i)) 12(B.1a)subject to γij = yii + yjj − yij − yji, (i, j) ∈ E , (B.1b)r2ij ≤ γij , (i, j) ∈ E , (B.1c)tr(M i) = yii − 2aTi xi + aTi ai, i ∈ Na, (B.1d)xi = [yim+1 yim+2]T , i ∈ N , (B.1e)ym+1m+1 ym+1m+2ym+2m+1 ym+2m+2= I2, (B.1f)M i ai − xi(ai − xi)T 1 03, i ∈ Na, (B.1g)173Appendix B. Proof of Proposition 3.2Y  0m+2, (B.1h)where M i is defined in (3.11). The SDP relaxation (B.1) is equivalentto (3.9) because there is a one-to-one mapping between the feasible solutionset of (3.9) to the feasible solution set of (B.1). LetSsdp = {X,Y , {M i} , {γij} , {rij}} be a feasible solution for robust SDPsatisfying constraints (B.1b)-(B.1h). We show that the variables definedin (3.11) satisfy the SOCP constraints (3.7c)-(3.7e) and (3.8), and henceany feasible solution for robust SDP (B.1) (equivalently (3.9)) is a feasiblesolution for (3.7).In fact, constraints (3.7c) and (3.7d)) are clearly satisfied with equalityby definition of v and tij in (3.11). To see that constraint (3.7e) is satisfied,first note that since SDP constraint (B.1g) is satisfied,M i − (ai − xi)(ai − xi)T , i ∈ Na, is a positive semidefinite matrix. Itis then clear thattr(Ψ−1i(M i − (ai − xi)(ai − xi)T))≥ 0, i ∈ Na, (B.2)due to the fact that the trace of the product of two positive semidefinitematrix is always non-negative. Using this inequality we obtains2i = tr(Ψ−1i M i)≥ tr(Ψ−1i (ai − xi)(ai − xi)T)= ‖Ψ−1/2i (ai − xi)‖2, i ∈ Na,which leads to constraint (3.7e) by taking the square root of both sides.174Appendix B. Proof of Proposition 3.2For constraint (3.8), we follow the same line of reasoning as [21]. Specif-ically, since constraint (B.1h) is satisfied, Y .=Y m XTX I2is positivesemidefinite, and Z .= Y m − XTX  0m. Moreover, since any 2 × 2principal submatrix of the positive semidefinite matrix Z is also positivesemidefinite, we getyii − ‖xi‖2 yij − xTi xjyji − xTj xi yjj − ‖xj‖2 02, (i, j) ∈ E . (B.3)Hence,[1,−1]yii − ‖xi‖2 yij − xTi xjyji − xTj xi yjj − ‖xj‖21−1≥ 0,⇒yii − ‖xi‖2 + yjj − ‖xj‖2 − 2(yij − xTi xj) ≥ 0.Consequently,q2ij = yii + yjj − 2yij ≥ ‖xi‖2 − 2xTi xj + ‖xj‖2 = ‖xi − xj‖2.Therefore, constraint (3.8) is also satisfied.We have shown that all constraints of the robust SOCP are satisfied andthus any feasible solution of the robust SDP is also a feasible solution ofthe robust SOCP. Also, the optimum value of the robust SOCP in (3.7) is175Appendix B. Proof of Proposition 3.2smaller than or equal to that for the robust SDP in (B.1) because at theoptimal point of SDP, which is a feasible point for SOCP, we havev′sdp =√vsdp + v0=∑(i,j)∈Eg2ij(γij − 2dijrij + d2ij)+∑i∈Natr(Ψ−1i M i)12=∑(i,j)∈Eg2ij(γij − 2dij√γij + d2ij)+∑i∈Nas2i12=∑(i,j)∈Eg2ij (qij − dij)2 +∑i∈Nas2i12=∑(i,j)∈Et2ij +∑i∈Nas2i12= vsocp,where the third equality holds because at the optimum solution of the robustSDP, r2ij = γij , i.e. constraint (B.1e) is satisfied with equality [25]. The proofis complete by noting that, by definition, any non-optimal solution of SDPhas a value of objective which is larger than v′sdp.176

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0167441/manifest

Comment

Related Items