1 % v2-acmsmall-sample.tex, dated March 6 2012
\r
2 % This is a sample file for ACM small trim journals
\r
4 % Compilation using 'acmsmall.cls' - version 1.3 (March 2012), Aptara Inc.
\r
5 % (c) 2010 Association for Computing Machinery (ACM)
\r
7 % Questions/Suggestions/Feedback should be addressed to => "acmtexsupport@aptaracorp.com".
\r
8 % Users can also go through the FAQs available on the journal's submission webpage.
\r
10 % Steps to compile: latex, bibtex, latex latex
\r
12 % For tracking purposes => this is v1.3 - March 2012
\r
14 \documentclass[prodmode,acmtecs]{acmsmall} % Aptara syntax
\r
16 % Package to generate and customize Algorithm as per ACM style
\r
17 \usepackage[ruled]{algorithm2e}
\r
18 \renewcommand{\algorithmcfname}{ALGORITHM}
\r
20 \SetAlCapFnt{\small}
\r
21 \SetAlCapNameFnt{\small}
\r
23 \IncMargin{-\parindent}
\r
25 % Metadata Information
\r
36 \markboth{G. Zhou et al.}{A Multifrequency MAC Specially Designed for WSN Applications}
\r
39 \title{A Multifrequency MAC Specially Designed for Wireless Sensor Network Applications}
\r
41 \affil{College of William and Mary}
\r
43 \affil{University of Virginia}
\r
45 \affil{Eaton Innovation Center}
\r
47 \affil{University of Minnesota}
\r
51 \affil{University of Virginia}
\r
53 \affil{University of Illinois at Urbana-Champaign}}
\r
54 % NOTE! Affiliations placed here should be for the institution where the
\r
55 % BULK of the research was done. If the author has gone to a new
\r
56 % institution, before publication, the (above) affiliation should NOT be changed.
\r
57 % The authors 'current' address may be given in the "Author's addresses:" block (below).
\r
58 % So for example, Mr. Abdelzaher, the bulk of the research was done at UIUC, and he is
\r
59 % currently affiliated with NASA.
\r
62 Multifrequency media access control has been well understood in
\r
63 general wireless ad hoc networks, while in wireless sensor networks,
\r
64 researchers still focus on single frequency solutions. In wireless
\r
65 sensor networks, each device is typically equipped with a single
\r
66 radio transceiver and applications adopt much smaller packet sizes
\r
67 compared to those in general wireless ad hoc networks. Hence, the
\r
68 multifrequency MAC protocols proposed for general wireless ad hoc
\r
69 networks are not suitable for wireless sensor network applications,
\r
70 which we further demonstrate through our simulation experiments. In
\r
71 this article, we propose MMSN, which takes advantage of
\r
72 multifrequency availability while, at the same time, takes into
\r
73 consideration the restrictions of wireless sensor networks. Through
\r
74 extensive experiments, MMSN exhibits the prominent ability to utilize
\r
75 parallel transmissions among neighboring nodes. When multiple physical
\r
76 frequencies are available, it also achieves increased energy
\r
77 efficiency, demonstrating the ability to work against radio
\r
78 interference and the tolerance to a wide range of measured time
\r
79 synchronization errors.
\r
82 \category{C.2.2}{Computer-Communication Networks}{Network Protocols}
\r
84 \terms{Design, Algorithms, Performance}
\r
86 \keywords{Wireless sensor networks, media access control,
\r
87 multi-channel, radio interference, time synchronization}
\r
89 \acmformat{Gang Zhou, Yafeng Wu, Ting Yan, Tian He, Chengdu Huang, John A. Stankovic,
\r
90 and Tarek F. Abdelzaher, 2010. A multifrequency MAC specially
\r
91 designed for wireless sensor network applications.}
\r
92 % At a minimum you need to supply the author names, year and a title.
\r
94 % Full first names whenever they are known, surname last, followed by a period.
\r
95 % In the case of two authors, 'and' is placed between them.
\r
96 % In the case of three or more authors, the serial comma is used, that is, all author names
\r
97 % except the last one but including the penultimate author's name are followed by a comma,
\r
98 % and then 'and' is placed before the final author's name.
\r
99 % If only first and middle initials are known, then each initial
\r
100 % is followed by a period and they are separated by a space.
\r
101 % The remaining information (journal title, volume, article number, date, etc.) is 'auto-generated'.
\r
103 \begin{bottomstuff}
\r
104 This work is supported by the National Science Foundation, under
\r
105 grant CNS-0435060, grant CCR-0325197 and grant EN-CS-0329609.
\r
107 Author's addresses: G. Zhou, Computer Science Department,
\r
108 College of William and Mary; Y. Wu {and} J. A. Stankovic,
\r
109 Computer Science Department, University of Virginia; T. Yan,
\r
110 Eaton Innovation Center; T. He, Computer Science Department,
\r
111 University of Minnesota; C. Huang, Google; T. F. Abdelzaher,
\r
112 (Current address) NASA Ames Research Center, Moffett Field, California 94035.
\r
118 \section{Introduction}
\r
120 As a new technology, Wireless Sensor Networks (WSNs) has a wide
\r
121 range of applications [Culler 2001,Bahl 2002,Akyildiz 2001], including
\r
122 environment monitoring, smart buildings, medical care, industrial and
\r
123 military applications. Among them, a recent trend is to develop
\r
124 commercial sensor networks that require pervasive sensing of both
\r
125 environment and human beings, for example, assisted living
\r
126 [Akyildiz 2002,Harvard 2001,CROSSBOW] and smart homes
\r
127 [Harvard 2001,Adya 2001,CROSSBOW].
\r
130 ``For these applications, sensor devices are incorporated into human
\r
131 cloths [Natarajan 2001,Zhou 2006,Bahl 2002,Adya 2001] for monitoring
\r
132 health related information like EKG readings, fall detection, and voice recognition".
\r
134 While collecting all these multimedia information
\r
135 [Akyildiz 2002] requires a high network throughput, off-the-shelf
\r
136 sensor devices only provide very limited bandwidth in a single
\r
137 channel: 19.2Kbps in MICA2 [Bahl 2002] and 250Kbps in MICAz.
\r
139 In this article, we propose MMSN, abbreviation for Multifrequency
\r
140 Media access control for wireless Sensor Networks. The main
\r
141 contributions of this work can be summarized as follows.
\r
144 \item To the best of our knowledge, the MMSN protocol is the first
\r
145 multifrequency MAC protocol especially designed for WSNs, in which
\r
146 each device is equipped with a single radio transceiver and
\r
147 the MAC layer packet size is very small.
\r
148 \item Instead of using pairwise RTS/CTS frequency negotiation
\r
149 [Adya 2001,Culler 2001; Tzamaloukas 2001; Zhou 2006],
\r
150 we propose lightweight frequency assignments, which are good choices
\r
151 for many deployed comparatively static WSNs.
\r
152 \item We develop new toggle transmission and snooping techniques to
\r
153 enable a single radio transceiver in a sensor device to achieve
\r
154 scalable performance, avoiding the nonscalable ``one
\r
155 control channel + multiple data channels'' design [Natarajan 2001].
\r
159 \section{MMSN Protocol}
\r
162 \subsection{Frequency Assignment}
\r
164 We propose a suboptimal distribution to be used by each node, which is
\r
165 easy to compute and does not depend on the number of competing
\r
166 nodes. A natural candidate is an increasing geometric sequence, in
\r
168 % Numbered Equation
\r
171 P(t)=\frac{b^{\frac{t+1}{T+1}}-b^{\frac{t}{T+1}}}{b-1},
\r
173 where $t=0,{\ldots}\,,T$, and $b$ is a number greater than $1$.
\r
175 In our algorithm, we use the suboptimal approach for simplicity and
\r
176 generality. We need to make the distribution of the selected back-off
\r
177 time slice at each node conform to what is shown in Equation
\r
178 (\ref{eqn:01}). It is implemented as follows: First, a random
\r
179 variable $\alpha$ with a uniform distribution within the interval
\r
180 $(0, 1)$ is generated on each node, then time slice $i$ is selected
\r
181 according to the following equation:
\r
182 % Unnumbered Equation
\r
184 i=\lfloor(T+1)\log_b[\alpha(b-1)+1]\rfloor.
\r
186 It can be easily proven that the distribution of $i$ conforms to Equation
\r
189 So protocols [Bahl 2002,Culler 2001,Zhou 2006,Adya 2001,Culler 2001;
\r
190 Tzamaloukas-01; Akyildiz-01] that use RTS/CTS
\r
191 controls\footnote{RTS/CTS controls are required to be implemented by
\r
192 802.11-compliant devices. They can be used as an optional mechanism
\r
193 to avoid Hidden Terminal Problems in the 802.11 standard and
\r
194 protocols based on those similar to [Akyildiz 2001] and
\r
195 [Adya 2001].} for frequency negotiation and reservation are not
\r
196 suitable for WSN applications, even though they exhibit good
\r
197 performance in general wireless ad hoc
\r
201 \subsubsection{Exclusive Frequency Assignment}
\r
203 In exclusive frequency assignment, nodes first exchange their IDs
\r
204 among two communication hops so that each node knows its two-hop
\r
205 neighbors' IDs. In the second broadcast, each node beacons all
\r
206 neighbors' IDs it has collected during the first broadcast period.
\r
209 \paragraph{Eavesdropping}
\r
211 Even though the even selection scheme leads to even sharing of
\r
212 available frequencies among any two-hop neighborhood, it involves a
\r
213 number of two-hop broadcasts. To reduce the communication cost, we
\r
214 propose a lightweight eavesdropping scheme.
\r
216 \subsection{Basic Notations}
\r
218 As Algorithm~\ref{alg:one} states, for each frequency
\r
219 number, each node calculates a random number (${\textit{Rnd}}_{\alpha}$) for
\r
220 itself and a random number (${\textit{Rnd}}_{\beta}$) for each of its two-hop
\r
221 neighbors with the same pseudorandom number generator.
\r
223 \begin{algorithm}[t]
\r
225 \KwIn{Node $\alpha$'s ID ($ID_{\alpha}$), and node $\alpha$'s
\r
226 neighbors' IDs within two communication hops.}
\r
227 \KwOut{The frequency number ($FreNum_{\alpha}$) node $\alpha$ gets assigned.}
\r
228 $index$ = 0; $FreNum_{\alpha}$ = -1\;
\r
229 \Repeat{$FreNum_{\alpha} > -1$}{
\r
230 $Rnd_{\alpha}$ = Random($ID_{\alpha}$, $index$)\;
\r
232 \For{each node $\beta$ in $\alpha$'s two communication hops
\r
234 $Rnd_{\beta}$ = Random($ID_{\beta}$, $index$)\;
\r
235 \If{($Rnd_{\alpha} < Rnd_{\beta}$) \text{or} ($Rnd_{\alpha}$ ==
\r
236 $Rnd_{\beta}$ \text{and} $ID_{\alpha} < ID_{\beta}$)\;
\r
238 $Found$ = $FALSE$; break\;
\r
242 $FreNum_{\alpha}$ = $index$\;
\r
247 \caption{Frequency Number Computation}
\r
251 Bus masters are divided into two disjoint sets, $\mathcal{M}_{RT}$
\r
252 and $\mathcal{M}_{NRT}$.
\r
254 \begin{description}
\r
256 $\mathcal{M}_{RT}=\{ \vec{m}_{1},\dots,\vec{m}_{n}\}$ denotes the
\r
257 $n$ RT masters issuing real-time constrained requests. To model the
\r
258 current request issued by an $\vec{m}_{i}$ in $\mathcal{M}_{RT}$,
\r
259 three parameters---the recurrence time $(r_i)$, the service cycle
\r
260 $(c_i)$, and the relative deadline $(d_i)$---are used, with their
\r
263 $\mathcal{M}_{NRT}=\{ \vec{m}_{n+1},\dots,\vec{m}_{n+m}\}$ is a set
\r
264 of $m$ masters issuing nonreal-time constrained requests. In our
\r
265 model, each $\vec{m}_{j}$ in $\mathcal{M}_{NRT}$ needs only one
\r
266 parameter, the service cycle, to model the current request it
\r
270 Here, a question may arise, since each node has a global ID. Why
\r
271 don't we just map nodes' IDs within two hops into a group of
\r
272 frequency numbers and assign those numbers to all nodes within two
\r
275 \section{Simulator}
\r
278 If the model checker requests successors of a state which are not
\r
279 created yet, the state space uses the simulator to create the
\r
280 successors on-the-fly. To create successor states the simulator
\r
281 conducts the following steps.
\r
284 \item Load state into microcontroller model.
\r
285 \item Determine assignments needed for resolving nondeterminism.
\r
286 \item For each assignment.
\r
288 \item either call interrupt handler or simulate effect of next instruction, or
\r
289 \item evaluate truth values of atomic propositions.
\r
291 \item Return resulting states.
\r
293 Figure~\ref{fig:one} shows a typical microcontroller C program that
\r
294 controls an automotive power window lift. The program is one of the
\r
295 programs used in the case study described in Section~\ref{sec:sim}.
\r
296 At first sight, the programs looks like an ANSI~C program. It
\r
297 contains function calls, assignments, if clauses, and while loops.
\r
300 \centerline{\includegraphics{acmsmall-mouse}}
\r
301 \caption{Code before preprocessing.}
\r
305 \subsection{Problem Formulation}
\r
307 The objective of variable coalescence-based offset assignment is to find
\r
308 both the coalescence scheme and the MWPC on the coalesced graph. We start
\r
309 with a few definitions and lemmas for variable coalescence.
\r
312 \begin{definition}[Coalesced Node (C-Node)]A C-node is a set of
\r
313 live ranges (webs) in the AG or IG that are coalesced. Nodes within the same
\r
314 C-node cannot interfere with each other on the IG. Before any coalescing is
\r
315 done, each live range is a C-node by itself.
\r
318 \begin{definition}[C-AG (Coalesced Access Graph)]The C-AG is the access
\r
319 graph after node coalescence, which is composed of all C-nodes and C-edges.
\r
323 The C-MWPC problem is NP-complete.
\r
325 \begin{proof} C-MWPC can be easily reduced to the MWPC problem assuming a
\r
326 coalescence graph without any edge or a fully connected interference graph.
\r
327 Therefore, each C-node is an uncoalesced live range after value separation
\r
328 and C-PC is equivalent to PC. A fully connected interference graph is made
\r
329 possible when all live ranges interfere with each other. Thus, the C-MWPC
\r
330 problem is NP-complete.
\r
333 \begin{lemma}[Lemma Subhead]The solution to the C-MWPC problem is no
\r
334 worse than the solution to the MWPC.
\r
337 Simply, any solution to the MWPC is also a solution to the
\r
338 C-MWPC. But some solutions to C-MWPC may not apply to the MWPC (if any
\r
339 coalescing were made).
\r
342 \section{Performance Evaluation}
\r
344 During all the experiments, the Geographic Forwarding (GF)
\r
345 [Akyildiz 2001] routing protocol is used. GF exploits geographic
\r
346 information of nodes and conducts local data-forwarding to achieve
\r
347 end-to-end routing. Our simulation is
\r
348 configured according to the settings in
\r
349 Table~\ref{tab:one}. Each run lasts for 2 minutes and
\r
350 repeated 100 times. For each data value we present in the results,
\r
351 we also give its 90\% confidence interval.
\r
354 \tbl{Simulation Configuration\label{tab:one}}{%
\r
355 \begin{tabular}{|l|l|}
\r
357 TERRAIN{$^a$} & (200m$\times$200m) Square\\\hline
\r
358 Node Number & 289\\\hline
\r
359 Node Placement & Uniform\\\hline
\r
360 Application & Many-to-Many/Gossip CBR Streams\\\hline
\r
361 Payload Size & 32 bytes\\\hline
\r
362 Routing Layer & GF\\\hline
\r
363 MAC Layer & CSMA/MMSN\\\hline
\r
364 Radio Layer & RADIO-ACCNOISE\\\hline
\r
365 Radio Bandwidth & 250Kbps\\\hline
\r
366 Radio Range & 20m--45m\\\hline
\r
369 \Note{Source:}{This is a table
\r
370 sourcenote. This is a table sourcenote. This is a table
\r
373 \Note{Note:}{This is a table footnote.}
\r
374 \tabnoteentry{$^a$}{This is a table footnote. This is a
\r
375 table footnote. This is a table footnote.}
\r
379 \section{Conclusions}
\r
381 In this article, we develop the first multifrequency MAC protocol for
\r
382 WSN applications in which each device adopts a
\r
383 single radio transceiver. The different MAC design requirements for
\r
384 WSNs and general wireless ad-hoc networks are
\r
385 compared, and a complete WSN multifrequency MAC design (MMSN) is
\r
386 put forth. During the MMSN design, we analyze and evaluate different
\r
387 choices for frequency assignments and also discuss the nonuniform
\r
388 back-off algorithms for the slotted media access design.
\r
390 % Start of "Sample References" section
\r
392 \section{Typical references in new ACM Reference Format}
\r
393 A paginated journal article \cite{Abril07}, an enumerated
\r
394 journal article \cite{Cohen07}, a reference to an entire issue \cite{JCohen96},
\r
395 a monograph (whole book) \cite{Kosiur01}, a monograph/whole book in a series (see 2a in spec. document)
\r
396 \cite{Harel79}, a divisible-book such as an anthology or compilation \cite{Editor00}
\r
397 followed by the same example, however we only output the series if the volume number is given
\r
398 \cite{Editor00a} (so Editor00a's series should NOT be present since it has no vol. no.),
\r
399 a chapter in a divisible book \cite{Spector90}, a chapter in a divisible book
\r
400 in a series \cite{Douglass98}, a multi-volume work as book \cite{Knuth97},
\r
401 an article in a proceedings (of a conference, symposium, workshop for example)
\r
402 (paginated proceedings article) \cite{Andler79}, a proceedings article
\r
403 with all possible elements \cite{Smith10}, an example of an enumerated
\r
404 proceedings article \cite{VanGundy07},
\r
405 an informally published work \cite{Harel78}, a doctoral dissertation \cite{Clarkson85},
\r
406 a master's thesis: \cite{anisi03}, an online document / world wide web resource \cite{Thornburg01}, \cite{Ablamowicz07},
\r
407 \cite{Poker06}, a video game (Case 1) \cite{Obama08} and (Case 2) \cite{Novak03}
\r
408 and \cite{Lee05} and (Case 3) a patent \cite{JoeScientist001},
\r
409 work accepted for publication \cite{rous08}, 'YYYYb'-test for prolific author
\r
410 \cite{SaeediMEJ10} and \cite{SaeediJETC10}. Other cites might contain
\r
411 'duplicate' DOI and URLs (some SIAM articles) \cite{Kirschmer:2010:AEI:1958016.1958018}.
\r
412 Boris / Barbara Beeton: multi-volume works as books
\r
413 \cite{MR781536} and \cite{MR781537}.
\r
417 \section*{APPENDIX}
\r
418 \setcounter{section}{1}
\r
419 In this appendix, we measure
\r
420 the channel switching time of Micaz [CROSSBOW] sensor devices.
\r
421 In our experiments, one mote alternatingly switches between Channels
\r
422 11 and 12. Every time after the node switches to a channel, it sends
\r
423 out a packet immediately and then changes to a new channel as soon
\r
424 as the transmission is finished. We measure the
\r
425 number of packets the test mote can send in 10 seconds, denoted as
\r
426 $N_{1}$. In contrast, we also measure the same value of the test
\r
427 mote without switching channels, denoted as $N_{2}$. We calculate
\r
428 the channel-switching time $s$ as
\r
430 s=\frac{10}{N_{1}}-\frac{10}{N_{2}}. \nonumber
\r
432 By repeating the experiments 100 times, we get the average
\r
433 channel-switching time of Micaz motes: 24.3$\mu$s.
\r
435 \appendixhead{ZHOU}
\r
439 The authors would like to thank Dr. Maura Turolla of Telecom
\r
440 Italia for providing specifications about the application scenario.
\r
444 \bibliographystyle{ACM-Reference-Format-Journals}
\r
445 \bibliography{acmsmall-sample-bibfile}
\r
446 % Sample .bib file with references that match those in
\r
447 % the 'Specifications Document (V1.5)' as well containing
\r
448 % 'legacy' bibs and bibs with 'alternate codings'.
\r
449 % Gerry Murray - March 2012
\r
452 \received{February 2007}{March 2009}{June 2009}
\r
454 % Electronic Appendix
\r
459 \section{This is an example of Appendix section head}
\r
461 Channel-switching time is measured as the time length it takes for
\r
462 motes to successfully switch from one channel to another. This
\r
463 parameter impacts the maximum network throughput, because motes
\r
464 cannot receive or send any packet during this period of time, and it
\r
465 also affects the efficiency of toggle snooping in MMSN, where motes
\r
466 need to sense through channels rapidly.
\r
468 By repeating experiments 100 times, we get the average
\r
469 channel-switching time of Micaz motes: 24.3 $\mu$s. We then conduct
\r
470 the same experiments with different Micaz motes, as well as
\r
471 experiments with the transmitter switching from Channel 11 to other
\r
472 channels. In both scenarios, the channel-switching time does not have
\r
473 obvious changes. (In our experiments, all values are in the range of
\r
474 23.6 $\mu$s to 24.9 $\mu$s.)
\r
476 \section{Appendix section head}
\r
478 The primary consumer of energy in WSNs is idle listening. The key to
\r
479 reduce idle listening is executing low duty-cycle on nodes. Two
\r
480 primary approaches are considered in controlling duty-cycles in the
\r
484 % End of v2-acmsmall-sample.tex (March 2012) - Gerry Murray, ACM
\r
