Toronto Networking Seminar 2006

Throughput-optimal Configuration of Wireless Sensor Networks 

Catherine Rosenberg
Dept. of Electrical and Computer Engineering
University of Waterloo

Date:  March  31  3pm
Location: BA1210 (Bahen Center)


In this work we seek answers to two fundamental questions concerning data gathering wireless sensor networks; first, for a given placement of n sensors and the sink what is the maximum achievable throughput of the network?, and second, how should the network  i.e., the radio and link layer parameters at each sensor be configured to achieve this maximum? Unlike the popular "scaling" approach, we determine what is achievable but not through asymptotic results. We assume centrally computed TDMA link schedules and not a distributed MAC.  We show that routing and scheduling are intricately related.  We cast the problem of maximizing the network throughput as a nonlinear nonconvex optimization problem over the radio parameters (transmission power and modulation), routing and scheduling schemes. In a special case of fixed transmission power and modulation scheme, we show that the optimal throughput is determined by the maximum weighted clique of the contention graph prescribed by the radio parameters; the vertex weights in this graph equal the traffic carried by the corresponding link under the routing scheme that is optimal for power P. Moreover, the optimal link schedule is contention free and is also determined by the maximum weighted clique. For a grid topology with the sink in a corner, and all the sensors using the same radio parameters, we obtain the maximum throughput in a closed form under a two-circle interference model.  The optimal routing is such that in a certain region around the sink the traffic is routed using the shortest paths while the traffic outside this region flows in two branches deviating away from each other and finally getting fed into the region through the border sensors. Interestingly, of all feasible transmission powers, the power which allows sensors to transmit to the sink in one hop has the maximum throughput.


Born and educated in France (Ecole Nationale Supérieure des Télécommunications de Bretagne, ‘Diplôme d'Ingénieur’ in 1983 and University of Paris, Orsay, ‘Doctorat en Sciences’ in 1986) and in the USA (UCLA, MS in 1984), Dr. Rosenberg has worked in several countries including USA, UK, Canada, France and India. In particular, she worked for Nortel Networks in the UK, AT&T Bell Laboratories in the USA, Alcatel in France and taught at Purdue University (USA), Ecole Polytechnique of Montreal (Canada). Dr. Rosenberg is currently Chair of the Department of Electrical and Computer Engineering at the University of Waterloo, Canada, where she also holds a University Research Chair.  Her research interests are broadly in networking with currently an emphasis in wireless networking and in traffic engineering (Quality of Service, Network Design, and Routing). She has authored over 70 papers and has been awarded six patents in the USA.  Agencies and industries that have supported her research include USA NSF (National Science Foundation) NSERC (Natural Sciences and Engineering Research Council of Canada), FCAR (The Quebec counterpart of NSERC), CRC (Canadian Ministry of Communications), EEC (European Commission) while at Nortel Networks, ESA (European Space Agency) while at Nortel Networks, France-Telecom, CISCO, Bell Canada, and Nortel Networks.