The current State of “Super Computing”

v2-acmsmall-sample-word10.docx

Home >Computer Science homework help >The current State of “Super Computing”

39:8 G. Zhou et al.

A Multifrequency MAC Specially Designed for Wireless Sensor Network Applications 39:9

A Multifrequency MAC Specially Designed for Wireless Sensor Network Applications[footnoteRef:1] [1: This work is supported by the National Science Foundation, under grant CNS-0435060, grant CCR-0325197 and grant EN-CS-0329609. Author’s addresses: G. Zhou, Computer Science Department, College of William and Mary; Y. Wu and J.A. Stankovic, Computer Science Department, University of Virginia; T. Yan, Eaton Innovation Center; T. He, Computer Science Department, University of Minnesota; C. Huang, Google; T.F. Abdelzaher, (Current address) NASA Ames Research Center, Moffett Field, California 94035. Permission to make digital or hardcopies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credits permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or [email protected]. © 2010 ACM 1539-9087/2010/03-ART39 $15.00 DOI:http://dx.doi.org/10.1145/0000000.0000000]

GANG ZHOU, College of William and Mary

YAFENG WU, University of Virginia

TING YAN, Eaton Innovation Center

TIAN HE, University of Minnesota

CHENGDU HUANG, Google

JOHN A. STANKOVIC, University of Virginia

TAREK F. ABDELZAHER, University of Illinois at Urbana-Champaign

Multifrequency media access control has been well understood in general wireless ad hoc networks, while in wireless sensor networks, researchers still focus on single frequency solutions. In wireless sensor networks, each device is typically equipped with a single radio transceiver and applications adopt much smaller packet sizes compared to those in general wireless ad hoc networks. Hence, the multifrequency MAC protocols proposed for general wireless ad hoc networks are not suitable for wireless sensor network applications, which we further demonstrate through our simulation experiments. In this article, we propose MMSN, which takes advantage of multifrequency availability while, at the same time, takes into consideration the restrictions of wireless sensor networks. Through extensive experiments, MMSN exhibits the prominent ability to utilize parallel transmissions among neighboring nodes. When multiple physical frequencies are available, it also achieves increased energy efficiency, demonstrating the ability to work against radio interference and the tolerance to a wide range of measured time synchronization errors.

Categories and Subject Descriptors: C.2.2 [Computer-Communication Networks]: Network Protocols

General Terms: Design, Algorithms, Performance

Additional Key Words and Phrases: Wireless sensor networks, media access control, multi-channel, radio interference, time synchronization

ACM Reference Format:

Gang Zhou, Yafeng Wu, Ting Yan, Tian He, Chengdu Huang, John A. Stankovic, and Tarek F. Abdelzaher, 2010. A multi-frequency MAC specially designed for wireless sensor network applications. ACM Trans. Embedd. Comput. Syst. 9, 4, Article 39 (March 2010), 6 pages.   DOI:http://dx.doi.org/10.1145/0000000.0000000

INTRODUCTION

As a new technology, Wireless Sensor Networks (WSNs) has a wide range of applications [Culler et al. 2004; Bahl et al. 2004; Akyildiz et al. 2002], including environment monitoring, smart buildings,medical care, industrial andmilitary applications. Among them, a recent trend is to develop commercial sensor networks that require pervasive sensing of both environment and human beings, for example, assisted living [Akyildiz et al. 2007; Harvard CodeBlue 2008; 2008] and smart homes [Harvard CodeBlue 2008; Adya et al. 2004; CROSSBOW 2008].

“For these applications, sensor devices are incorporated into human cloths [Natarajan et al. 2007; Zhou et al. 2008; Bahl et al. 2004; Adya et al. 2004] for monitoring health related information like EKG readings, fall detection, and voice recognition”.

While collecting all these multimedia information [Akyildiz et al. 2007] requires a high network throughput, off-the-shelf sensor devices only provide very limited bandwidth in a single channel: 19.2Kbps in MICA2 [Bahl et al. 2004] and 250Kbps in MICAz. In this article, we propose MMSN, abbreviation for Multifrequency Media access control for wireless Sensor Networks. The main contributions of this work can be summarized as follows.

— To the best of our knowledge, the MMSN protocol is the first multifrequency MAC protocol especially designed for WSNs, in which each device is equipped with a single radio transceiver and the MAC layer packet size is very small.

— Instead of using pairwise RTS/CTS[footnoteRef:2] frequency negotiation [Adya et al. 2004; Culler et al. 2004; Tzamaloukas and Garcia-Luna-Aceves 2000; Zhou et al. 2008], we propose lightweight frequency assignments, which are good choices for many deployed comparatively static WSNs. [2: RTS/CTS controls are required to be implemented by 802.11-compliant devices. They can be used as an optional mechanism to avoid Hidden Terminal Problems in the 802.11 standard and protocols based on those similar to Akyildiz et al. [2002] and Adya et al. [2004].]

— We develop new toggle transmission and snooping techniques to enable a single radio transceiver in a sensor device to achieve scalable performance, avoiding the nonscalable “one control channel + multiple data channels” design [Natarajan et al. 2007].

MMSN PROTOCOL

Frequency Assignment

We propose a suboptimal distribution to be used by each node, which is easy to compute and does not depend on the number of competing nodes. A natural candidate is an increasing geometric sequence, in which

(1)

where t = 0, . . . , T, and b is a number greater than 1.

In our algorithm, we use the suboptimal approach for simplicity and generality. We need to make the distribution of the selected back-off time slice at each node conform to what is shown in Equation (1). It is implemented as follows: First, a random variable with a uniform distribution within the interval (0, 1) is generated on each node, then time slice i is selected according to the following equation:

It can be easily proven that the distribution of i conforms to Equation (1).

So protocols [Bahl et al. 2004; Culler et al. 2004; Zhou et al. 2008; Adya et al. 2004; Culler et al. 2004; Tzamaloukas and Garcia-Luna-Aceves 2000; Akyildiz et al. 2002] that use RTS/CTS controls1 for frequency negotiation and reservation are not suitable for WSN applications, even though they exhibit good performance in general wireless ad hoc networks.

Algorithm 1. Frequency Number Computation

Input: Node α’s ID (IDα), and node α’s neighbors’ IDs within two communication hops.

Output: The frequency number (FreNumα) node α • gets assigned.

index = 0; FreNumα =−1;

repeat

Rndα = Random(IDα, index);

Found = TRUE;

for each node β• in α’s two communication hops do

Rndβ = Random (IDβ, index);

if (Rndα < Rndβ) or (Rndα = = Rndβ and IDα < IDβ)

then

Found = FALSE; break;

end

if Found then

FreNumα = index;

else

index ++;

end

until FreNumα > −1;

2.1.1. Exclusive Frequency Assignment. In exclusive frequency assignment, nodes first exchange their IDs among two communication hops so that each node knows its twohop neighbors’ IDs. In the second broadcast, each node beacons all neighbors’ IDs it has collected during the first broadcast period.

Eavesdropping. Even though the even selection scheme leads to even sharing of available frequencies among any two-hop neighborhood, it involves a number of twohop broadcasts. To reduce the communication cost, we propose a lightweight eavesdropping scheme.

Basic Notations

As Algorithm 1 states, for each frequency number, each node calculates a random number (Rnd) for itself and a random number (Rnd) for each of its two-hop neighbors with the same pseudorandom number generator.

Bus masters are divided into two disjoint sets,MRT andMNRT .

RT Masters. denotes the n RT masters issuing real-time constrained requests. To model the current request issued by an mi in M, three parameters—the recurrence time (ri), the service cycle (ci), and the relative deadline (di)—are used, with their relationships.

NRT Masters. is a set of m masters issuing nonrealtime constrained requests. In our model, each in needs only one parameter, the service cycle, to model the current request it issues.

Here, a question may arise, since each node has a global ID. Why don’t we just map nodes’ IDs within two hops into a group of frequency numbers and assign those numbers to all nodes within two hops?

SIMULATOR

If the model checker requests successors of a state which are not created yet, the state space uses the simulator to create the successors on-the-fly. To create successor states the simulator conducts the following steps.

(1) Load state into microcontroller model.

(2) Determine assignments needed for resolving nondeterminism.

(3) For each assignment.

(a) Either call interrupt handler or simulate effect of next instruction, or

(b) Evaluate truth values of atomic propositions.

(4) Return resulting states.

Fig. 1.

Fig. 1. Code before preprocessing.

Figure 1 shows a typical microcontroller C program that controls an automotive power window lift. The program is one of the programs used in the case study described in Section 3. At first sight, the programs looks like an ANSI C program. It contains function calls, assignments, if clauses, and while loops.

Problem Formulation

The objective of variable coalescence-based offset assignment is to find both the coalescence scheme and the MWPC on the coalesced graph. We start with a few definitions and lemmas for variable coalescence.

Definition 3.1 (Coalesced Node (C-Node)). A C-node is a set of live ranges (webs) in the AG or IG that are coalesced. Nodes within the same C-node cannot interfere with each other on the IG. Before any coalescing is done, each live range is a C-node by itself.

Definition 3.2 (C-AG (Coalesced Access Graph)). The C-AG is the access graph after node coalescence, which is composed of all C-nodes and C-edges.

Lemma 3.3. The C-MWPC problem is NP-complete.

Proof. C-MWPC can be easily reduced to the MWPC problem assuming a coalescence graph without any edge or a fully connected interference graph. Therefore, each C-node is an uncoalesced live range after value separation and C-PC is equivalent to PC. A fully connected interference graph is made possible when all live ranges interfere with each other. Thus, the C-MWPC problem is NP-complete.

Lemma 3.4 (Lemma Subhead). The solution to the C-MWPC problem is no worse than the solution to the MWPC.

Proof. Simply, any solution to the MWPC is also a solution to the C-MWPC. But some solutions to C-MWPC may not apply to the MWPC (if any coalescing were made).

Table I. Simulation Configuration

TERRAINa	(200m×200m) Square
Node Number	289
Node Placement	Uniform
Application	Many-to-Many/Gossip CBR Streams
Payload Size	32 bytes
Routing Layer	GF
MAC Layer	CSMA/MMSN
Radio Layer	RADIO-ACCNOISE
Radio Bandwidth	250Kbps
Radio Range	20m–45m
Source: This is a table source note. This is a table source note. This is a table source note. Note: This is a table footnote. aThis is a table footnote. This is a table footnote. This is a table footnote.

PERFORMANCE EVALUATION

During all the experiments, the Geographic Forwarding (GF) [Akyildiz et al. 2002] routing protocol is used. GF exploits geographic information of nodes and conducts local data-forwarding to achieve end-to-end routing. Our simulation is configured according to the settings in Table I. Each run lasts for 2 minutes and repeated 100 times. For each data value we present in the results, we also give its 90% confidence interval.

CONCLUSIONS

In this article, we develop the first multifrequency MAC protocol for WSN applications in which each device adopts a single radio transceiver. The different MAC design requirements for WSNs and general wireless ad-hoc networks are compared, and a complete WSN multifrequency MAC design (MMSN) is put forth. During the MMSN design, we analyze and evaluate different choices for frequency assignments and also discuss the nonuniform back-off algorithms for the slotted media access design.

TYPICAL REFERENCES IN NEW ACM REFERENCE FORMAT

A paginated journal article [Abril and Plant 2007], an enumerated journal article [Cohen et al. 2007], a reference to an entire issue [Cohen 1996], a monograph (whole book) [Kosiur 2001], a monograph/whole book in a series (see 2a in spec. document) [Harel 1979], a divisible-book such as an anthology or compilation [Editor 2007] followed by the same example, however we only output the series if the volume number is given [Editor 2008] (so Editor00a’s series should NOT be present since it has no vol. no.), a chapter in a divisible book [Spector 1990], a chapter in a divisible book in a series [Douglass et al. 1998], a multi-volume work as book [Knuth 1997], an article in a proceedings (of a conference, symposium, workshop for example) (paginated proceedings article) [Andler 1979], a proceedings article with all possible elements [Smith 2010], an example of an enumerated proceedings article [Gundy et al. 2007], an informally published work [Harel 1978], a doctoral dissertation [Clarkson 1985], a master’s thesis: [Anisi 2003], an online document / world wide web resource [Thornburg 2001], [Ablamowicz and Fauser 2007], [Poker-Edge.Com 2006], a video game (Case 1) [Obama 2008] and (Case 2) [Novak 2003] and [Lee 2005] and (Case 3) a patent Scientist 2009], work accepted for publication [Rous 2008], ‘YYYYb’-test for prolific author [Saeedi et al. 2010a] and [Saeedi et al. 2010b]. Other cites might contain ‘duplicate’ DOI and URLs (some SIAM articles) [Kirschmer and Voight 2010]. Boris / Barbara Beeton: multi-volume works as books [Hörmander 1985b] and [Hörmander 1985a].

APPENDIX

In this appendix, we measure the channel switching time of Micaz [CROSSBOW 2008] sensor devices. In our experiments, one mote alternatingly switches between Channels 11 and 12. Every time after the node switches to a channel, it sends out a packet immediately and then changes to a new channel as soon as the transmission is finished. e measure the number of packets the test mote can send in 10 seconds, denoted as 1. In contrast, we also measure the same value of the test mote without switching channels, denoted as N2. We calculate the channel-switching time s as

By repeating the experiments 100 times, we get the average channel-switching time of icaz motes: 24.3 s.