<?xml version="1.0" encoding="UTF-8"?><?xml-stylesheet type="text/xsl" href="static/style.xsl"?><OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"><responseDate>2026-11-22T07:23:41Z</responseDate><request verb="GetRecord" identifier="oai:uwspace.uwaterloo.ca:10012/7142" metadataPrefix="dim">https://dspacemainprd01.lib.uwaterloo.ca/server/oai/request</request><GetRecord><record><header><identifier>oai:uwspace.uwaterloo.ca:10012/7142</identifier><datestamp>2017-03-21T18:47:29Z</datestamp><setSpec>com_10012_9900</setSpec><setSpec>com_10012_1</setSpec><setSpec>col_10012_9908</setSpec><setSpec>col_10012_6</setSpec></header><metadata><dim:dim xmlns:dim="http://www.dspace.org/xmlns/dspace/dim" xmlns:doc="http://www.lyncode.com/xoai" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.dspace.org/xmlns/dspace/dim http://www.dspace.org/schema/dim.xsd">
   <dim:field mdschema="dc" element="contributor" qualifier="author" authority="aada5436-99a3-4942-834b-0ed529077c7e" confidence="600">Sappidi, Rajasekhar Reddy</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="accessioned">2012-12-07T18:07:01Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="available">2012-12-07T18:07:01Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="issued">2012-12-07T18:07:01Z</dim:field>
   <dim:field mdschema="dc" element="date" qualifier="submitted">2012-11-22</dim:field>
   <dim:field mdschema="dc" element="identifier" qualifier="uri">http://hdl.handle.net/10012/7142</dim:field>
   <dim:field mdschema="dc" element="description" qualifier="abstract" lang="en">Sensor networks are an important emerging class of networks that have many&#xd;
applications. A sink in these networks acts as a bridge between the sensor nodes&#xd;
and the end-user (which may be automated and/or part of the sink). Typically,&#xd;
convergecast is performed in which all the data collected by the sensors is&#xd;
relayed to the sink, which in turn presents the relevant information to the&#xd;
end-user. Interestingly, some applications require the sink to relay just a&#xd;
function of the data collected by the sensors.  For instance, in a fire alarm&#xd;
system, the sinks needs to monitor the maximum of the temperature readings of&#xd;
all the sensors. For these applications, instead of performing convergecast, we&#xd;
can let  the intermediate nodes process the data they receive, to significantly&#xd;
reduce the volume of traffic transmitted and increase the rate at which&#xd;
the data is collected and processed at the sink: this is known as in-network&#xd;
computation. &#xd;
&#xd;
&#xd;
Most of the current literature on this novel technique focuses on asymptotic&#xd;
results for large networks and for very elementary functions. In this&#xd;
dissertation, we study a new class of functions for which we want to compute&#xd;
explicit solutions for networks of practical size.&#xd;
We consider the applications where the sink is interested in the first&#xd;
M statistical moments of the data collected at a certain time.&#xd;
The k-th statistical moment is&#xd;
defined as the expectation of the k-th power of the data. The M=1 case represents the&#xd;
elementary functions like MAX, MIN, MEAN, etc. that are commonly considered in&#xd;
the literature. For this class of functions, we are interested in explicitly&#xd;
computing the maximum achievable throughput including routing, scheduling and&#xd;
queue management for any given network when in-network computation is allowed.&#xd;
&#xd;
Flow models have been routinely used to solve optimal joint routing and scheduling&#xd;
problems when there is no in-network computation and they are typically&#xd;
tractable for relatively large networks. However, deriving such models is not&#xd;
obvious when in-network computation is allowed.  Considering a single rate wireless network&#xd;
and the physical model of interference,  we develop a discrete-time model for&#xd;
the real-time network operation and perform two transformations to obtain a flow&#xd;
model that keeps the essence of in-network computation. This model gives an&#xd;
upper bound on the maximum achievable throughput. To show the tightness of that&#xd;
upper bound, we derive a numerical lower bound  by computing a feasible solution&#xd;
to the discrete-time model. This lower bound turns out to be&#xd;
close to the upper bound proving that the flow model is an excellent&#xd;
approximation to the discrete-time model.&#xd;
&#xd;
We then adapt the flow model to a&#xd;
wired multi-rate network with asynchronous transmissions on links with different&#xd;
capacities. To compute the lower bound for wired networks,  we propose a&#xd;
heuristic strategy involving the generation of multiple trees and effective&#xd;
queue management that achieves a throughput  close to the one computed by the&#xd;
flow model. This cross validates the tightness of the upper bound and the&#xd;
goodness of our heuristic strategy. Finally, we provide several engineering&#xd;
insights on what in-network computation can achieve in both types of networks.</dim:field>
   <dim:field mdschema="dc" element="language" qualifier="iso" lang="en">en</dim:field>
   <dim:field mdschema="dc" element="publisher" lang="en">University of Waterloo</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">In-network computation</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Sensor Networks</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Optimization</dim:field>
   <dim:field mdschema="dc" element="subject" lang="en">Flow Model</dim:field>
   <dim:field mdschema="dc" element="subject" qualifier="program" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="dc" element="title" lang="en">In-network computation in sensor networks</dim:field>
   <dim:field mdschema="dc" element="type" lang="en">Doctoral Thesis</dim:field>
   <dim:field mdschema="dc" element="comment" qualifier="hidden" lang="en">Parts of this thesis will appear in peer reviewed journals. The first part on &amp;quot;Wireless networks&amp;quot; is accepted to be published in &amp;quot;Transactions on Networking&amp;quot;. The second part on &amp;quot;Wired networks&amp;quot; has been submitted to the &amp;quot;Journal on Selected Areas in Communication (JSAC)&amp;quot; and is under review.</dim:field>
   <dim:field mdschema="dc" element="pending" lang="en">false</dim:field>
   <dim:field mdschema="uws-etd" element="degree" qualifier="department" lang="en">Electrical and Computer Engineering</dim:field>
   <dim:field mdschema="uws-etd" element="degree" lang="en">Doctor of Philosophy</dim:field>
   <dim:field mdschema="uws" element="typeOfResource" lang="en">Text</dim:field>
   <dim:field mdschema="uws" element="peerReviewStatus" lang="en">Unreviewed</dim:field>
   <dim:field mdschema="uws" element="scholarLevel" lang="en">Graduate</dim:field>
   <dim:field mdschema="others" element="access-status">open.access</dim:field>
</dim:dim>
</metadata></record></GetRecord></OAI-PMH>