Phoebus Wei-Chih Chen

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2009-75

May 20, 2009

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-75.pdf

Research in wireless sensor networks (WSNs) is moving from studies of WSNs in isolation toward studies where the WSN is treated as a component of a larger system. One hot area of research is the study of how to integrate wireless sensor networks with existing real-time measurement and control systems, forming what we call a wireless networked system. To apply the theories for studying real-time systems operating over wireless networks, for instance the theory of Networked Control Systems, we need to develop models of the lossy wireless communication medium. The models are used to compute network metrics, measures of network performance such as latency and reliability, that serve as an abstraction of the network which are used as input to the theoretical tools for analyzing the entire wireless networked system.

This dissertation focuses on modeling WSNs which use mesh networking with a TDMA data link layer. Specifically, it focuses on two classes of TDMA mesh networking schemes, Unicast Path Diversity (UPD) and Directed Staged Flooding (DSF). UPD uses retransmissions to get reliable packet delivery while DSF uses constrained flooding / multicast to get reliable packet delivery. We derive Markov chain models of UPD and DSF to compute the probability of end-to-end packet delivery as a function of latency, the expected radio energy consumption on the nodes from relaying packets, and the traffic distribution on the network. We also derive metrics based on clearly defined link failure models and routing models that allow a network designer to compare mesh routing topologies to determine which is better for reliable packet delivery. One of these network metrics leads to a greedy algorithm for constructing a mesh routing topology. Finally, we study the implications of using distributed scheduling schemes to generate schedules for WSNs. Particularly, we focus on the impact scheduling has on path diversity, using short repeating schedules and Greedy Maximal Matching scheduling as examples. A cluster-based scheduling scheme is proposed which works well on a subclass of network topologies.

Advisors: S. Shankar Sastry

---

BibTeX citation:

@phdthesis{Chen:EECS-2009-75,
    Author= {Chen, Phoebus Wei-Chih},
    Title= {Wireless Sensor Network Metrics for Real-Time Systems},
    School= {EECS Department, University of California, Berkeley},
    Year= {2009},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-75.html},
    Number= {UCB/EECS-2009-75},
    Abstract= {Research in wireless sensor networks (WSNs) is moving from studies of WSNs in isolation toward studies where the WSN is treated as a component of a larger system.  One hot area of research is the study of how to integrate wireless sensor networks with existing real-time measurement and control systems, forming what we call a wireless networked system.  To apply the theories for studying real-time systems operating over wireless networks, for instance the theory of Networked Control Systems, we need to develop models of the lossy wireless communication medium.  The models are used to compute network metrics, measures of network performance such as latency and reliability, that serve as an abstraction of the network which are used as input to the theoretical tools for analyzing the entire wireless networked system.

This dissertation focuses on modeling WSNs which use mesh networking with a TDMA data link layer.  Specifically, it focuses on two classes of TDMA mesh networking schemes, Unicast Path Diversity (UPD) and Directed Staged Flooding (DSF).  UPD uses retransmissions to get reliable packet delivery while DSF uses constrained flooding / multicast to get reliable packet delivery.  We derive Markov chain models of UPD and DSF to compute the probability of end-to-end packet delivery as a function of latency, the expected radio energy consumption on the nodes from relaying packets, and the traffic distribution on the network.  We also derive metrics based on clearly defined link failure models and routing models that allow a network designer to compare mesh routing topologies to determine which is better for reliable packet delivery.  One of these network metrics leads to a greedy algorithm for constructing a mesh routing topology. Finally, we study the implications of using distributed scheduling schemes to generate schedules for WSNs.  Particularly, we focus on the impact scheduling has on path diversity, using short repeating schedules and Greedy Maximal Matching scheduling as examples.  A cluster-based scheduling scheme is proposed which works well on a subclass of network topologies.},
}

EndNote citation:

%0 Thesis
%A Chen, Phoebus Wei-Chih 
%T Wireless Sensor Network Metrics for Real-Time Systems
%I EECS Department, University of California, Berkeley
%D 2009
%8 May 20
%@ UCB/EECS-2009-75
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-75.html
%F Chen:EECS-2009-75