Changeset 2791

Timestamp:

10/30/09 17:04:00 (4 weeks ago)

Author:

jortiz

Message:

first draft of final copy

Location:

code/Multichannel/docs/mobisys/doc

Files:

• abstract.tex (modified) (1 diff)
• conc.tex (modified) (1 diff)
• intro.tex (modified) (4 diffs)
• motivation.tex (modified) (6 diffs)
• references.bib (modified) (2 diffs)
• related.tex (modified) (2 diffs)
• report.tex (modified) (2 diffs)
• results.tex (modified) (31 diffs)
• setupandmeth.tex (modified) (12 diffs)
• sexton.tex (modified) (5 diffs)

code/Multichannel/docs/mobisys/doc/abstract.tex

@@ -13 +13 @@
 %hopping.
 
-We study the utility of dynamic frequency agility in real-world wireless sensor networks,
-which many view as essential to obtaining reliability in industrial environments.
-We introduce three graph-theoretic objects -- Multichannel Links (MCLs)
-and Multichannel Triangles (MCTs) --
-that identify instances in the network where considering multiple
-frequencies enables reliable communication.  We examine connectivity graphs
+We study the utility of dynamic frequency agility in real-world wireless sensor networks.
+Many view such agility as essential to obtaining adequate reliability in industrial environments.
+We quantify the actual utility by identifying the two facets of connectivity graph that
+yield potential benefits called Multichannel Links (MCLs) and Multichannel Triangles (MCTs),
+study how frequently these occur empirically and determine whether multihop provides
+a comparable solution without the complexity of switching channels.
+We examine connectivity graphs
 of live networks over each 802.15.4 channel and find that MCLs and MCTs
 are extremely rare in practice.  Almost no MCLs are found in any
-connectivity graph while MCTs occur between 0-500 parts per million (ppm).
+connectivity graph while MCTs occur between 0-200 parts per million (ppm).
 Furthermore, we show that MCLs are rarely important for routing while each
 MCT has a single-channel routing solution.  We also find that there are channels
 that are always good for connectivity and offer comparable routing costs, with respect
 to transmission count, in comparison to multichannel communication.
+Thus, the justification for channel agility in industrial environments applies in the 
+absence but not in the presence of multihop routing.
 %with the same cost in the expected
 %number of transmissions as the multichannel solution.

code/Multichannel/docs/mobisys/doc/conc.tex

@@ -3 +3 @@
 
 In this study, we examined the utility of dynamic frequency agility in real-world wireless sensor networks.
-To quantify the need for multichannel we examined Sexton's study on wireless links in the industrial 
-environment and pulled out a set of graphical facets, a Sexton Triangle, that could be directly tested for on
-live networks.  We also examined the related artifact, a Sexton Link.
+%To quantify the need for multichannel we examined Sexton's study on wireless links in the industrial 
+%environment and pulled out a set of graphical facets, a Sexton Triangle, that could be directly tested for on
+%live networks.  We also examined the related artifact, a Sexton Link.
+%
+%Our findings establish the following:
+%
+%\begin{itemize}
+%       \item Instances where a multichannel solution is necessary are
+%               extremely rare.  The graphical facet -- a Sexton
+%               Triangle -- occurs only about 20-50 parts per million (ppm). 
+%       \item In every instance where a multichannel solution is necessary
+%               for directional communication
+%               there is a single-channel routing solution available.
+%       \item The single-channel routing transmission cost is the same as the 
+%               multichannel transmission cost.  
+%\end{itemize}
+%
+%These results suggest that in the presence of routing, frequency agility is of marginal value
+%in improving reliability.
+We analyzed the set of assumptions related to the benefit of multichannel with respect to reliable
+packet transmission.  We reduced the problem to graph-theoretic facets that are searchable on network
+connectivity graphs -- multichannel links and multichannel triangles.  Our results suggest that 
+MCLs are rare in practice.
+Also, when the graph is disconnected, it is disconnected on \emph{every} channel.
+We also find that MCTs are extremely rare in practice and that there is a routing solution to every
+MCT on a single channel.  We demonstrated this on channel $26$.
+Furthermore, free channels are not difficult to find.  We easily determined which
+was the good channel.
 
-Our findings establish the following:
+These results show that, in the well-connected networks, multichannel communication is not necessary
+for reliable communication.  The standards bodies recommend the use of well connected networks and 
+provide a list of rules-of-thumb.  Yet, they also recommend the use of FH, which may only be of marginal
+value if the network setup is done correctly.
 
-\begin{itemize}
-        \item Instances where a multichannel solution is necessary are
-                extremely rare.  The graphical facet -- a Sexton
-                Triangle -- occurs only about 20-50 parts per million (ppm). 
-        \item In every instance where a multichannel solution is necessary
-                for directional communication
-                there is a single-channel routing solution available.
-        \item The single-channel routing transmission cost is the same as the 
-                multichannel transmission cost.  
-\end{itemize}
-
-These results suggest that in the presence of routing, frequency agility is of marginal value
-in improving reliability.

code/Multichannel/docs/mobisys/doc/intro.tex

@@ -4 +4 @@
 Reliability is of great concern for wireless sensing in
 industrial settings -- rooms with lots of metal surfaces and rotating
-machinery that make 
+machinery make 
 it a harsh environment for radio-frequency (RF) communication.  
 In~\cite{sexton}, Sexton et al. show that RF signals in this environment
@@ -14 +14 @@
 it~\cite{propwireless,fading},
 these standards bodies have agreed that frequency diversity is absolutely
-necessary to provide high levels of reliable wireless communication.
+necessary to provide high levels of reliability in wireless communication.
 
-Beyond the standards groups, there has been much work in the sensornet
+Beyond the standards groups, there has been much work in the research
 community to develop multichannel protocols.
-Many are evaluated in simulation~\cite{crowded, mmsn, mcmac_cit2006} while
-others have been implemented and evaluated in practice~\cite{ymac, pracmac,tsmp}. 
-Each work states various assumptions about the value of multiple channels,
+Many are evaluated in simulation~\cite{mcmac_cit2006,mmsn,crowded} while
+others have been implemented and evaluated in practice~\cite{tsmp,ymac,pracmac}. 
+Each study states various assumptions about the value of multiple channels,
 with some implicit validation.  However, the validation is mostly with respect to 
 network capacity.  None of the studies closely examine the contribution of multiple
-channels with respect to reliability.
+channels with respect to the primary motivation -- reliability.
 
 %but none evaluate the underlying validity and importance of those assumption. 
@@ -30 +30 @@
 
 Furthermore, these wireless devices form mesh networks and route over multiple hops.
-Routing is an alternative to frequency diversity in enabling communication among
-devices that cannot communicate directly.  It also provides receiver diversity.
+Routing enables communication among devices that cannot communicate directly.  
+Thus, it is an alternative to frequency diversity even for nodes that are in close
+proximity. It also provides receiver diversity.
 In this paper we find frequency diversity is not necessary for high reliability
 in the presence of routing.
 In practice, we show that even on a single channel, route diversity --  
-mulitple choices for routing at 
+multiple choices for routing at 
 each hop -- offers the same level of reliability
 % at the same transmission cost
 as the multichannel solution.
 
-To show this we distill the multichannel reliability assumption into two
+To show this we distill the multichannel reliability assumption into two observable 
 graph-theoretic objects that we can explicitly test for on live networks:
 Multichannel Links (MCLs) and Multichannel Triangles (MCTs).%, and Multichannel Paths (MCPs).  
 These objects capture locations  in the network where channel-switching is necessary for 
-reliable transmission.  After identifying instances of these objects
-we examine them with respect to routing on a \emph{single channel} to determine if there is routing 
-solution.
+the reliability of communication.  After identifying instances of these objects
+we examine them with respect to routing on a \emph{single channel} to determine if there is 
+also a routing solution.
 Our results establish the following:
 
 \begin{itemize}
         \item Although there are many unidirectional links, MCLs -- 
-                links that are unidirectional or non-existant on some channel
-                and bidirectional on another -- are rare.  This allows
-                for reachability between all nodes in the network through the 
-                underlying connectivity graph on every channel.
+                links that are unidirectional or nonexistent on some channel
+                and bidirectional on another -- are rare.  
+                %This allows
+                %for reachability between all nodes in the network through the 
+                %underlying connectivity graph on every channel.
         \item Instances where a multichannel solution is necessary are
-                extremely rare.  The graphical facet, an MCT --
-                instances in the network where three nodes are pairwise-connected on 
-                some channel but there is no single channel that connects all three
-                -- occurs only about 0-500 parts per million (ppm). 
+                extremely rare.  The graphical facet, an MCT 
+                %--
+                %instances in the network where three nodes are pairwise-connected on 
+                %me channel but there is no single channel that connects all three
+                %-- 
+                occurs only about 0-200 parts per million (ppm). 
         \item In every instance where a multichannel solution is necessary
-                for directional communication
+                for communication
                 there is a single-channel routing solution available.
         %\item Although MCPs -- paths between nodes that only exist with links
@@ -76 +80 @@
 
 This study focuses on communication \emph{reliability}.  That is, the successful
-delivery of data between nodes.   Reliability is a seperate concern from latency and
+delivery of data between nodes.   Reliability is a separate concern from latency and
 throughput.  One can obtain perfect reliability with high latency and low throughput
-(i.e. low duty-cycled applications).  Furthermore, we examine the deeper implications, 
-trade-offs, and associated costs between single and multichannel communication from a 
+by re-transmitting forever, but we want to achieve efficient reliability.
+Thus, we examine the  
+trade-offs and associated costs between single and multichannel communication from a 
 reliability stand-point.
 To the best of our knowledge this is the first study to systematically assess

code/Multichannel/docs/mobisys/doc/motivation.tex

@@ -1 +1 @@
 \section{Motivation}
 
-Sensornets are deployed in real-world environments and often
-use batteries as their main power source.
-On mote-class devices, the radio consumes the most energy~\cite{prabalbatch}.
-Therefore, reducing communication cost can significantly lengthen the lifetime of a deployment.
-This section discusses the challenges in efficient packet delivery
-and describes
-general approaches to dealing with the unpredictability of wireless
-signal propagation.
+Sensornets are deployed in real-world environments, often
+use batteries as their main power source, and
+on mote-class devices, the radio consumes the most energy~\cite{prabalbatch}.
+Communication cost is essential.
+As background, we describe general approaches to dealing with unpredictability
+of wireless signal propagation to obtain efficient packet delivery.
 
 \subsection{Wireless Propagation}
 
-\begin{figure}[t]
-\begin{center}
-\includegraphics[width=1.0\columnwidth]{../figs/80211_802154_spectrum}
-\caption{This figure shows the 2.4 GHz spectrum interval where both 802.11
-and 802.15.4 radios transmit.  The 802.11 channels shown are used most often
-in planned deployments.  When these are set there are four non-overlapping
-802.15.4 channels.}
-\label{fig:80211_802154_spectrum}
-\end{center}
-\end{figure}
+%\begin{figure}[t]
+%\begin{center}
+%\includegraphics[width=1.0\columnwidth]{../figs/80211_802154_spectrum}
+%\caption{This figure shows the 2.4 GHz spectrum interval where both 802.11
+%and 802.15.4 radios transmit.  The 802.11 channels shown are used most often
+%in planned deployments.  When these are set there are four non-overlapping
+%802.15.4 channels.}
+%\label{fig:80211_802154_spectrum}
+%\end{center}
+%\end{figure}
 
 Sensornets are deployed in various types of environments over extended
-periods of time.  As such, they are subject to unpredictable 
+periods of time and they are subject to unpredictable 
 internal and external interference, collisions, physical obstructions, and
-multipath fading.  Furthermore, these
+multipath fading.  These
 factors change over time and are non-uniform throughout the network.
 Different parts of the network may experience different phenomena
 that cause the connectivity to vary.
 
-Internal interference occurs when nodes in the same network do not hear one another
-and interfere each other's transmission.  Collisions are a form of internal 
+Internal interference may occur when nodes in the same network transmit simultaneously.
+Collisions are a form of internal 
 interference -- multiple senders, within transmission distance of one another, transmitting
 simultaneously to the same receiver -- and is avoided with
 Carrier Sense Multiple Access (CSMA).  However, hidden terminal problems
 may occur and CSMA does not solve the problem entirely. 
-Internal interference can be largely avoided by scheduling all transmissions 
-in the network, known as time-division multiple access (TDMA).  Still, if the schedule is
-not unique for all nodes, TDMA remains susceptible.
+Internal interference can be largely avoided by scheduling transmissions 
+in the network (e.g. time-division multiple access (TDMA)).  
 
 External interference occurs when devices outside the network generate RF
-that interferes with transmissions in the network. 
-For example, 802.11 shares the same RF frequency range as 802.15.4
-(shown in Figure~\ref{fig:80211_802154_spectrum}).  When a mote and an 802.11 client
-transmit on any overlapping frequency simultaneously, interference may occur.  Microwaves, 
-chordless phones
+signals that prevent reception. 
+For example, 802.11 shares the same RF frequency range as 802.15.4. 
+%(shown in Figure~\ref{fig:80211_802154_spectrum}).  
+When a mote and an 802.11 client
+transmit on any overlapping frequency, simultaneously, interference may occur.  Microwaves, 
+cordless phones
 and Bluetooth devices also transmit RF signals in the same frequency range
 and serve as external interferers to 802.15.4 networks.
+In industrial environments there may be many unintended source of RF interference.
 
-Mote placement also contributes to loss.  Non-line-of-site 
-(NLOS) transmission causes a signal to fade faster as it bounces off surfaces in the environment lengthening
-the distance the signal propagates and weakening its strength by time it reaches the receiver.  
+Placement also contributes to loss.  When there is Non-line-of-site 
+(NLOS) communication, signals bounce off surfaces in the environment lengthening
+the propagation distance, weakening its strength by time the signal reaches the receiver.  
 Moreover, reflections can cause destructive interference in certain locations
 and these locations change with changes in the environment.
@@ -61 +60 @@
 \subsection{Diversity Helps}
 
-To improve comunication robustness and reliability,  we introduce diversity 
-in time, space, and frequency.  Time diversity involves transmission retries and
-is implemented with a maximum bound (i.e. maximum of three retries).  The medium access control 
-(MAC), network, and transport
-layers, may all implement retries.  This allows the system to hide 
-much of the underlying packet delivery uncertainty. 
+To improve communication robustness and reliability,  diversity 
+in time, space, and frequency is utilized.  Time diversity involves transmission retries.  
+The link , network, and transport
+layers, may all implement retries.  
 
-Spatial diversity transforms the propogation phenomenon that causes multipath fading into
+Spatial diversity transforms the propagation problem that causes multipath fading into
 a feature by using either multiple antennas or various choices for receivers in
 the network.  Multiple-input multiple-output (MIMO) technology uses 
@@ -78 +75 @@
 
 Frequency diversity is used in various forms at different layers of the communication
-stack.  Modulation techniques such as direct-sequence spread spectrum (DSSS) and phase-shift
-keying (PSK), are used at the physical layer in order to minimize the effects of noise
-on a given channel.  Radios may also use frequency-hopping spread spectrum (FHSS).
-The sender and receiver share the same pseudorandom frequency-hop sequence in order to
-communicate across multiple channels.  Most multichannel MACs run on radios 
-using wideband modulation techniques and provide the additional frequency diversity at the 
-MAC layer.  Diversity helps to hide the wireless communication errors. 
+stack.  Modulation techniques, such as direct-sequence spread spectrum (DSSS), are used 
+at the physical layer in order to minimize the effects of noise
+on a given channel.  Radios may also use frequency-hopping spread spectrum (FHSS)
+to communicate using multiple channels.
+%The sender and receiver share the same pseudorandom frequency-hop sequence in order to
+%communicate across multiple channels.  
+Most multichannel MACs run on radios using wideband modulation techniques and provide 
+the additional frequency diversity by explicit channel hopping at the link layer. 
+
+Diversity helps to hide the wireless communication errors. 
 However, it is not clear how much each level of diversity improves communication reliability,
 as many of the mechanisms are redundant.
-
-Early version of the 802.11 standard used FHSS~\cite{80211_fhss}.  However, studies
+Early versions of the 802.11 standard used both FHSS and DSSS.  However, studies
 indicated 802.11 FHSS did not coexist well with other FHSS systems~\cite{80211_bluetooth} 
-and the standard eventually changed the modulation scheme to DSSS~\cite{80211_standard}.
+and the standard eventually changed the modulation scheme to only DSSS~\cite{80211_standard}.
 
 \subsection{Standardization}
@@ -96 +95 @@
 Three standards bodies have formed to address some of the issues just discussed (mostly in the context
 of WSN deployments in industrial settings).  
-In their proposals~\cite{802154e_ppt, whart} and standards~\cite{sp10011a}, they introduce many forms
+In their proposals~\cite{15_4e, whart} and standards~\cite{sp10011a}, they introduce many forms
 of diversity.  One is frequency diversity and the other is receiver diversity.  Many reasons are
 given to justify each level of redundancy.  With largely overlapping sets of goals, we
 examine the reasons more closely and analyze the underlying assumptions and related issues.
 
-Since the goals of the standards bodies are largely overlapping, so are the mechanisms to facilitate them.
-They include reliabile packet delivery, long deployment lifetime, adjustable quality-of-service (QoS), 
-and fault tolerance.  However, some goals are fundamentally at odds in their extreme, so the 
-mechanisms that are used must be composed such that the system performance falls in the right region 
-in the trade-off space.  Several claims can be pulled directly from the standards documents and 
+The goals of the standards efforts are include reliable packet delivery, long deployment lifetime, 
+adjustable quality-of-service (QoS), 
+and fault tolerance.  However, some goals are fundamentally at odds in their extreme, so  
+mechanisms are proposed to provide a compromise.
+Several claims can be pulled directly from the standards documents and 
 associated presentations.
 
-% FH by iteself
+% FH by itself
 First, it is stated that ``channel hopping [is used] to provide a level of immunity against interference
 from other RF devices operating in the same band, as well as robustness to mitigate multipath interference
@@ -119 +118 @@
 \end{enumerate}
 
-If these are the communication conditions then frequency-hopping (FH) \emph{may} help.  FH may be of no help
+If these communication conditions hold then frequency-hopping (FH) \emph{may} help.  FH may be of no help
 if it switches to another congested channel or may even \emph{hurt} performance by switching from a good
-channel to a congested one.
+channel to a congested one.  The non-zero cost of switching is wasted when there is nothing to send.
 
 % FH + mesh + TDMA
 Second, they explicitly state the use of TDMA ``to allow a device to access the RF medium without having to
 wait for other devices''~\cite{sp10011a} and multihop mesh networking to ``support end-to-end network 
-reliability in the face of changing RF and environmental conditions''~\cite{sp10011a}.  TDMA prevents
-collisions when two senders want to send to the same receiver, however, it is still susceptible to
+reliability in the face of changing RF and environmental conditions''~\cite{sp10011a}.  TDMA 
+does reduce internal interference by explicitly causing devices to wait.  Local scheduling
+is sufficient to prevent collisions to a common receiver but more global scheduling is required to avoid
+hidden terminals.  Still external interference remains.  FH is natural to include with TDMA but is
+orthogonal and does not come for free.  The more sparse the channel usage, the more costly is the join
+operation.
+TDMA prevents
+collisions when two senders want to send to the same receiver but is still susceptible to
 hidden and exposed terminal problems, as well as external interference.  Multihop mesh networking
-provides a way to route over the underlying connectivity graph.
-It is important to note that reliability, when routing over multiple hops, is about reachability in the 
-graph.  This is important to consider, as FH fundamentally affects the perceived connectivity
-graph, which may also affect overall reliability.
+allows for communication between nodes that are not directly connected for reasons of distance
+or interference.
+It is important to note that reliability, when routing over multiple hops is about reachability in the 
+connectivity graph.  This is important to consider, as FH fundamentally affects the available connectivity
+graph, which may also affect overall reliability.  Section~\ref{subsec:other_costs} examines the effects
+of FH on the connectivity graph and link quality.
 
-% Contraints -- battery life, predictability
-Third, we pull out a statement about the constraints, not the underlying assumptions.  Each standard's goals
+% Constraints -- battery life, predictability
+Third, each standard's goals
 includes a network lifetime constraint.  802.15.4e states that they wish to obtain ``long operational life
-for battery powered device ($>$ 5 years)''~\cite{802154e_ppt}.  This has deep implications on protocol
+for battery powered device ($>$ 5 years)''~\cite{15_4e}.  This has deep implications on protocol
 efficiency.  Given a fixed energy budget and lifetime constraints,
-you want to maximize the transmit efficiency.  How does FH affect the 
+we want to maximize the transmit efficiency.  How does FH affect the 
 communication efficiency and how does it compare with the single-channel case?
-
-%The next study played an important role establishing the ground-truth for adding FH to the standard(s).
-The next section discusses an important study that played a role in the ISA standard, SP100.11a.  The authors
-examine the behavior of wireless links in industrial environments and recommends the use of various forms
-of diversity -- FH being one of them.  We revisit the results of the study and argue that the conclusions
-would have been different had they considered routing as an alternative to FH.
-
 
 
 %The reliability argument is supported by several studies~\cite{sexton, propwireless, fading} characterizing
-%link behavior and signal propogation properties.  These findings, coupled with the strict
+%link behavior and signal propagation properties.  These findings, coupled with the strict
 %delivery requirements in industrial settings, have motivated the formation of several standards bodies.
 %These standard bodies --  802.15.4e~\cite{15_4e}, SP100.11a~\cite{sp10011a}, and WirelessHART~\cite{whart} --
@@ -157 +157 @@
 %and use frequency diversity (as per the recommendation in~\cite{sexton}) to improve communication predictability 
 %while extracting all the data from the network successfully.  The reliability argument based entirely on the 
-%studies cited, however none of the studies considers the effects of route diversity for reliabile communication
+%studies cited, however none of the studies considers the effects of route diversity for reliable communication
 %in a multihop wireless mesh network setting -- typical for sensornet deployments in industrial and 
 %non-industrial settings alike.

code/Multichannel/docs/mobisys/doc/references.bib

@@ -699 +699 @@
 }
 
-@misc{80211_fhss,
-        title = "IEEE 802.11 wireless lan medium access control (MAC) and physical
-                layer (PHY) specifications.",
-        author={IEEE}
-        year = {1999},
-}
-
 @INPROCEEDINGS{80211_bluetooth,
         title={Throughput of IEEE 802.11 FHSS networks in the presence of strongly interfering Bluetooth networks},
@@ -1823 +1816 @@
 }
 
-@misc{cc2420_datasheet,
-  title = "Chipcon CC2420.  CC2420 2.4 GHz IEEE 802.15.4/Zigbee-ready RF Transceiver Datasheet.",
-  note = "\url{http://focus.ti.com/lit/ds/symlink/cc2420.pdf}"
-}
-
 @article{SunlightModel,
   author = "Jaein Jeong", 

code/Multichannel/docs/mobisys/doc/related.tex

@@ -2 +2 @@
 \label{sec:related}
 
-With the increased ubiquity of wireless communication and the ever
-increasing saturation of the wireless spectrum, there has been a gold-rush
-effect in networking research communities to explore the multichannel
-protocol design space.  In the 802.11 research community there have
-been numerous publications in theory~\cite{optimal_mcmac,mcmac_eval},
-simulation~\cite{so03multichannel,ssch, apclient-driven}, 
-and practice~\cite{freemac,aptraffic-aware,apcoloring}.
+%There has been a gold-rush
+%effect in networking research community to explore the multichannel
+%protocol design space.  In the 802.11 research community there have
+%been numerous publications in theory~\cite{optimal_mcmac,mcmac_eval}, 
+%simulation~\cite{ssch,so03multichannel}, %, apclient-driven}, 
+%and practice~\cite{aptraffic-aware,apcoloring}%freemac,apcoloring}.
 
-%In the 802.11 research community, scientists
-%and engineers have been studying the ways to use frequency diversity
-%to increase throughput by decreasing losses related to internal
-%interference (in-network interference), external interference (micorwave,
-%phones, etc), and increase throughput by decreasing competition among nodes 
-%in the same collision domain (increased spatial reuse).  There have
-%been numerous publications theory~\cite{optimal_mcmac,mcmac_eval},
-%simulation~\cite{so03multichannel,ssch, apclient-driven}, 
-%and practice~\cite{freemac,aptraffic-aware,apcoloring}.
-
-%In 802.11-hotspot
-%locations where competition among clients and access points (AP) is high,
-%several protocol proposals have been made~\cite{apcoloring,apclient-driven,
-%aptraffic-aware} to increase the throughput seen per client.
-%Furthermore, with the proposal to use 802.11 devices in multihop, mesh
-%networks, there has been much work in multichannel MAC protocols
-%and their evaluation in theory~\cite{optimal_mcmac,mcmac_eval},
-%simulation~\cite{so03multichannel,ssch}, and 
-%practice~\cite{freemac}.
-
-%Naturally, multichannel research moved into the low-power wireless 
-%sensor networking community.  However, 
-The transition of multichannel MAC protocols into sensor networks 
-has not been straight-forward because of the fundamental differences between 
-802.11 and 802.15.4.  802.11 network devices are either plugged
-into a power source or recharged daily (laptops, smart phones, etc) and
-have radios that are always on.
-802.15.4 devices run at a much lower transmission power and generally run at very 
-low  duty cycles (between 1-7\%)~\cite{prabalbatch}.
-%in environments where energy is scarce the radio frequency environment is harsh.  
-802.11 radios transmit with more power and are more sophisticated than low-power
-802.15.4 radios, such at the CC2420~\cite{cc2420}.  802.11 wireless networks
-handle streaming data while most 802.15.4 networks transmit small amounts 
-of data once every dozens of minutes.
-
-While much effort in the sensornet community has 
-focused on link characterization~\cite{betafactor, SrinivasanDTL06,ZhouHKS06,lof,zuniga_trans} 
-and estimation~\cite{prabalbatch,rodrigo4bit} in the context
-of a single channel, these efforts have led to the most recent work in multichannel
-MAC protocols~\cite{crowded, mmsn, mcmac_cit2006,ymac, pracmac}.
-Since energy consumption is of highest priority and communication comsumes the most
-energy, reliability and efficiency is of utmost importance.
-Therefore, the focus of multichannel work has been to increase packet-delivery
+In sensornets, energy consumption is of highest priority and communication comsumes the most
+energy. Therefore reliability and efficiency is of utmost importance.
+The focus of multichannel work has been to increase packet-delivery
 reliability.  Throughput is a secondary goal as sensor networks mostly
 transmit at very low data rates and operate at low duty cycles.
+Several multichannel MACs have been built and studied for sensornets~\cite{mcmac_cit2006,
+ymac, pracmac, mmsn,crowded}.
 
 Y-MAC~\cite{ymac} and the Time Synchronized Mesh Protocol (TSMP)~\cite{tsmp} -- 
@@ -78 +39 @@
 to achieve better reliability.  
 
-Multipath is not the only problem for 802.15.4 networks.  802.11 interference
-is also a concern as both types of radios transmit in the same frequency
-and have channels that directly overlap, as shown in 
-figure~\ref{fig:80211_802154_spectrum}.  A few multichannel schemes have been 
-developed to minimize the effects of 802.11 intereference~\cite{80211_80154_testreport, 
-802_11_154_razvan, coexist_80211_802154}.
-
-There is no doubt that real-world RF behavior is unpredictable and that link qualities
-can vary quite drastically over time, space, and frequency.  However, fundamentally,
+Real-world RF behavior is unpredictable and that link qualities
+can vary over time.  However, fundamentally,
 protocols are constructing connectivity graphs over which to perform routing.
 We contend that RF and link qualities should not be evaluated in isolation.  Instead, 

code/Multichannel/docs/mobisys/doc/report.tex

@@ -60 +60 @@
 %\crdata{978-1-60558-096-8/08/09} 
 
-\title{Cost-Benefit Evaluation of Multiple Channels in Real World WSNs}
+%\title{Cost-Benefit Evaluation of Multiple Channels for Reliability in Real World WSNs}
+\title{Multichannel Reliability Assessment in Real World WSNs}
 
 %\title{Alternate {\ttlit ACM} SIG Proceedings Paper in LaTeX
@@ -133 +134 @@
 \input{setupandmeth}
 \input{results}
-%\input{related}
+\input{related}
 %\input{notes}
 %\input{methodology}

code/Multichannel/docs/mobisys/doc/results.tex

@@ +1 @@
+\begin{figure*}[!tbh]
+\centering
+\subfigure[Links found in the industrial setting.]{
+\includegraphics[width=0.3\textwidth]{../figs/basement_sextonlinks_view2}
+\label{fig:basement_sextonlinks}
+}
+\subfigure[Links found in the computer room.]{
+\includegraphics[scale=0.33]{../figs/machineroom_sextonlinks_view2}
+\label{fig:machineroom_sextonlinks}
+}
+\subfigure[Links found on the tested.]{
+\includegraphics[scale=0.33]{../figs/testbed_sextonlinks_view2}
+\label{fig:testbed_sextonlinks}
+}
+\caption[Optional caption for list of figures]{
+%A subset of the MCLs found in each environment.  
+Properties found in these links match those found in each industrial setting examined in~\cite{sexton}.
+However, we observe much wider bands of fading links.
+}
+\label{fig:expsextonlinks}
+\end{figure*}
+
 \section{Experimental Results}
 \label{sec:results}
@@ -16 +38 @@
 %For each MCT there exists a routing solution of comparable cost.
 
-\begin{figure*}[!tbh]
-\centering
-\subfigure[Links found in the industrial setting.]{
-\includegraphics[scale=0.33]{../figs/basement_sextonlinks_view2}
-\label{fig:basement_sextonlinks}
-}
-\subfigure[Links found in the computer room.]{
-\includegraphics[scale=0.33]{../figs/machineroom_sextonlinks_view2}
-\label{fig:machineroom_sextonlinks}
-}
-\subfigure[Links found on the tested.]{
-\includegraphics[scale=0.33]{../figs/testbed_sextonlinks_view2}
-\label{fig:testbed_sextonlinks}
-}
-\caption[Optional caption for list of figures]{
-%A subset of the MCLs found in each environment.  
-Properties found in these links match those found in each industrial setting examined in~\cite{sexton}.
-However, we observe much wider bands of fading links.
-}
-\label{fig:expsextonlinks}
-\end{figure*}
-
-
 Figure~\ref{fig:expsextonlinks} shows the equivalent of the connectivity measurements in \cite{sexton}
 for our test environments.  Since we have many more nodes in our networks, in the figure
@@ -45 +44 @@
 connectivity is nearly perfect on some channels while there is almost no connectivity on others.  
 The band of this fading is much less 'narrow' than in the Sexton study.  In general, there is 
-less connectivity between our nodes.  This does imply that the toplogy of connectivity seen
+less connectivity between our nodes.  This does imply that the topology of connectivity seen
 on one channel may be very different from that on other channels, which is likely to have
 a serious impact of routing protocols that use multiple channels.  Below we study the 
-observed connectivity under these graphs in much greater detail.
+observed connectivity under these graphs in greater detail.
 
 \subsection{Multichannel Links in Practice}
 \label{subsec:sextonlinksexp}
 
-Asymmentric links are indeed common in our networks.  The number of them also and varies substantially 
+Asymmetric links are indeed common in our networks.  The number of them also and varies substantially 
 by node placement, channel, link-quality threshold, and time.  We define a link between
 a pair of nodes as unidirectional if the PRR is greater than some threshold, $T$, in one direction 
-and less than $T$ in the other.  Although this may seem weak, it is effectively what occurs when
-a protocol sets a maximum transmission count.  For example, a maximum transmission count of 3
-implies a threshold of 33\% PRR.
-
-In examining our connectivity graphs in all environments and thresholds between $T=1$ and $T=90$ (with
-a step of 10), we observed that 32-36\% of the links in the machine room are
-unidirectional, 18-34\% of the links in the computer room are undirectional, and 10-46\% of 
+and less than $T$ in the other.  Although stranger criteria would be require a difference
+of $\epsilon$ around threshold $T$, we allow even a small difference to be most generous to the
+prevalence of situations where FH provides benefit.  The vast majority of potential links
+lie far from the threshold regardless.
+
+%Although this may seem weak, it is effectively what occurs when
+%a protocol sets a maximum transmission count.  For example, a maximum transmission count of 3
+%implies a threshold of 33\% PRR.
+
+In examining our connectivity graphs in all environments and thresholds between $T=1$ and $T=90$ with
+a step of 10, we observed that 32-36\% of the links in the machine room are
+unidirectional, 18-34\% of the links in the computer room are unidirectional, and 10-46\% of 
 the links on the testbed are unidirectional.  
 %These ranges are for all links and all runs
@@ -89 +93 @@
 sparse networks. 
 
-This may also suggest a small grey region in our deployments~\cite{zhao, SrinivasanDTL06} 
+This may also suggest a small gray region in our deployments~\cite{zhao,zuniga_trans} 
 -- locations in the network where connectivity
 between the sender and receiver are at the edge of radio connectivity.  Generally, the
-population of links in the grey region is small, since reliable communication
-is desirable and grey-region links have more unpredictable link quality~\cite{churn}.  Sparser networks 
+population of links in the gray region is small, since reliable communication
+is desirable and gray-region links have more unpredictable link quality~\cite{churn}.  Sparser networks 
 have more links at the edge of network connectivity
 and thus there may be some links that are above the goodness threshold on some channels
@@ -116 +120 @@
 
 This may indicate much wider noise correlation across channels in the operating frequency band.  This also
-directly addresseses the assumption made in the standards about FH's ability to avoid interference.  It can only
+directly addresses the assumption made in the standards about FH's ability to avoid interference.  It can only
 improve reliability if there is an opportunity to transmit on \emph{some} channel that is interference free.  
 According to our data,  that opportunity is quite rare.  Furthermore, this number is
@@ -127 +131 @@
 %graphs that were disconnected and there exists a connected multichannel graph.
 
-%disconnected graph occured on channel 17 and only a single node was disconnected.  However, the missing
+%disconnected graph occurred on channel 17 and only a single node was disconnected.  However, the missing
 %edge is not a member of an MCT, although it exists on other channels.  Therefore a multichannel solution
 %exists where a single-channel solution does not.  In order to capture these instances in the network, we
-%examine the prevalence of Mulichannel Paths (MCPs).
+%examine the prevalence of Multichannel Paths (MCPs).
 
 
@@ -169 +173 @@
 
 %From our data we were able to match the results found by Sexton et al.  However, this is not enough to declare
-%frequency diversity indepensible.  In order to get a better understanding of value for frequency agility in
+%frequency diversity indispensable.  In order to get a better understanding of value for frequency agility in
 %real networks, we have to examine cases where routing may be problematic.  In order to do this we examine
 %the second piece of the assertion, namely, the existence of MCTs.
@@ -181 +185 @@
 %In addition to this evaluation, we must also consider whether multichannel is the best or only solution
 %to communicate data over an MCT.  Therefore, we also examine how often we can communicate to each node
-%by simply considering the existence of a route path the includes all the nodes in the the instance of 
+%by simply considering the existence of a route path the includes all the nodes in the instance of 
 %an MCT.  We present the details of this analysis in section~\ref{sec:routingresults}.
 
@@ -191 +195 @@
 \centering
 \subfigure[Machine room multichannel triangle-set count.]{
-\includegraphics[angle=90,scale=0.14]{../figs/basement_mctrigs}
+\includegraphics[scale=0.26]{../figs/basement_mctrigs}
 \label{fig:basement_mc_demo}
 }
 \subfigure[Machine room triangle-set count.]{
-\includegraphics[angle=90,scale=0.14]{../figs/basement_sextontrigs}
+\includegraphics[scale=0.26]{../figs/basement_sextontrigs}
 \label{fig:basement_sexton_demo}
 }
 \subfigure[Computer room multichannel triangle-set count.]{
-\includegraphics[angle=90,scale=0.14]{../figs/machineroom_mctrigs}
+%\includegraphics[angle=90,scale=0.14]{../figs/machineroom_mctrigs}
+\includegraphics[scale=0.26]{../figs/machineroom_mctrigs}
 \label{fig:machineroom_mc_demo}
 }
 \subfigure[Computer room MCT-set count.]{
-\includegraphics[angle=90,scale=0.14]{../figs/machineroom_sextontrigs}
+\includegraphics[scale=0.26]{../figs/machineroom_sextontrigs}
 \label{fig:machineroom_sexton_demo}
 }
 \subfigure[Testbed multichannel triangles.]{
-\includegraphics[angle=90,scale=0.14]{../figs/motescope_run3_mctrigs}
+\includegraphics[scale=0.26]{../figs/motescope_run3_mctrigs}
 \label{fig:testbed_mc_demo}
 }
 \subfigure[MCTs on with N hop solution on testbed.]{
-\includegraphics[angle=90,scale=0.14]{../figs/motescope_run3_sextontrigs_diffchans}
+\includegraphics[scale=0.26]{../figs/motescope_run3_sextontrigs_diffchans}
 \label{fig:testbed_sexton_demo}
 }
@@ -223 +228 @@
 and all thresholds.  As a working example, when the threshold is set to 50\%, 
 the diameter of the machine room network is between 5-6 hops, the diameter of the computer room
-is between 2-3 hops and the diamter of the testbed is between 3-4 hops.
+is between 2-3 hops and the diameter of the testbed is between 3-4 hops.
 
 %In order to count MCTs, we first had to construct a connectivity graph on each
-%channel.  To do this we set the link PRR threhold to 50\% and remove all links that are not bi-directional.
+%channel.  To do this we set the link PRR threshold to 50\% and remove all links that are not bi-directional.
 %The 50\% threshold was set arbitrarily, however, in section~\ref{subsec:thresholding} we see that our results
 %hold true no matter what threshold is chosen.  The reason we include only bi-directional links
@@ -233 +238 @@
 %implemented at some layer of the stack (software or hardware).
 %The diameter of the machine room network is between 5-6 hops, the diameter of the computer room
-%is between 2-3 hops and the diamter of the testbed is between 3-4 hops.
+%is between 2-3 hops and the diameter of the testbed is between 3-4 hops.
 
 % What's the diameter of the network?
 
-%Sexton triangle demonstration in Industrial envrionment.
+%Sexton triangle demonstration in Industrial environment.
 
 Figure~\ref{fig:basement_mc_demo} and figure~\ref{fig:basement_sexton_demo} show the set of non-unique multichannel
@@ -263 +268 @@
 \label{fig:testbed_mctrates}
 }
-\label{fig:mcts_thresh_distro}
 \caption[Optional caption for list of figures]{MCT occurrence rate distribution for all experimental
 runs and link-quality thresholds.}
+\label{fig:mcts_thresh_distro}
 \end{figure*}
 
 Figure~\ref{fig:mcts_thresh_distro} summarizes our results. The boxplot shows the distribution of MCT
 occurrence rates for each run and threshold.  Observe that for all three environments, the MCT occurrence rate
-is extremely small.  The rates range from 0-550 ppm.  This indicates that MCTs are actually not that
+is extremely small.  The rates range from 0-200 ppm.  This indicates that MCTs are actually not that
 important to consider if your deployment is provisioned to be connected on a single channel -- since
 they occur so infrequently.
-Also observe the effects of thresholding on the MCT occurrence rate.  The general trend indicates that
-as the threshold increases, the rate of MCT occurrence increases by a multiplicative factor.
-In the machine room, the average rate increases by a factor of 10 from $T=1$ to $T=80$.  The general 
-trend repeats in the computer room and the testbed.  In the latter, the rate increases by a factor
-of 3 from $T=80$ to $T=90$.
-
-This results is rather counter-intuitive.  Initially, one might expect to observe more MCTs as the link population
-admits more grey-region links.  However, it is pricisely because of this that it MCTs are not found.
-Although there are many more non-unique multichannel triangles, the likelihood of an MCT decreases as the link
-choices increase since there are more choices for communication on every channel.  The reason it rises
+Also observe the effects of thresholding on the MCT occurrence rate.  In the machine room, the occurrence
+rate increases by almost a factor of 6 from $T=1$ to $T=80$. Only 2 MCTs were found in the computer room
+and the testbed did not significant variations.
+
+%The general trend indicates that
+%as the threshold increases, the rate of MCT occurrence increases by a multiplicative factor.
+%In the machine room, the average rate increases by a factor of 10 from $T=1$ to $T=80$.  The general 
+%trend repeats in the computer room and the testbed.  In the latter, the rate increases by a factor
+%of 3 from $T=80$ to $T=90$.
+
+%This results is counter-intuitive.  
+Initially, one might expect to observe more MCTs as the link population
+admits more gray-region links.  
+%However, it is precisely because of this that MCTs are not found.
+%Although there are many more non-unique multichannel triangles, the likelihood of an MCT decreases as the link
+%choices increase since there are more choices for communication on every channel.  
+The reason it rises
 so sharply is related to the link population distribution.  A vast majority of the link population is either
-really high quality or really poor (non-existant).  This is often referred to as a bimodal link distribution.
-As the threshold increases, we start excluding more and more links from the population at a faster rate 
+very high quality or very poor (nonexistent), i.e. a bimodal distribution.
+As the threshold increases, we exclude more links from the population at a faster rate 
 (for all the links on the ``good'' portion of the bimodal distribution).
+On the testbed, this is not as pronounced.
 
 Another interesting observation is the differences in the MCT occurrence rates across the three environments.
@@ -303 +316 @@
 %MCTs are extremely rare in our industrial facility.
 %
-%The network diameter changes as a function of threshold, as does the population of links in the grey region
+%The network diameter changes as a function of threshold, as does the population of links in the gray region
 %of connectivity~\cite{SrinivasanDTL06, ZhouHKS06, churn}.  As the number of nodes in at the edge of connectivity
 %decrease one might expect for the instance of MCTs to also decrease as the set of links
 %in the population improve in quality by definition.  By setting the threshold at 50\% we include links
-%that usually fall this is grey region.  In section~\ref{subsec:thresholding} we show that changing the threshold 
+%that usually fall this is gray region.  In section~\ref{subsec:thresholding} we show that changing the threshold 
 %does not affect the results.
 
@@ -345 +358 @@
 %that they are common, we did not find this to be true in our environments.  It is also interesting that
 %the rate at which they occur was actually \emph{higher} in the testbed than either of the other two environments.
-%The effects of having more nodes, with a larger set of nodes in the grey region, and significant 
+%The effects of having more nodes, with a larger set of nodes in the gray region, and significant 
 %802.11 interference may all contribute to this finding.  Still, the rate of occurrence of an MCT is
 %extremely small and calls to question the motivation for multichannel for reliability.
@@ -378 +391 @@
 \begin{table}
 \centering
+\begin{small}
 \begin{tabular}{|c|c|c|c|} \hline
 \textbf{Run ID}&\textbf{MCTs}&\textbf{2-Hop}&\textbf{N-hop}\\ \hline
@@ -398 +412 @@
 17 &   81  &  75&     6 \\ \hline
 \end{tabular}
-\caption{Routing Solutions on Testbed.}
+\end{small}
+\caption{Routing solutions on testbed with threshold set at 50.}
 \label{tab:testbedroutingsoln}
 \end{table}
@@ -405 +420 @@
 \subsubsection{Channel Distribution}
 Table~\ref{tab:testbedroutingsoln} shows the associated routing solution count for each MCT found on
-testbed ($T=50$).  Notice, every MCT has a single-channel routing solution.  Furthmore, the vast majority 
+testbed ($T=50$).  Notice, \emph{every MCT has a single-channel routing solution}.  The vast majority 
 of routing solutions are two hops in length.  Similar results are seen for all thresholds in each
 all environments tested.  This demonstrates that there is \emph{some channel} channel that provides
@@ -411 +426 @@
 that is good for the entire network to use.
 
-Due to a lack of space, we did not include the channel distribution graph.  However, we observe that
-there are route solutions on every channel where the MCT has an edge.  Furthermore, as stated earlier,
+We observe that the channel distribution graph shows that every channel where an MCT has an edge
+there is also a route solution.
+Furthermore, 
 the machine room and computer rooms connectivity graphs were connected for all experimental runs
-and the testbed was connected over 98\% of the time.  This means that every channel was good for routing
-almost all the time, except on the testbed.  Even on the testbed, channels 25, and 26 were free
-and connected the entire time, for all runs and all experiments.
-Finding the best communication channel might be easier than expected.  With a spectrum analyzer and
+and the testbed was connected over 98\% of the time.  On the testbed, channels 25 and 26 were free, 
+for all runs and all experiments.
+Finding the best communication channel was easier than expected.  With a spectrum analyzer and
 an engineered network deployment (i.e. Wireless HART's recommendation to have 3 neighbors per node), 
-one can choose a single channel over which to route over reliably for the lifetime of the network.
+one can choose a single channel over which to route over, reliably, for the lifetime of the network.
 
 %The channel distribution graphs show the total number of routing solutions (2, 3, and n-hop) on
@@ -455 +470 @@
 %\end{figure*}
 
-In this section we take a closer examination of the use of routing in cases where an MCT is present.
+%In this section 
+We take a closer examination of the use of routing in cases where an MCT is present.
 In our evaluation, we make two important assumptions. First, we assume
 expected transmission count (ETX) can serve as a proxy for energy consumption.  Second,
@@ -485 +501 @@
 \begin{figure}[!tb]
 \centering
-\includegraphics[width=\columnwidth,scale=0.25]{../figs/2hopdemo}
-\caption{Two-Hop single-channel solutions in a Multichannel Triangle instance.
+\includegraphics[scale=0.25]{../figs/2hopdemo}
+\caption{Two-hop single-channel solutions in a Multichannel Triangle instance.
 }
 \label{fig:routingdemo}
@@ -579 +595 @@
 \label{fig:testbed_cost_cdf}
 }
-\label{fig:routingcosts}
 \caption[Optional caption for list of figures]{Single-channel to multichannel communication cost ratio
-comparison.}
+comparison.  The connectivity graph constructed with threshold T=50 and the routing channel is 26.
+}
+\label{fig:costratios}
 \end{figure*}
 
@@ -593 +610 @@
 %case.
 
-Figure~\ref{fig:routingcosts} and ~\ref{tab:costratio_machine} shows the routings costs for all
+Figure~\ref{fig:costratios} shows the routings costs for all
 routing solutions in the each of our environments.  These were calculated with the link-quality
 threshold set at 50\%.
@@ -605 +622 @@
 
 Of course, this is only part of the cost comparison as there are many other protocol-dependent factors
-that may lead to inefficiencies in energy consumption for either single or multichannel communication.
-However, this sets a basis for comparison based on transmission links alone and can be used as a guidance
-for understanding the tradeoffs between both choices.
-
-The next section considers how changes in the connectivity graph, by changing the threshold, affects 
-the routing solutions and associated costs.
+that may lead to inefficiencies in energy consumption. 
+%for either single or multichannel communication.
+However, this sets a basis for comparison based on transmission links.% and can be used 
+%as a guidance
+%kfor understanding the tradeoffs between both choices.
+
+%The next section considers how changes in the connectivity graph, by changing the threshold, affects 
+%the routing solutions and associated costs.
 
 %\begin{figure}[tb!]
@@ -625 +644 @@
 \begin{table}
 \centering
+\begin{small}
 \begin{tabular}{|c|c|c|} \hline
 \textbf{Run ID}&\textbf{Best}&\textbf{Worst}\\ \hline
@@ -634 +654 @@
 6 & 1.5 & 1.5  \\ \hline
 \end{tabular}
-\caption{Cost ratio comparison for the machine room.}
+\end{small}
+\caption{Cost ratio comparison for the machine room.  Threshold set to 50, routing solutions channel
+set to 26.}
 \label{tab:costratio_machine}
 \end{table}
-
 
 \subsubsection{Link Threshold Effects On Ratio}
@@ -657 +678 @@
 \label{fig:testbed_threshold_costratio}
 }
+\caption[Optional caption for list of figures]{Cost ratios in each environment as a function of
+link-quality threshold on the connectivity graph.}
 \label{fig:testbed_threshold_costratios}
-\caption[Optional caption for list of figures]{Cost Ratios in each environment as a function of
-link-quality threshold on the connectivity graph.}
 \end{figure*}
 
-Recall that to contruct a connectivity graph, one must set an initial threshold
+Recall that to construct a connectivity graph, one must set an initial threshold
 on the population of links in the traces.  For the results that have thus far been shown, 
 the link threshold was set at 50\%.
@@ -679 +700 @@
 of threshold.  Note the slight increase in cost for the testbed routing solution.
 As the threshold increases, the link-population choice becomes shorter in length and the choices
-available are essentially the same for both the multichannel and single-channel solutions
-and the ratios do not change very much.
+available are essentially the same for both the multichannel and single-channel solutions,
+so the ratios do not change very much.
 
 %However, this may suggest that routing is more expensive if there is high link-quality threshold
@@ -699 +720 @@
 
 \subsection{Other Associated Costs}
+\label{subsec:other_costs}
 
 \begin{table}
 \centering
+\begin{small}
 \begin{tabular}{|c|c|c|} \hline
 \textbf{Protocol}&\textbf{ROM}&\textbf{RAM}\\ \hline
@@ -709 +732 @@
 B-MAC w/LPL + ACK & 4386 & 277 \\ \hline
 \end{tabular}
-\caption{Example code size comparsion in bytes between single and multichannel
+\end{small}
+\caption{Example code size comparison in bytes between single and multichannel
 MAC protocols.~\cite{pracmac, bmac}
 }
@@ -715 +739 @@
 \end{table}
 
-A good indication of code complexity is code size, and it matters.
+A good indication of code complexity is code size. %, and it matters.
 Reducing the complexity of the protocol reduces the state and the likelihood of race 
 conditions~\cite{bmac}.  Therefore it is desirable to keep code size small.  Table \ref{tab:codesize}
-shows the code sizes of the default single-channel MAC is TinyOS and compare the size against
-an implemetation of a multichannel MAC protocol also written in TinyOS.  Notice the difference
-in code size.  PracMac is almost 5 times larger in RAM and more than twice as large in ROM.
-Furthermore, motes are resource contrained, and the larger the stack, the smaller the space
+shows the code sizes of the default single-channel MAC in TinyOS, B-MAC, and compares the size against
+an implementation of a multichannel MAC protocol also written in TinyOS, PracMac~\cite{pracmac}.  
+PracMac is almost 5 times larger in RAM and more than twice as large in ROM.
+Furthermore, motes are resource constrained, and the larger the stack, the smaller the space
 for applications.
 
-We simulated FH on the testbed data set, run ID 1,  using first of five pre-set hop sequences.
-The link qualities using this hop sequence, we were able to construct a sparse connectivity graph with
-poor links.  Although the simulation is not realistic, it may indicate a problem with FH in an 802.11-rich
+We also simulated FH on the testbed data set, run ID 1,  using first of five pre-set hop 
+sequences~\cite{sp10011a}.
+The links formed by this process were of very poor quality (about 25\% or below PRR)
+We were able to construct a sparse, poorly connected graph.  
+Although the simulation is not realistic, it may indicate a problem with FH in an 802.11-rich
 environment.  As mentioned earlier, there are 7 access points sitting amongst the nodes on the testbed.
 With the access point center frequencies set to 802.11 channels 1, 6, and 11, there are only 4 of the possible 16
-channels that do not overlap 802.11 transmissions.  Therefore, the hop sequence, chooses a ``bad'' channel
-75\% of the time.  SP100.11a and Wireless Hart are certainly aware of this and make explicit recommendations
-to blacklist the 802.11 channel a priori.  We suspect that if this is done in the testbed environment, the
-links qualities will not differ from remaining on a single, good channel (since FH is left to choose
+channels that do not overlap 802.11 transmissions.  Therefore, the hop sequence chooses a ``bad'' channel
+with about 75\% of the time.  SP100.11a and Wireless Hart are certainly aware of this and make explicit recommendations
+to blacklist the 802.11 channels a priori.  We suspect that if this is done in the testbed environment, the
+links qualities will not differ from that of remaining on a single, good channel (since FH is left to choose
 from only top remaining channels).
 
@@ -747 +773 @@
 data-exchange channel, the scanning and negotiation overhead is non-negligible.
 
-Another multichannel approach couples time-synchronization with multichannel communication 
-and schedules both frequency and transmission-time slots.  This scheme removes the need for scanning, 
-however, it requires message-exchange synchronization overhead (usually 1 packet sent by every node 
-every 30 seconds~\cite{ftsp} --
-with the 30-second period adjusted according to clock-drift and deployment size). 
-At this rate each node sends 2880 synchronization packets per day and in the worst case receives
-some fraction of that from each neighbor.  Packet reception incurs slightly more cost (19.7 mA)
-on the CC2420 then transmitting (17.4 mA)~\cite{cc2420} making the synchronization-flood
-overhead non-negligible.
-Furthermore, without active channel-noise observations
-the schedule may choose poor channels while hopping which can potentially drive up the communication
-cost unnecessarily.
-
-
+In the FH case, the overhead is still non-negligable.  SP100.11a uses a send frame of 10 ms.
+In this frame, approximately 5 packets can be sent.  If the offered load is greater than 5 packets
+($>$ 300 bytes) the sender and receiver must both switch channels.  Switching channels
+takes 1.4 ms, or 14\% overhead.  Single-channel communication would not incur any extra overhead
+if a good channel is chosen.
+
+Of course, single-channel communication is not free.  Some pre-provisioning and planning is necessary.
+One must survey the deployment environment, choose the right channel, and test the connectivity over time.
+One must also set up the network.  However, you have to do this anyway, according to SP100.11a and WirelessHART,
+as both make recommendations about topology properties and blacklisting.
+Still, FH may offer higher network capacity, as multiple senders in the same space can transmit simultaneously
+with interfering with one another.
+
+%Another multichannel approach couples time-synchronization with multichannel communication 
+%and schedules both frequency and transmission-time slots.  This scheme removes the need for scanning, 
+%however, it requires message-exchange synchronization overhead (usually 1 packet sent by every node 
+%every 30 seconds~\cite{ftsp} --
+%with the 30-second period adjusted according to clock-drift and deployment size). 
+%At this rate each node sends 2880 synchronization packets per day and in the worst case receives
+%some fraction of that from each neighbor.  Packet reception incurs slightly more cost (19.7 mA)
+%on the CC2420 then transmitting (17.4 mA)~\cite{cc2420} making the synchronization-flood
+%overhead non-negligible.
+%Furthermore, without active channel-noise observations
+%the schedule may choose poor channels while hopping which can potentially drive up the communication
+%cost unnecessarily.
+
+

code/Multichannel/docs/mobisys/doc/setupandmeth.tex

@@ -3 +3 @@
 
 %Three different environments, many motes covering each space.
-In this section we describe our experimental setup.  To examine RF characteristics
+To examine RF characteristics
 and connectivity we placed a set of 
 motes in three distinct environments: an industrial machine room environment 
@@ -15 +15 @@
 and narrowband fading.   The main source of loss in the industrial setting
 is due to NLOS communication and multipath-induced narrowband fading.  We
-observed some external interference but activity was sporatic and short-lived.
+observed some external interference but activity was sporadic and short-lived.
 Most of the communication between motes in the computer room and testbed
 is NLOS.  Furthermore, both settings are subject to 802.11 interference
@@ -22 +22 @@
 %Placement of motes in the industrial setting is
 %a factor as NLOS communication, metal surfaces, and rotating machinery affect wireless
-%signal propogation.
+%signal propagation.
 %Both the computer room and testbed are subject to
 %802.11 traffic and NLOS communication.  
@@ -32 +32 @@
 the b6lowpan~\cite{b6lowpan} stack.   Motes handle various experiment commands which
 are delivered over the routing tree constructed by the stack.  Data is also collected 
-over the routing tree after each experiment.  For the testbed we used the ethernet 
-backchannel for command delivery and data collection.
+over the routing tree after each experiment.  For the testbed we used the Ethernet 
+back-channel for command delivery and data collection.
 
 %For both the industrial setting and machine room we used the b6lowpan~\cite{b6lowpan}
@@ -48 +48 @@
 %placed in sensing and routing-relevant locations.
 For the machine room and computer room we placed motes in locations in the network 
-where sensing might take place.  In the machine room(s), we placed motes on top of moving engines
-and between pipes.  The machine room deployment in seperated into two
-seperate rooms that are side by side.  Both rooms have similar equipment and are seperated
-by a wall.  We placed motes in both rooms and tested connetivity among all the motes
+where sensing might take place.  In the machine room, we placed motes on top of moving engines
+and between pipes.  The machine room deployment in separated into two
+separate rooms that are side by side.  Both rooms have similar equipment and are separated
+by a wall.  We placed motes in both rooms and tested connectivity among all the motes
 in the deployment.  Similarly, we placed motes inside computer racks, next to active
 air conditioning units, and at varying heights inside the computer room.
 
 On the testbed we had no choice in node placement.  Nodes are scatter on the ceiling across
-an entire floor in an office environment.  The motes sit amongst active 802.11 acces points
+an entire floor in an office environment.  The motes sit amongst active 802.11 access points
 that see a varying number of clients and activity throughout the day.  Since
 the floor is partitioned into several rooms, many of the links are NLOS.
@@ -73 +73 @@
 which uses the CC2420 radio.
 
-\begin{figure}[h!]
-\begin{center}
-\includegraphics[width=0.7\columnwidth]{../figs/basement_node_placement}
-\caption{Industrial Environment Nodes Placement map.
-}
-\label{fig:basement_node_placement}
-\end{center}
-\end{figure}
-
+%\begin{figure}[h!]
+%\begin{center}
+%\includegraphics[width=0.7\columnwidth]{../figs/basement_node_placement}
+%\caption{Industrial Environment Nodes Placement map.
+%}
+%\label{fig:basement_node_placement}
+%\end{center}
+%\end{figure}
+%
 \begin{figure}[h!]
 \begin{center}
 \includegraphics[width=0.8\columnwidth]{../figs/basement_pic}
-\caption{Industrial environment setting.
+\caption{Machine room setting.
 }
 \label{fig:basement_pic}
 \end{center}
 \end{figure}
+%
+%\begin{figure}[h!]
+%\begin{center}
+%\includegraphics[width=0.9\columnwidth]{../figs/machine_room_node_placement}
+%\caption{Machine room node placement.  The larger dot on the map denotes an
+%802.11 access point.
+%}
+%\label{fig:machine_room_node_placement}
+%\end{center}
+%\end{figure}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\begin{figure*}[!tbh]
+\centering
+
+\subfigure[Machine room node placement map.]{
+\includegraphics[width=0.3\textwidth]{../figs/basement_node_placement}
+\label{fig:basement_node_placement}
+} 
+\subfigure[Computer room node placement.  The larger dot on the map denotes an
+802.11 access point.]{
+\includegraphics[width=0.3\textwidth]{../figs/machine_room_node_placement}
+\label{fig:machine_room_node_placement}
+} 
+\subfigure[Testbed node placement.  The larger dots on the map denote the placement
+of 802.11 access points.]{
+\includegraphics[width=0.3\textwidth]{../figs/testbed_placement}
+\label{fig:basementlayout}
+}
+
+\label{fig:node_placement_maps}
+\caption[Optional caption for list of figures]{}
+\end{figure*}
 
 We use the WiSpy spectrum analyzer~\cite{wispy24} to characterize the RF environment 
 and find some RF noise generated near engines in the room.
-RF activity is sporatic and spread throughout the frequency band however we do not 
+RF activity is sporadic and spread throughout the frequency band however we do not 
 examine this data very closely, since it does not seem to affect our results.  
 
 \subsubsection{Computer Room Setup}
 Like the machine room, motes were placed in locations where sensing might take place.
-For example, motes were placed inside racks, near air conditioners, at the extremeties of the
+For example, motes were placed inside racks, near air conditioners, at the extremities of the
 room and at different heights.  The room is 28x28 feet and we placed 23 telosb motes throughout
 the room.
@@ -108 +144 @@
 shows the node placement overlayed on the map of the room.
 
-\begin{figure}[h!]
-\begin{center}
-\includegraphics[width=0.9\columnwidth]{../figs/machine_room_node_placement}
-\caption{Machine room node placement.  The larger dot on the map denotes an
-802.11 access point.
-}
-\label{fig:machine_room_node_placement}
-\end{center}
-\end{figure}
-
-There is an access point sitting on the ceiling in the middle of the computer room.  We actually
+There is an access point sitting on the ceiling in the middle of the computer room.  We
 ran the experiments in the evening during the spring break session, so the RF activity was
 fairly low for each run.
 
 \subsubsection{Testbed Setup}
-On the testbed mote are placed to allow for full network connectivity.  This is the largest 
+On the testbed, motes are placed to allow for full network connectivity.  This is the largest 
 of the 3 deployments we examined, with 55-60 MicaZ~\cite{MicaZ} motes. Floor dimensions are 
-128x128 and it is partitioned into multiple rooms in an office environment.
+128x128 feet and it is partitioned into multiple rooms in an office environment.
 Since the testbed is inside the computer science building of the university it sees
 lots of human traffic and 802.11 activity.   There are 7 access points 
@@ -131 +157 @@
 the day.
 
-\begin{figure}[h!]
-\begin{center}
-\includegraphics[width=0.9\columnwidth]{../figs/testbed_placement}
-\caption{Testbed node placement.  The larger dots on the map denote the placement
-of 802.11 access points.
-}
-\label{fig:basementlayout}
-\end{center}
-\end{figure}
+%\begin{figure}[h!]
+%\begin{center}
+%\includegraphics[width=0.9\columnwidth]{../figs/testbed_placement}
+%\caption{Testbed node placement.  The larger dots on the map denote the placement
+%of 802.11 access points.
+%}
+%\label{fig:basementlayout}
+%\end{center}
+%\end{figure}
 
 %RF environment description.
@@ -186 +212 @@
 three times and the testbed 17 times continuously over the span of a week.
 
+\subsubsection{Analytical Approach}
+\label{subsec:analytical}
+
+
+Each broadcast packet contains a sender ID and a local sequence number.  When a node receives 
+a broadcast packet it extracts both of these values and logs them along with its own ID
+and  current channel.  The testbed experiment also logs timestamp and received signal-strength
+indicator (RSSI) values.  Using this information we separate the data set into bins 
+separated by channel and use each subset to study the connectivity graph on
+each channel.
+
+For each directional link in the connectivity graph we calculate the PRR
+and set a threshold on link quality to construct the connectivity graph.
+We then run the MCL and MCT locaters on the traces as well as 
+Dijkstra's shortest-path algorithm.  In calculating the cost of transmission
+over a link, we use the expected transmission count (ETX) metric and compute the sum for all links
+along a path to determine its cost.  Equation~\ref{eqn:etx} shows how to calculate
+ETX; $l_f$ is the forward link PRR and $l_b$ is the backward link PRR.
+
+\begin{equation}
+ETX = \frac{1}{l_{f} * l_{b}}
+\label{eqn:etx}
+\end{equation}
+
+After the construction of a graph for each channel we count the number MCLs.
+For each link on a particular channel, we search for the same link the exists in only one
+direction on any channel.  If the link is either not found or it exists
+unidirectionally on some channel, it is added to the set of MCLs.  This
+set enumerates the number of opportunities there are for multichannel to enable communication
+between a pair of nodes.  In addition, we ran connectivity tests for all the observed
+connectivity graphs using Tarjan's connectivity algorithm.%~\cite{}.
+
+In the search for MCTs we create various sets that 
+consist of 3-tuples of unique nodes in the network that share bi-directional links 
+between each other.  The first set, the \emph{single-channel set}, takes every set 
+of three nodes in the network that are bi-directionally connected on a \emph{single} channel.  
+For example, if there exists bi-directional links $(i,j)$, $(i,k)$,
+and $(j,k)$ for unique nodes $i$, $j$, and $k$ and each link is on the same channel, then it 
+is included in the single-channel triangle set, also referred to as set $S$.
+
+We also construct another set, similar to set $S$, except that the constraints on the links 
+are loosened to include triangles that occur across channels.  Therefore, if there exists 
+bi-directional links $(i,j)$, $(i,k)$, and $(j,k)$ for unique nodes $i$, $j$, and $k$ on 
+\emph{any} channel, then it is included in the global multichannel triangle set, hereafter referred 
+to as set $M$.
+
+Finally we construct the set of interest, the \emph{MCT set}.  This set includes 
+all element in set $M$ that are not in set $S$.  In other words, it includes all sets of 3 nodes 
+that are not connected on a single channel but are connected on multiple channels -- the 
+definition of an MCT.  We refer to this set at set $M_u$ (unique multichannel 
+triangles).
+
+%For each element in set $M_u$, the MCT set, we examine if there exists a routing 
+%solution and separate each solution into the number of hops in the shortest path route.  
+%The 2-hop routing solution is each element of $M_u$ where any two bi-directional links are 
+%on the same channel.  This assume that the sender wants to send the same data to each node 
+%in the triangle.  The multichannel solution is only possible by switching channels, however, 
+%routing over a 2-hop path using the links in the triangle also works.
+%Figure~\ref{fig:2hopdemo} shows a demonstration of the 2-hop solution to an MCT
+%where $i$ is the source and either $j$ or $k$ is the destination.
+
+%Similarly, we construct the sets for routing solutions that consist of 3 hops and N hops.  
+%The route must be on a single channel and include all three nodes, $i, j, $ and $k$ where 
+%one of the three nodes is considered the source, another is considered the destination, and 
+%the last node is on the path from the source  to the destination.  For each route calculation 
+%we use Dijkstra's shortest path algorithm using the link ETX's as the link weights.
+%The key is to minimize the ETX sum between the source and destination.
+%Figure~\ref{fig:Nhopdemo} shows a demonstration of the N-hop solution to an MCT
+%where $i$ is the source and $j$ or $k$ is the destination.
+
+
 \subsubsection{How representative are samples?}
 Commands from the experiment
@@ -204 +301 @@
 
 In capturing directional properties of links it may be worrisome that each link samples 
-(100 packets) in either direction may be seperated by at $2N + \epsilon$ sample times, 
+(100 packets) in either direction may be separated by at $2N + \epsilon$ sample times, 
 where $N$ is the number of nodes
 in the network and $\epsilon$ is the a small random wait time caused by stalls and retries.
-This kind of seperation between samples may statistically decorrelate the measurements in
+This kind of separation between samples may statistically de-correlate the measurements in
 either direction.  However, by taking many samples we can bound of the error for
-the PRR measured in each direction of a bi-directional link.  Furthermore, the main
+the packet reception rate (PRR) measured in each direction of a bi-directional link.  Furthermore, the main
 source of uncertainty -- external interference and changes in the environment -- are effectively
 removed from the two experiments with the least number of samples.  The industrial
@@ -224 +321 @@
 %
 %\emph{Each direction of a link between a pair of nodes is not done consecutively
-%or interleaved.  They are seperated by at most $2N + \epsilon$ seconds apart where
+%or interleaved.  They are separated by at most $2N + \epsilon$ seconds apart where
 %$N$ is the number of motes in the experiment and $\epsilon$ is some random period
 %for command-send retries.}
@@ -231 +328 @@
 %
 %Basement had little to no RF
-%interference, location of motes and orientation of mote attenas did not change.
-
-\subsubsection{Analytical Approach}
-\label{subsec:analytical}
-
-
-Each broadcast packet contains a sender ID and a local sequence number.  When a node receives 
-a broadcast packet it extracts both of these values and logs them along with its own ID
-and  current channel.  The testbed experiment also logs timestamp and received signal-strength
-indicator (RSSI) values.  Using this information we seperate the data set into bins 
-seperated by channel and use each subset to study the connectivity graph on
-each channel.
-
-For each directional link in the connectivity graph we calculate the packet reception rate (PRR)
-and set a threshold on link quality to construct the connectivity graph.
-We then run the MCL and MCT locaters on the traces as well as 
-Dijkstra's shortest-path algorithm.  In calculating the cost of transmission
-over a link, we use the expected transmission count metric and compute the sum for all links
-along a path to determine its cost.  Equation~\ref{eqn:etx} shows how to calculate
-ETX; $l_f$ is the forward link PRR and $l_b$ is the backward link PRR.
-
-\begin{equation}
-ETX = \frac{1}{l_{f} * l_{b}}
-\label{eqn:etx}
-\end{equation}
-
-After the construction of a graph for each channel we count the number MCLs.
-For each link on a particular channel, we search for the same link the exists in only one
-direction on any channel.  If the link is either not found or it exists
-unidirectionally on some channel, it is added to the set of MCLs.  This
-set enumerates the number of opportunities there are for multichannel to enable communication
-between a pair of nodes.  In addition, we ran ran connectivity tests for all the observed
-connectivity graphs using Tarjan's connectivity algorithm.%~\cite{}.
-
-In the search for MCTs we create various sets that 
-consist of 3-tuples of unique nodes in the network that share bi-directional links 
-between each other.  The first set, the \emph{single-channel set}, takes every set 
-of three nodes in the network that are bi-directionally connected on a \emph{single} channel.  
-For example, if there exists bi-directional links $(i,j)$, $(i,k)$,
-and $(j,k)$ for unique nodes $i$, $j$, and $k$ and each link is on the same channel, then it 
-is included in the single-channel triangle set, also referred to as set $S$.
-
-We also construct another set, similar to set $S$, except that the constraints on the links 
-are loosened to include triangles that occur across channels.  Therefore, if there exists 
-bi-directional links $(i,j)$, $(i,k)$, and $(j,k)$ for unique nodes $i$, $j$, and $k$ on 
-\emph{any} channel, then it is included in the global multichannel triangle set, hereafter referred 
-to as set $M$.
-
-Finally we construct the set of interest, the \emph{MCT set}.  This set includes 
-all element in set $M$ that are not in set $S$.  In other words, it includes all sets of 3 nodes 
-that are not connected on a single channel but are connected on multiple channels -- the 
-definition of an MCT.  We refer to this set at set $M_u$ (unique multichannel 
-triangles).
-
-%For each element in set $M_u$, the MCT set, we examine if there exists a routing 
-%solution and seperate each solution into the number of hops in the shortest path route.  
-%The 2-hop routing solution is each element of $M_u$ where any two bi-directional links are 
-%on the same channel.  This assume that the sender wants to send the same data to each node 
-%in the triangle.  The multichannel solution is only possible by switching channels, however, 
-%routing over a 2-hop path using the links in the triangle also works.
-%Figure~\ref{fig:2hopdemo} shows a demonstration of the 2-hop solution to an MCT
-%where $i$ is the source and either $j$ or $k$ is the destination.
-
-%Similarly, we construct the sets for routing solutions that consist of 3 hops and N hops.  
-%The route must be on a single channel and include all three nodes, $i, j, $ and $k$ where 
-%one of the three nodes is considered the source, another is considered the destination, and 
-%the last node is on the path from the source  to the destination.  For each route calculation 
-%we use Dijkstra's shortest path algorithm using the link ETX's as the link weights.
-%The key is to minimize the ETX sum between the source and destionation.
-%Figure~\ref{fig:Nhopdemo} shows a demonstration of the N-hop solution to an MCT
-%where $i$ is the source and $j$ or $k$ is the destination.
-
+%interference, location of motes and orientation of mote antennas did not change.
+
+

code/Multichannel/docs/mobisys/doc/sexton.tex

@@ -1 +1 @@
 \section{Guiding Study}
 \label{sec:sexton_study}
+%The next study played an important role establishing the ground-truth for adding FH to the standards).
+An important study that played a role in the ISA standard, SP100.11a.  The authors
+examine the behavior of wireless links in industrial environments and recommend various forms
+of diversity -- FH being one of them.  We revisit the results of the study and argue that the conclusions
+would have been different had they considered routing as an alternative to FH.
 
 In~\cite{sexton}, Sexton et al. measure the multipath delay spread and link
@@ -6 +11 @@
 may suffer in these types of environments.  
 The CC2420 transmits at 250 kbps with a chip rate of 
-2000 kChips/sec~\cite{cc2420_datasheet}.  Therefore each chip takes
+2000 kChips/sec~\cite{cc2420}.  Therefore each chip takes
 500 nanoseconds to transmit.  If the delay spread is greater than 50 nanoseconds
 it could present a problem for the CC2420, since it has no equalization.  
@@ -55 +60 @@
 We may observe that the study focuses on direct connectivity between all pairs
 of nodes in the network.  In this context, the conclusions are, in fact, sound.
-However,  we do not expect that to be present in most wireless meshes.
+However,  we do not expect direct links between all nodes to be present in wireless meshes.
 Communication between widely separated pairs of nodes is accomplished by routing
 over multiple hops.  Sometimes multiple hops are required even for nodes in close
@@ -124 +129 @@
 
 It is important to note that link-level acknowledgements in 802.15.4 utilize the same
-channel as the packet they cover, so bidirectionality on a single channel is essential
-for reliability through retransmissions.  Therefore, the ability of multichannel communication
+channel as the packet they cover, so bi-directionality on a single channel is essential
+for reliability through re-transmission.  Therefore, the ability of multichannel communication
 to construct good bi-directional communication from two unidirectional links
 is not possible in practice. %; the second possibility is the only viable option.
@@ -170 +175 @@
 agility is required for all nodes to communicate with one another in the absence of routing.
 An example is shown in Figure~\ref{fig:sextrigdemo}, where $i$ can communicate bi-directionally 
-with $j$ and $k$ on $c_{1}$ and $i$ can communicate bi-directionally with $k$ and $j$ on $c_{2}$
+with $j$ on $c_{1}$, $i$ can communicate bi-directionally with $k$ on $c_{2}$, and 
+$j$ can communicate bi-directionally with $k$ on $c_{3}$
 but there is no channel where all three can communicate.