Artifact Content
Not logged in

Artifact 0ee7b8f839a7462ee60ce29bc016f74f3f3df3b7:

Attachment "2002_xx_xx_DataCentric_Storage_in_SensorNets_by_Scott_Shenker_and_Sylvia_Ratnasamy_and_Brad_Karp_and_Ramesh_Govindan_and_Deborah_Estrin.ps" to wiki page [Attic 001 for Holding Various Files] added by martin_vahi on 2018-01-20 12:50:16.
%!PS-Adobe-2.0
%%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software
%%Title: hotnets-shenker.dvi
%%Pages: 6
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Helvetica-Bold Helvetica Times-Roman Times-Bold
%%+ Times-Italic Courier Symbol
%%EndComments
%DVIPSWebPage: (www.radicaleye.com)
%DVIPSCommandLine: dvips -f hotnets-shenker
%DVIPSParameters: dpi=600, compressed
%DVIPSSource:  TeX output 2002.09.30:2206
%%BeginProcSet: texc.pro
%!
/TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S
N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72
mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0
0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{
landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize
mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[
matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round
exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{
statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0]
N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin
/FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array
/BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2
array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N
df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A
definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get
}B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub}
B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr
1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3
1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx
0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx
sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{
rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp
gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B
/chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{
/cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{
A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy
get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse}
ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp
fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17
{2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add
chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{
1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop}
forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn
/BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put
}if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{
bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A
mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{
SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{
userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X
1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4
index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N
/p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{
/Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT)
(LaserWriter 16/600)]{A length product length le{A length product exch 0
exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse
end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask
grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot}
imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round
exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto
fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p
delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M}
B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{
p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S
rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end

%%EndProcSet
%%BeginProcSet: psfrag.pro
%%
%% This is file `psfrag.pro',
%% generated with the docstrip utility.
%%
%% The original source files were:
%%
%% psfrag.dtx  (with options: `filepro')
%% 
%% Copyright (c) 1996 Craig Barratt, Michael C. Grant, and David Carlisle.
%% All rights reserved.
%% 
%% This file is part of the PSfrag package.
%% 
userdict begin
/PSfragLib 90 dict def
/PSfragDict 6 dict def
/PSfrag { PSfragLib begin load exec end } bind def
end
PSfragLib begin
/RO /readonly      load def
/CP /currentpoint  load def
/CM /currentmatrix load def
/B { bind RO def } bind def
/X { exch def } B
/MD { { X } forall } B
/OE { end exec PSfragLib begin } B
/S false def
/tstr 8 string def
/islev2 { languagelevel } stopped { false } { 2 ge } ifelse def
[ /sM /tM /srcM /dstM /dM /idM /srcFM /dstFM ] { matrix def } forall
sM currentmatrix RO pop
dM defaultmatrix RO idM invertmatrix RO pop
srcFM identmatrix pop
/Hide { gsave { CP } stopped not newpath clip { moveto } if } B
/Unhide { { CP } stopped not grestore { moveto } if } B
/setrepl islev2 {{ /glob currentglobal def true setglobal array astore
                   globaldict exch /PSfrags exch put glob setglobal }}
                {{ array astore /PSfrags X }} ifelse B
/getrepl islev2 {{ globaldict /PSfrags get aload length }}
                {{ PSfrags aload length }} ifelse B
/convert {
   /src X src length string
   /c 0 def src length {
      dup c src c get dup 32 lt { pop 32 } if put /c c 1 add def
   } repeat
} B
/Begin {
    /saver save def
    srcFM exch 3 exch put
    0 ne /debugMode X 0 setrepl
    dup /S exch dict def { S 3 1 roll exch convert exch put } repeat
    srcM CM dup invertmatrix pop
    mark { currentdict { end } stopped { pop exit } if } loop
    PSfragDict counttomark { begin } repeat pop
} B
/End {
    mark { currentdict end dup PSfragDict eq { pop exit } if } loop
    counttomark { begin } repeat pop
    getrepl saver restore
    7 idiv dup /S exch dict def {
        6 array astore /mtrx X tstr cvs /K X
        S K [ S K known { S K get aload pop } if mtrx ] put
    } repeat
} B
/Place {
    tstr cvs /K X
    S K known {
        bind /proc X tM CM pop
        CP /cY X /cX X
        0 0 transform idtransform neg /aY X neg /aX X
        S K get dup length /maxiter X
        /iter 1 def {
            iter maxiter ne { /saver save def } if
            tM setmatrix aX aY translate
            [ exch aload pop idtransform ] concat
            cX neg cY neg translate cX cY moveto
            /proc load OE
            iter maxiter ne { saver restore /iter iter 1 add def } if
        } forall
        /noXY { CP /cY X /cX X } stopped def
        tM setmatrix noXY { newpath } { cX cY moveto } ifelse
    } {
        Hide OE Unhide
    } ifelse
} B
/normalize {
    2 index dup mul 2 index dup mul add sqrt div
    dup 4 -1 roll exch mul 3 1 roll mul
} B
/replace {
    aload pop MD
    CP /bY X /lX X gsave sM setmatrix
    str stringwidth abs exch abs add dup 0 eq
        { pop } { 360 exch div dup scale } ifelse
    lX neg bY neg translate newpath lX bY moveto
    str { /ch X ( ) dup 0 ch put false charpath ch Kproc } forall
    flattenpath pathbbox [ /uY /uX /lY /lX ] MD
    CP grestore moveto
    currentfont /FontMatrix get dstFM copy dup
    0 get 0 lt { uX lX /uX X /lX X } if
    3 get 0 lt { uY lY /uY X /lY X } if
    /cX uX lX add 0.5 mul def
    /cY uY lY add 0.5 mul def
    debugMode { gsave 0 setgray 1 setlinewidth
        lX lY moveto lX uY lineto uX uY lineto uX lY lineto closepath
        lX bY moveto uX bY lineto lX cY moveto uX cY lineto
        cX lY moveto cX uY lineto stroke
    grestore } if
    dstFM dup invertmatrix dstM CM srcM
    2 { dstM concatmatrix } repeat pop
    getrepl /temp X
        S str convert get {
            aload pop [ /rot /scl /loc /K ] MD
            /aX cX def /aY cY def
            loc {
                dup 66  eq { /aY bY def } { % B
                dup 98  eq { /aY lY def } { % b
                dup 108 eq { /aX lX def } { % l
                dup 114 eq { /aX uX def } { % r
                dup 116 eq { /aY uY def }   % t
                if } ifelse } ifelse } ifelse } ifelse pop
            } forall
            K srcFM rot tM rotate dstM
            2 { tM concatmatrix } repeat aload pop pop pop
            2 { scl normalize 4 2 roll } repeat
            aX aY transform
            /temp temp 7 add def
        } forall
    temp setrepl
} B
/Rif {
    S 3 index convert known { pop replace } { exch pop OE } ifelse
} B
/XA { bind [ /Kproc /str } B /XC { ] 2 array astore def } B
/xs   { pop } XA XC
/xks  { /kern load OE } XA /kern XC
/xas  { pop ax ay rmoveto } XA /ay /ax XC
/xws  { c eq { cx cy rmoveto } if } XA /c /cy /cx XC
/xaws { ax ay rmoveto c eq { cx cy rmoveto } if }
    XA /ay /ax /c /cy /cx XC
/raws { xaws { awidthshow } Rif } B
/rws  { xws { widthshow } Rif } B
/rks  { xks { kshow } Rif } B
/ras  { xas { ashow } Rif } B
/rs   { xs { show } Rif } B
/rrs { getrepl dup 2 add -1 roll //restore exec setrepl } B
PSfragDict begin
islev2 not { /restore { /rrs PSfrag } B } if
/show       { /rs   PSfrag } B
/kshow      { /rks  PSfrag } B
/ashow      { /ras  PSfrag } B
/widthshow  { /rws  PSfrag } B
/awidthshow { /raws PSfrag } B
end PSfragDict RO pop
end

%%EndProcSet
%%BeginProcSet: 8r.enc
% @@psencodingfile@{
%   author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry",
%   version = "0.6",
%   date = "1 July 1998",
%   filename = "8r.enc",
%   email = "tex-fonts@@tug.org",
%   docstring = "Encoding for TrueType or Type 1 fonts
%                to be used with TeX."
% @}
% 
% Idea is to have all the characters normally included in Type 1 fonts
% available for typesetting. This is effectively the characters in Adobe
% Standard Encoding + ISO Latin 1 + extra characters from Lucida.
% 
% Character code assignments were made as follows:
% 
% (1) the Windows ANSI characters are almost all in their Windows ANSI
% positions, because some Windows users cannot easily reencode the
% fonts, and it makes no difference on other systems. The only Windows
% ANSI characters not available are those that make no sense for
% typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen
% (173). quotesingle and grave are moved just because it's such an
% irritation not having them in TeX positions.
% 
% (2) Remaining characters are assigned arbitrarily to the lower part
% of the range, avoiding 0, 10 and 13 in case we meet dumb software.
% 
% (3) Y&Y Lucida Bright includes some extra text characters; in the
% hopes that other PostScript fonts, perhaps created for public
% consumption, will include them, they are included starting at 0x12.
% 
% (4) Remaining positions left undefined are for use in (hopefully)
% upward-compatible revisions, if someday more characters are generally
% available.
% 
% (5) hyphen appears twice for compatibility with both 
% ASCII and Windows.
% 
/TeXBase1Encoding [
% 0x00 (encoded characters from Adobe Standard not in Windows 3.1)
  /.notdef /dotaccent /fi /fl
  /fraction /hungarumlaut /Lslash /lslash
  /ogonek /ring /.notdef
  /breve /minus /.notdef 
% These are the only two remaining unencoded characters, so may as
% well include them.
  /Zcaron /zcaron 
% 0x10
 /caron /dotlessi 
% (unusual TeX characters available in, e.g., Lucida Bright)
 /dotlessj /ff /ffi /ffl 
 /.notdef /.notdef /.notdef /.notdef
 /.notdef /.notdef /.notdef /.notdef
 % very contentious; it's so painful not having quoteleft and quoteright
 % at 96 and 145 that we move the things normally found there to here.
 /grave /quotesingle 
% 0x20 (ASCII begins)
 /space /exclam /quotedbl /numbersign
 /dollar /percent /ampersand /quoteright
 /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
 /zero /one /two /three /four /five /six /seven
 /eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
 /P /Q /R /S /T /U /V /W
 /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
 /p /q /r /s /t /u /v /w
 /x /y /z /braceleft /bar /braceright /asciitilde
 /.notdef % rubout; ASCII ends
% 0x80
 /.notdef /.notdef /quotesinglbase /florin
 /quotedblbase /ellipsis /dagger /daggerdbl
 /circumflex /perthousand /Scaron /guilsinglleft
 /OE /.notdef /.notdef /.notdef
% 0x90
 /.notdef /.notdef /.notdef /quotedblleft
 /quotedblright /bullet /endash /emdash
 /tilde /trademark /scaron /guilsinglright
 /oe /.notdef /.notdef /Ydieresis
% 0xA0
 /.notdef % nobreakspace
 /exclamdown /cent /sterling
 /currency /yen /brokenbar /section
 /dieresis /copyright /ordfeminine /guillemotleft
 /logicalnot
 /hyphen % Y&Y (also at 45); Windows' softhyphen
 /registered
 /macron
% 0xD0
 /degree /plusminus /twosuperior /threesuperior
 /acute /mu /paragraph /periodcentered
 /cedilla /onesuperior /ordmasculine /guillemotright
 /onequarter /onehalf /threequarters /questiondown
% 0xC0
 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
 /Egrave /Eacute /Ecircumflex /Edieresis
 /Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
 /Eth /Ntilde /Ograve /Oacute
 /Ocircumflex /Otilde /Odieresis /multiply
 /Oslash /Ugrave /Uacute /Ucircumflex
 /Udieresis /Yacute /Thorn /germandbls
% 0xE0
 /agrave /aacute /acircumflex /atilde
 /adieresis /aring /ae /ccedilla
 /egrave /eacute /ecircumflex /edieresis
 /igrave /iacute /icircumflex /idieresis
% 0xF0
 /eth /ntilde /ograve /oacute
 /ocircumflex /otilde /odieresis /divide
 /oslash /ugrave /uacute /ucircumflex
 /udieresis /yacute /thorn /ydieresis
] def

%%EndProcSet
%%BeginProcSet: texps.pro
%!
TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2
index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{
dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1
roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def
dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def}
if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def}
def end

%%EndProcSet
%%BeginProcSet: special.pro
%!
TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N
/vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N
/rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N
/@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{
/hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho
X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B
/@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{
/urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known
{userdict/md get type/dicttype eq{userdict begin md length 10 add md
maxlength ge{/md md dup length 20 add dict copy def}if end md begin
/letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S
atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{
itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll
transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll
curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf
pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}
if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1
-1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3
get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip
yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub
neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{
noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop
90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get
neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr
1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr
2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4
-1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S
TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{
Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale
}if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState
save N userdict maxlength dict begin/magscale true def normalscale
currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts
/psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x
psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx
psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub
TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict
begin/SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{
CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N
/@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}
repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N
/@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX
currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY
moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X
/yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0
1 startangle endangle arc savematrix setmatrix}N end

%%EndProcSet
%%BeginProcSet: color.pro
%!
TeXDict begin/setcmykcolor where{pop}{/setcmykcolor{dup 10 eq{pop
setrgbcolor}{1 sub 4 1 roll 3{3 index add neg dup 0 lt{pop 0}if 3 1 roll
}repeat setrgbcolor pop}ifelse}B}ifelse/TeXcolorcmyk{setcmykcolor}def
/TeXcolorrgb{setrgbcolor}def/TeXcolorgrey{setgray}def/TeXcolorgray{
setgray}def/TeXcolorhsb{sethsbcolor}def/currentcmykcolor where{pop}{
/currentcmykcolor{currentrgbcolor 10}B}ifelse/DC{exch dup userdict exch
known{pop pop}{X}ifelse}B/GreenYellow{0.15 0 0.69 0 setcmykcolor}DC
/Yellow{0 0 1 0 setcmykcolor}DC/Goldenrod{0 0.10 0.84 0 setcmykcolor}DC
/Dandelion{0 0.29 0.84 0 setcmykcolor}DC/Apricot{0 0.32 0.52 0
setcmykcolor}DC/Peach{0 0.50 0.70 0 setcmykcolor}DC/Melon{0 0.46 0.50 0
setcmykcolor}DC/YellowOrange{0 0.42 1 0 setcmykcolor}DC/Orange{0 0.61
0.87 0 setcmykcolor}DC/BurntOrange{0 0.51 1 0 setcmykcolor}DC
/Bittersweet{0 0.75 1 0.24 setcmykcolor}DC/RedOrange{0 0.77 0.87 0
setcmykcolor}DC/Mahogany{0 0.85 0.87 0.35 setcmykcolor}DC/Maroon{0 0.87
0.68 0.32 setcmykcolor}DC/BrickRed{0 0.89 0.94 0.28 setcmykcolor}DC/Red{
0 1 1 0 setcmykcolor}DC/OrangeRed{0 1 0.50 0 setcmykcolor}DC/RubineRed{
0 1 0.13 0 setcmykcolor}DC/WildStrawberry{0 0.96 0.39 0 setcmykcolor}DC
/Salmon{0 0.53 0.38 0 setcmykcolor}DC/CarnationPink{0 0.63 0 0
setcmykcolor}DC/Magenta{0 1 0 0 setcmykcolor}DC/VioletRed{0 0.81 0 0
setcmykcolor}DC/Rhodamine{0 0.82 0 0 setcmykcolor}DC/Mulberry{0.34 0.90
0 0.02 setcmykcolor}DC/RedViolet{0.07 0.90 0 0.34 setcmykcolor}DC
/Fuchsia{0.47 0.91 0 0.08 setcmykcolor}DC/Lavender{0 0.48 0 0
setcmykcolor}DC/Thistle{0.12 0.59 0 0 setcmykcolor}DC/Orchid{0.32 0.64 0
0 setcmykcolor}DC/DarkOrchid{0.40 0.80 0.20 0 setcmykcolor}DC/Purple{
0.45 0.86 0 0 setcmykcolor}DC/Plum{0.50 1 0 0 setcmykcolor}DC/Violet{
0.79 0.88 0 0 setcmykcolor}DC/RoyalPurple{0.75 0.90 0 0 setcmykcolor}DC
/BlueViolet{0.86 0.91 0 0.04 setcmykcolor}DC/Periwinkle{0.57 0.55 0 0
setcmykcolor}DC/CadetBlue{0.62 0.57 0.23 0 setcmykcolor}DC
/CornflowerBlue{0.65 0.13 0 0 setcmykcolor}DC/MidnightBlue{0.98 0.13 0
0.43 setcmykcolor}DC/NavyBlue{0.94 0.54 0 0 setcmykcolor}DC/RoyalBlue{1
0.50 0 0 setcmykcolor}DC/Blue{1 1 0 0 setcmykcolor}DC/Cerulean{0.94 0.11
0 0 setcmykcolor}DC/Cyan{1 0 0 0 setcmykcolor}DC/ProcessBlue{0.96 0 0 0
setcmykcolor}DC/SkyBlue{0.62 0 0.12 0 setcmykcolor}DC/Turquoise{0.85 0
0.20 0 setcmykcolor}DC/TealBlue{0.86 0 0.34 0.02 setcmykcolor}DC
/Aquamarine{0.82 0 0.30 0 setcmykcolor}DC/BlueGreen{0.85 0 0.33 0
setcmykcolor}DC/Emerald{1 0 0.50 0 setcmykcolor}DC/JungleGreen{0.99 0
0.52 0 setcmykcolor}DC/SeaGreen{0.69 0 0.50 0 setcmykcolor}DC/Green{1 0
1 0 setcmykcolor}DC/ForestGreen{0.91 0 0.88 0.12 setcmykcolor}DC
/PineGreen{0.92 0 0.59 0.25 setcmykcolor}DC/LimeGreen{0.50 0 1 0
setcmykcolor}DC/YellowGreen{0.44 0 0.74 0 setcmykcolor}DC/SpringGreen{
0.26 0 0.76 0 setcmykcolor}DC/OliveGreen{0.64 0 0.95 0.40 setcmykcolor}
DC/RawSienna{0 0.72 1 0.45 setcmykcolor}DC/Sepia{0 0.83 1 0.70
setcmykcolor}DC/Brown{0 0.81 1 0.60 setcmykcolor}DC/Tan{0.14 0.42 0.56 0
setcmykcolor}DC/Gray{0 0 0 0.50 setcmykcolor}DC/Black{0 0 0 1
setcmykcolor}DC/White{0 0 0 0 setcmykcolor}DC end

%%EndProcSet
TeXDict begin 40258431 52099146 1000 600 600 (hotnets-shenker.dvi)
@start /Fa 139[12 2[21 1[21 2[12 10[21 97[{
TeXBase1Encoding ReEncodeFont}5 41.511 /Times-Italic
rf /Fc 139[16 2[29 1[29 2[16 10[29 15[42 12[42 68[{
TeXBase1Encoding ReEncodeFont}7 58.1154 /Times-Italic
rf
%DVIPSBitmapFont: Fd cmr10 7 1
/Fd 1 44 df<1438B2B712FCA3C70038C7FCB226277DA12D>43 D
E
%EndDVIPSBitmapFont
/Fe 135[37 2[42 25 29 33 1[42 37 42 1[21 2[21 1[37 1[33
1[33 1[37 12[50 42 2[46 3[50 3[58 58 1[50 54 54 8[25
12[25 3[25 25 40[{TeXBase1Encoding ReEncodeFont}27 74.7198
/Times-Bold rf
%DVIPSBitmapFont: Ff cmr10 9 5
/Ff 5 94 df<EB0180EB030013065B131C5B5B13F05B12015B1203485AA290C7FC5AA212
1EA3123EA2123CA2127CA4127812F8B11278127CA4123CA2123EA2121EA37EA27E7FA26C
7E12017F12007F13707F7F130C7F7FEB0180114B79B71D>40 D<12C012607E7E121C7E7E
7F12037F12017F6C7EA213701378A27FA3133EA2131EA2131FA47F1480B114005BA4131E
A2133EA2133CA35BA2137013F0A2485A5B12035B120790C7FC120E5A12185A5A5A114B7C
B71D>I<EC01C0B3A6B91280A3C7D801C0C8FCB3A631337CAB3A>43
D<EAFFE0A3EAE000B3B3B3AFEAFFE0A30B4B78B715>91 D<EAFFE0A31200B3B3B3AF12FF
A30B4B7FB715>93 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fg cmmi10 9 2
/Fg 2 63 df<123C127EB4FCA21380A2127F123D1201A412031300A25A1206120E120C5A
12385A122009177A8715>59 D<12C012F8127EEA1F80EA07E0EA01F8EA007EEB1F80EB07
E0EB01F8EB007EEC1F80EC07E0EC01F8EC007EED1F80ED07E0ED01F8ED007EEE1F80EE07
E0EE01F8EE0078EE01F8EE07E0EE1F80EE7E00ED01F8ED07E0ED1F80037EC7FCEC01F8EC
07E0EC1F80027EC8FCEB01F8EB07E0EB1F80017EC9FCEA01F8EA07E0EA1F80007ECAFC12
F812E02D2D7AA83A>62 D E
%EndDVIPSBitmapFont
/Fh 82[30 51[41 41 1[41 46 25 36 36 46 46 46 46 66 25
41 1[25 46 46 25 41 46 41 46 46 9[76 1[66 51 46 1[66
56 3[51 4[66 1[56 66 61 1[56 6[30 2[46 46 46 46 46 9[30
30 40[{TeXBase1Encoding ReEncodeFont}44 91.3242 /Times-Italic
rf
%DVIPSBitmapFont: Fj cmsy10 9 3
/Fj 3 113 df<EB1F80EBFFF0000313FC487F487F4814804814C0A24814E0A3B612F0A6
6C14E0A36C14C0A26C14806C14006C5B6C5BC613F0EB1F801C1C7CA025>15
D<00E0EB01C000F814F0007EEB00FC001F143ED807C0EB0F80D803F0EB07E0D800FCEB01
F8013EEB007CD90F80131FD907E0EB0FC0D901F0EB03E0D9007CEB00F8023F147EDA0F80
131FDA03E0EB07C0DA01F8EB03F0DA007EEB00FC031F143EDB07C0EB0F80DB03F0EB07E0
DB00F8EB01F0043EEB007C706C133FDC07E0EB0FC0040114030407140FDC1F80EB3F0004
3EC7127C04F8EB01F0DB03F0EB07E0DB07C0EB0F80031FC7003EC7FC037E14FCDA01F8EB
03F0DA03E0EB07C0DA0F80011FC8FC023FC7127E027C14F8D901F0EB03E0D907E0EB0FC0
D90F8049C9FC013EC7127C01FC495AD803F0EB07E0D807C0EB0F80001FC7003ECAFC007E
14FC00F8EB01F000E014C042317CAA4B>29 D<19C01801A2F00380A2F00700A2180EA260
A260A260A260A24D5AA24D5AA34DC7FCA2170EA25FA25FA25FA25FA24C5AA24C5A13E012
0100034BC8FCEA0FF0001F150EEA31F800615DEAC0FC00005D137E5EA26D5CA26D6C485A
A26D6C485AA26D6C48C9FCA2EB03F0150EA26D6C5AA26D6C5AA2EC7E70A26E5AA26E5AA2
5D140F92CAFC80A23A4B7B823E>112 D E
%EndDVIPSBitmapFont
/Fk 136[45 1[45 45 45 45 1[45 45 45 45 45 45 1[45 45
2[45 45 45 45 45 32[45 5[45 10[45 45 46[{TeXBase1Encoding ReEncodeFont}
22 74.7198 /Courier rf /Fl 133[29 33 33 50 33 37 21 29
29 1[37 37 37 54 21 33 1[21 37 37 21 33 37 33 37 37 9[62
2[42 37 46 54 46 54 50 62 2[33 25 1[54 46 46 54 50 1[46
8[37 5[37 37 37 21 19 25 19 2[25 25 36[37 3[{
TeXBase1Encoding ReEncodeFont}52 74.7198 /Times-Italic
rf /Fm 104[75 37 1[33 33 24[33 37 37 54 37 37 21 29 25
37 37 37 37 58 21 37 21 21 37 37 25 33 37 33 37 33 3[25
1[25 46 54 1[71 54 54 46 42 50 54 42 54 54 66 46 54 29
25 54 54 42 46 54 50 50 54 5[21 21 37 37 37 37 37 37
37 37 37 37 21 19 25 19 2[25 25 25 35[42 42 2[{
TeXBase1Encoding ReEncodeFont}78 74.7198 /Times-Roman
rf /Fn 82[33 52[50 1[50 55 33 39 44 1[55 50 55 83 28
55 1[28 55 2[44 55 44 55 50 7[72 1[100 1[72 66 55 72
78 61 78 72 94 66 78 1[39 78 78 61 66 72 72 66 72 9[50
50 50 50 50 50 50 2[25 1[25 44[{TeXBase1Encoding ReEncodeFont}51
99.6264 /Times-Bold rf /Fo 121[29 81[29 29 29 29 49[{
TeXBase1Encoding ReEncodeFont}5 58.1154 /Times-Roman
rf
%DVIPSBitmapFont: Fq cmsy10 7 1
/Fq 1 4 df<136013701360A400E0137000F013F0387C63E0381E6780380FFF00EA03FC
EA00F0EA03FCEA0FFF381E6780387C63E038F060F000E0137000001300A4137013601419
7C9A1D>3 D E
%EndDVIPSBitmapFont
/Fr 134[42 6[28 1[46 46 1[69 18 42 1[18 3[46 1[42 13[60
1[55 6[46 2[23 5[60 55 55 7[46 46 46 1[46 46 3[46 23
23 1[23 44[{TeXBase1Encoding ReEncodeFont}26 83.022 /Helvetica
rf /Fs 134[50 2[50 55 28 50 33 1[55 55 55 83 22 50 1[22
55 2[55 55 50 55 55 13[66 72 6[66 3[78 1[66 72 1[66 1[101
17[28 46[{TeXBase1Encoding ReEncodeFont}28 99.6264 /Helvetica
rf /Ft 82[50 56[50 83 58 2[91 91 4[42 1[91 1[83 1[83
1[83 13[100 14[108 108 67[{TeXBase1Encoding ReEncodeFont}14
149.44 /Helvetica-Bold rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin

%%EndSetup
%%Page: 1 1
1 0 bop Black Black Black Black Black 682 107 a Ft(Data\255Centric)41
b(Stora)o(g)q(e)h(in)g(Sensornets)410 445 y Fs(Scott)28
b(Shenk)n(er)254 562 y Fr(ICSI,)c(Ber)q(k)n(ele)n(y)-8
b(,)23 b(CA)h(94704)54 694 y Fs(shenk)n(er@icsi.ber)q(k)n(ele)n(y)-10
b(.edu)1543 445 y(Sylvia)28 b(Ratnasam)o(y)2338 418 y
Fq(\003)1376 562 y Fr(ICSI/UCB)n(,)23 b(Ber)q(k)n(ele)n(y)-8
b(,)23 b(CA)f(94704)1407 694 y Fs(sylviar@cs)o(.ber)q(k)n(ele)n(y)-10
b(.edu)2978 445 y(Br)o(ad)29 b(Kar)s(p)3427 418 y Fo(\206)2733
562 y Fr(ICSI,)24 b(Ber)q(k)n(ele)n(y)-8 b(,)23 b(CA)h(94704)2672
694 y Fs(bkar)s(p@icsi.ber)q(k)n(ele)n(y)-10 b(.edu)p
Black Black 855 921 a(Ramesh)28 b(Go)o(vindan)684 1038
y Fr(USC)c(Comp)m(.)f(Sci.,)h(LA,)g(CA)f(90089)876 1170
y Fs(r)o(amesh@usc.edu)p Black Black 2250 919 a(Debor)o(ah)29
b(Estr)q(in)1982 1036 y Fr(UCLA)21 b(Comp)m(.)h(Sci.,)g(LA,)f(CA)g
(90095)2130 1168 y Fs(destr)q(in@cs)o(.ucla.edu)p Black
-152 1443 a Fn(1.)100 b(INTR)m(ODUCTION)-152 1534 y Fm(Recent)16
b(engineering)h(adv)n(ances)g(in)f(the)f(design)h(of)g(small)f(ener)o
(gy-ef)n(\002cient)-152 1621 y(hardw)o(are)h(and)f(compact)h(operating)
f(systems)g(ha)o(v)o(e)g(enabled)h(the)e(de)n(v)o(elop-)-152
1708 y(ment)k(of)f(lar)o(ge-scale)h(distrib)o(uted)f(sensing)h(netw)o
(orks)h(\(sensornets\))f(made)-152 1796 y(up)k(of)g(man)o(y)g(small)g
(sensing)g(de)n(vices)h(equipped)g(with)e(memory)-5 b(,)23
b(proces-)-152 1883 y(sors,)30 b(and)e(short-range)g(wireless)f
(communication.)51 b(These)28 b(sensornets)-152 1970
y(will)f(pro)o(vide)i(an)f(unprecedented)i(amount)f(of)e(detailed)h
(measurements)-152 2057 y(o)o(v)o(er)g(wide)f(geographic)i(areas.)49
b(Ho)n(we)n(v)o(er)m(,)30 b(these)e(data)f(are)h(distrib)o(uted)-152
2144 y(across)f(the)f(entire)g(sensornet,)i(and)f(so)f(are)g(hard)h(to)
f(use.)45 b(Communica-)-152 2231 y(tion)20 b(between)h(sensornet)f
(nodes)h(requires)f(the)g(e)o(xpenditure)h(of)f(ener)o(gy)-5
b(,)21 b(a)-152 2319 y(scarce)i(commodity)g(in)e(most)h(sensornets.)33
b(Thus,)22 b(making)h(ef)n(fecti)n(v)o(e)f(use)-152 2406
y(of)17 b(sensornet)h(data)f(will)e(require)i(scalable,)g(self-or)o
(ganizing,)h(and)f(ener)o(gy-)-152 2493 y(ef)n(\002cient)i(data)g
(dissemination)h(algorithms.)-152 2667 y(Since)27 b(the)g(content)h(of)
f(the)g(data)h(is)e(more)i(important)f(than)g(the)h(identity)-152
2754 y(of)23 b(the)g(node)h(that)e(gathers)h(them,)g(sensornet)h
(researchers)g(ha)o(v)o(e)f(found)g(it)-152 2842 y(useful)17
b(to)e(mo)o(v)o(e)i(a)o(w)o(ay)f(from)g(the)g(Internet')l(s)g
(point-to-point)g(communica-)-152 2929 y(tion)23 b(abstraction)g(and)g
(instead)g(adopt)g(abstractions)g(that)f(are)h(more)f(data-)-152
3016 y(centric.)h(This)16 b(approach)i(entails)e Fl(naming)h
Fm(the)g(data)f(and)i(using)f(communi-)-152 3103 y(cation)f
(abstractions)h(that)e(refer)h(to)g(those)g(names)g(rather)g(than)g(to)
g(node)h(net-)-152 3190 y(w)o(ork)k(addresses)h([1,)f(9].)28
b(In)20 b(particular)m(,)h(pre)n(vious)h(w)o(ork)f(on)g(data-centric)
-152 3278 y(routing)27 b(has)g(sho)n(wn)g(it)e(to)h(be)h(an)f(ener)o
(gy-ef)n(\002cient)h(data)g(dissemination)-152 3365 y(method)c(for)f
(sensornets)g([10].)32 b(Herein,)22 b(we)g(propose)h(a)e(useful)h
(compan-)-152 3452 y(ion)g(method,)h(data-centric)f(storage)g(\(DCS\).)
e(In)i(DCS,)e(rele)n(v)n(ant)j(data)f(are)-152 3539 y(stored)16
b(by)g(name)g(at)f(nodes)h(within)g(the)f(sensornet;)i(all)e(data)h
(with)f(the)g(same)-152 3626 y(general)26 b(name)f(\()p
Fl(e)o(.g)o(.,)g Fm(elephant)g(sightings\))h(will)d(be)i(stored)g(at)g
(the)f(same)-152 3713 y(sensornet)c(node)f(\(not)f(necessarily)h(the)g
(one)g(that)f(originally)h(gathered)g(the)-152 3801 y(data\).)30
b(Queries)22 b(for)f(data)g(with)g(a)g(particular)g(name)h(can)f(then)h
(be)g(sent)f(di-)-152 3888 y(rectly)k(to)h(the)f(node)h(storing)g
(those)f(named)h(data,)h(without)e(the)h(\003ooding)-152
3975 y(required)20 b(in)f(some)g(data-centric)h(routing)f(proposals.)
-152 4149 y(Se)n(v)o(eral)25 b(data-centric)h(dissemination)g(methods)g
(are)f(concei)n(v)n(able,)j(each)p Black -152 4213 797
4 v -148 4262 a Fq(\003)-114 4289 y Fm(Sylvia)23 b(Ratnasamy')l(s)h
(current)g(af)n(\002liation:)32 b(Intel)23 b(Research,)i(Berk)o(ele)o
(y)-5 b(,)-152 4364 y(CA)19 b(94704.)-148 4426 y Fo(\206)-114
4453 y Fm(Brad)g(Karp')l(s)g(current)h(af)n(\002liation:)j(Intel)c
(Research)h(and)g(Carne)o(gie)g(Mel-)-152 4528 y(lon)f(Uni)n(v)o
(ersity)-5 b(,)19 b(Pittsb)o(ur)o(gh,)f(P)-7 b(A)19 b(15213,)h
Fk(bkarp@cs.cmu.edu)p Fm(.)p Black Black Black Black
Black 2040 1443 a(with)j(rather)g(dif)n(ferent)g(performance)i
(characteristics.)35 b(The)23 b(appropriate)2040 1530
y(data)e(dissemination)g(method)h(for)e(a)h(particular)g(task)f(will)g
(depend)i(on)f(the)2040 1617 y(nature)h(of)f(the)h(sensornet,)g(its)f
(intended)h(deplo)o(yment)i(en)m(vironment,)f(and)2040
1704 y(the)i(e)o(xpected)h(w)o(orkload.)41 b(W)-6 b(e)25
b(mak)o(e)g(three)g(principal)g(contrib)o(utions)g(in)2040
1791 y(this)19 b(paper:)p Black 2152 2069 a Fj(\017)p
Black 38 w Fm(W)-6 b(e)27 b(propose)i(a)e(no)o(v)o(el)h(data)g
(dissemination)g(method,)i(DCS,)d(and)2227 2156 y(sho)n(w)19
b(where)h(it)e(outperforms)i(other)f(approaches.)p Black
2152 2340 a Fj(\017)p Black 38 w Fm(W)-6 b(e)22 b(pro)o(vide)i(an)f(or)
o(ganizing)g(frame)n(w)o(ork)h(for)e(comparing)i(among)2227
2427 y(three)j(canonical)g(data)g(dissemination)h(approaches,)i(and)d
(predict)2227 2514 y(where)19 b(each)h(performs)f(best.)p
Black 2152 2697 a Fj(\017)p Black 38 w Fm(W)-6 b(e)19
b(gi)n(v)o(e)g(an)h(o)o(v)o(ervie)n(w)f(of)h(GHT)-6 b(,)18
b(a)h(Geographic)i(Hash)e(T)-6 b(able)19 b(sys-)2227
2784 y(tem)g(that)f(implements)i(DCS.)2040 3062 y(Our)j(claim)g(is)g
(not)g(that)g(data-centric)g(storage)h(is)e(al)o(w)o(ays)i(the)f
(method)h(of)2040 3149 y(choice,)29 b(b)o(ut)e(rather)g(that)f(under)i
(some)f(conditions)h(it)e(will)g(be)h(the)g(most)2040
3236 y(desired)e(option.)41 b(In)24 b(f)o(act,)i(we)e(e)o(xpect)h(that)
g(future)f(sensornets)i(will)d(em-)2040 3324 y(body)j(all)e(of)g(these)
h(\(or)f(similar\))g(data-centric)g(dissemination)i(methods,)2040
3411 y(and)18 b(that)e(users)i(will)d(choose)k(the)d(appropriate)i
(method)g(based)g(on)f(the)g(task)2040 3498 y(at)j(hand.)27
b(T)-6 b(o)19 b(understand)j(the)e(relati)n(v)o(e)g(beha)o(vior)g(of)g
(each)g(dissemination)2040 3585 y(method)f(under)g(dif)n(ferent)g
(conditions,)g(one)g(must)f(in)g(turn)g(understand)i(the)2040
3672 y(conte)o(xt)g(in)e(which)i(these)f(algorithms)g(will)f(be)h
(deplo)o(yed.)2040 3847 y(F)o(or)28 b(this)f(reason,)k(we)d(be)o(gin)h
(our)f(paper)h(with)e(an)i(o)o(v)o(ervie)n(w)f(of)g(related)2040
3934 y(w)o(ork)f(\(in)f(Section)h(2\))f(that)g(gi)n(v)o(es)h(a)g(sense)
g(of)f(the)g(role)h(played)g(by)g(data)2040 4021 y(dissemination)32
b(in)e(a)h(complete)g(sensornet)h(system.)59 b(Thereafter)m(,)33
b(Sec-)2040 4108 y(tion)g(3)f(pro)o(vides)i(a)e(general)i(discussion)f
(of)g(sensornet)g(dissemination)2040 4195 y(algorithms\227their)19
b(constituent)g(components)i(and)e(the)g(en)m(vironments)h(in)2040
4283 y(which)27 b(the)o(y)h(may)f(be)h(used.)48 b(In)27
b(Section)f(4)i(we)e(describe)i(three)f(canon-)2040 4370
y(ical)g(dissemination)h(methods)g(and)f(use)h(a)f(simple)g(analytical)
g(model)g(to)2040 4457 y(compare)20 b(their)f(costs.)2040
4631 y(There)g(may)g(be)g(man)o(y)g(viable)g(system)g(designs)h(for)e
(data-centric)h(storage.)2040 4718 y(W)-6 b(e)18 b(present)g(a)g
(scalable)g(DCS)g(system)g(design)h(that)f(b)o(uilds)g(on)g(tw)o(o)g
(recent)2040 4806 y(adv)n(ances:)26 b(\(1\))19 b(the)g(GPSR)f
(geographic)j(routing)f(algorithm)g([11])g(and)g(\(2\))2040
4893 y(a)k(ne)n(w)f(generation)i(of)e(ef)n(\002cient)h(peer)o(-to-peer)
g(lookup)g(systems)g(such)g(as)2040 4980 y(P)o(astry)-5
b(,)19 b(CAN,)f(Chord,)h(and)h(T)-6 b(apestry)20 b([6,)e(18,)i(21,)f
(24].)24 b(In)19 b(Section)g(5,)h(we)2040 5067 y(describe)j(the)f
(high-le)n(v)o(el)h(design)h(for)e(our)g(DCS)g(system,)h(which)g(we)f
(call)2040 5154 y(Geographic)i(Hash)g(T)-6 b(able)23
b(\(GHT\).)f(The)h(design)g(details)g(and)h(e)n(v)n(aluation)2040
5241 y(of)19 b(GHT)f(are)h(described)h(in)f(a)g(companion)i(paper)e
([19].)p Black Black eop
%%Page: 2 2
2 1 bop Black Black -152 -69 a Fn(2.)100 b(RELA)-9 b(TED)26
b(W)o(ORK)-152 23 y Fm(In)e(this)g(section,)h(we)f(brie\003y)f(re)n
(vie)n(w)i(related)e(w)o(ork)i(on)f(sensornets.)39 b(W)-6
b(e)-152 110 y(or)o(ganize)29 b(this)g(discussion)h(in)f
(\223layers\224)g(ordered)h(from)f(bottom)g(to)g(top.)-152
197 y(These)c(layers)g(are)g(used)h(only)f(to)g(clarify)g(the)g
(presentation)h(and)f(con)m(v)o(e)o(y)-152 284 y(a)h(sense)g(of)g(the)f
(role)h(of)f(data)h(dissemination)g(in)g(a)f(complete)i(sensornet)-152
371 y(system;)g(we)e(don')o(t)f(mean)h(to)f(imply)h(that)f(sensornet)h
(architecture)g(is)f(or)o(-)-152 459 y(ganized)g(into)f(clean,)h
(well-separated)g(layers.)36 b(W)-6 b(e)22 b(be)o(gin)i(our)f(re)n(vie)
n(w)h(at)-152 546 y(layer)18 b(three)h(\(pack)o(et)f(routing\),)h(as)f
(we)g(are)g(concerned)i(with)d(data)h(dissem-)-152 633
y(ination,)g(which)h(interacts)f(directly)g(with)f(layer)h(three)g(and)
h(abo)o(v)o(e.)24 b(Layers)-152 720 y(one)19 b(\(physical)e(and)i(OS\))
d(and)i(tw)o(o)g(\(lo)n(w-le)n(v)o(el)g(communication)h(and)f(self-)
-152 807 y(con\002guration\))i(are)f(comparati)n(v)o(ely)h(orthogonal)h
(to)e(data)g(dissemination.)-152 1019 y Fh(L3:)33 b(P)-7
b(ac)n(k)o(et)21 b(r)l(outing:)-152 1110 y Fm(P)o(ack)o(et)j(routing)g
(algorithms)f(are)h(required)g(to)f(deli)n(v)o(er)g(pack)o(ets)i
(between)-152 1197 y(nodes)i(that)d(are)i(not)f(in)g(mutual)g(radio)h
(range.)42 b(P)o(ack)o(et)25 b(routing)h(systems)-152
1285 y(based)g(on)f(node)h(identi\002ers)f(are)f(ill-suited)h(to)f
(sensornets,)j(where)e(com-)-152 1372 y(munication)h(isn')o(t)e
(addressed)i(to)f(node)h(identi\002ers.)40 b(It)24 b(is)h(e)o(xpected)h
(that)-152 1459 y(sensornets)21 b(will)e(instead)h(implement)h
(geographic)g(routing)g(systems)f(that)-152 1546 y(deli)n(v)o(er)30
b(pack)o(ets)g(to)f(nodes)i(based)f(on)g(their)e(location.)55
b(Belo)n(w)29 b(we)g(de-)-152 1633 y(scribe)e(se)n(v)o(eral)h(types)f
(of)g(geographic)i(routing)e(systems,)i(each)f(with)e(its)-152
1720 y(o)n(wn)21 b(communication)g(abstraction)g(and)f(ener)o(gy)h
(cost.)26 b(In)20 b(the)f(follo)n(wing,)-152 1808 y(we)j(let)f
Fl(n)g Fm(be)h(the)f(number)i(of)e(nodes)i(in)e(the)h(sensornet,)g(and)
h(assume)f(that)-152 1895 y(the)d(diameter)g(of)g(the)g(sensornet)h(is)
f(approximately)h Fl(O)p Ff(\()1332 1841 y Fj(p)p 1394
1841 38 3 v 54 x Fl(n)q Ff(\))p Fm(.)-152 2069 y Fl(Str)m(ongly)15
b(g)o(eo)o(gr)o(aphic)i Fm(routing)e(algorithms,)h(lik)o(e)e(GPSR)f
([11],)j(allo)n(w)e(nodes)-152 2156 y(to)32 b(send)h(to)e(a)h
(particular)g(location.)62 b(T)-6 b(o)32 b(go)g(from)g(one)h(random)f
(loca-)-152 2244 y(tion)22 b(to)f(another)h(requires)g
Fl(O)p Ff(\()655 2190 y Fj(p)p 717 2190 V 54 x Fl(n)p
Ff(\))f Fm(pack)o(et)i(transmissions,)f(which)f(is)g(our)-152
2331 y(\(approximate\))28 b(metric)f(for)f(total)h(ener)o(gy)g
(consumption.)49 b Fl(W)-7 b(eakly)28 b(g)o(eo-)-152
2418 y(gr)o(aphic)f Fm(routing)e(algorithms)h(lik)o(e)f(GEAR)f([23])i
(allo)n(w)f(a)g(node)h(to)f(send)-152 2505 y(pack)o(ets)k(to)e(a)h(re)o
(gion)g(and)g(then)f(distrib)o(ute)g(the)h(pack)o(et)g(within)g(that)f
(re-)-152 2592 y(gion.)36 b(The)23 b(transmission)g(costs)h(here)f(are)
g Fl(O)p Ff(\()1095 2539 y Fj(p)p 1157 2539 V 53 x Fl(n)p
Ff(\))g Fm(pack)o(et)h(transmission)-152 2679 y(to)15
b(reach)h(the)f(re)o(gion)h(and)g Fl(O)p Ff(\()p Fl(r)r
Ff(\))e Fm(pack)o(et)j(transmissions)e(within)g(the)g(re)o(gion,)-152
2767 y(where)20 b Fl(r)g Fm(is)f(the)g(number)g(of)g(nodes)h(in)f(the)g
(re)o(gion.)-152 2941 y(In)k(addition)g(to)f(geographic)i(routing,)f
(tw)o(o)f(other)h(pack)o(et)g(routing)g(primi-)-152 3028
y(ti)n(v)o(es)d(are)f(lik)o(ely)h(to)f(be)h(a)o(v)n(ailable)f(in)g
(sensor)i(netw)o(orks.)k Fl(Scoped)c(\003ooding)-152
3115 y Fm(algorithms)c(\003ood)g(to)g(a)f(limited)g(re)o(gion)h(around)
h(the)f(sending)h(node.)23 b(Their)-152 3202 y(transmission)d(cost)g
(is)f Fl(O)p Ff(\()p Fl(r)r Ff(\))g Fm(where)h Fl(r)h
Fm(is)e(the)g(number)i(of)e(nodes)i(in)e(the)h(re-)-152
3290 y(gion.)27 b Fl(Flooding)21 b Fm(sends)g(a)f(pack)o(et)h(to)f(the)
g(entire)g(sensornet,)h(and)f(requires)-152 3377 y Fl(O)p
Ff(\()p Fl(n)p Ff(\))f Fm(pack)o(et)h(transmissions.)-152
3588 y Fh(L4:)33 b(Local)22 b(collabor)o(ative)e(information)j(pr)l
(ocessing:)-152 3680 y Fm(Ev)o(ent)f(detection)g(sometimes)g(requires)g
(synthesizing)g(results)g(from)f(se)n(v-)-152 3767 y(eral)d(dif)n
(ferent)f(sensors.)24 b(The)17 b(algorithms)h(in)g(this)f(class)h(only)
g(require)g(col-)-152 3854 y(laboration)i(between)g(local)f(nodes;)h
Fl(i.e)o(.,)e Fm(those)h(that)g(can)h(be)f(reached)h(by)g(a)-152
3941 y(tightly-scoped)25 b(\003ood.)35 b(An)23 b(e)o(xample)h(of)f
(such)h(algorithms)f(is)g(described)-152 4028 y(in)c([22].)-152
4240 y Fh(L5:)33 b(W)-5 b(ide\255Ar)m(ea)21 b(data)h(dissemination:)
-152 4332 y Fm(Under)f(the)f(data-centric)g(architecture)h(for)f
(sensornets,)h(data)f(are)g(named.)-152 4419 y(The)j(data)f
(dissemination)i(methods)f(we)g(refer)f(to)g(here)h(allo)n(w)f(nodes)i
(and)-152 4506 y(users)k(to)e(access)i(data)f(by)g(name)h(across)f(the)
g(sensornet.)48 b(Note)27 b(that,)i(in)-152 4593 y(contrast,)d(the)f
(local)f(collaborati)n(v)o(e)i(information)f(processing)h(only)f(used)
-152 4680 y(data)15 b(that)g(could)h(be)f(found)h(nearby;)h(these)e
(wide-area)h(data)f(dissemination)-152 4767 y(methods)i(are)g(needed)g
(to)f(do)h(collaborati)n(v)o(e)g(processing)g(in)f(the)h(wide)f(area,)
-152 4855 y(as)j(we)g(describe)h(belo)n(w)-5 b(.)-152
5029 y(The)17 b(most)f(commonly)i(mentioned)f(wide-area)g(data)f
(dissemination)h(tech-)-152 5116 y(nique)i(is)f Fl(dir)m(ected)h(dif)o
(fusion)f Fm([9,)g(10],)g(an)h(e)o(xample)g(of)f Fl(data-centric)h(r)m
(out-)-152 5203 y(ing)p Fm(:)k(routing)18 b(decisions)g(are)g(based)g
(on)g(the)g(name)g(of)f(the)h(data)g(rather)f(than)-152
5290 y(on)22 b(the)f(identity)g(of)g(the)h(sending)g(and)g(recei)n
(ving)g(nodes.)30 b(W)-6 b(e)21 b(discuss)h(di-)-152
5378 y(rected)j(dif)n(fusion)f(at)g(greater)g(length)h(in)f(Section)g
(4.3.)38 b(In)24 b(this)g(paper)h(we)2040 -69 y(propose)16
b(another)f(data)g(dissemination)g(approach:)23 b Fl(data-centric)15
b(stor)o(a)o(g)o(e)p Fm(,)2040 19 y(whereby)20 b(e)n(v)o(ent)g
(information)f(is)g(stored)g(by)g(name)h(within)e(the)h(sensornet.)2040
193 y(It)31 b(should)h(be)f(noted)h(that)f(directed)h(dif)n(fusion)g
(\(and)g(most)f(other)g(data-)2040 280 y(centric)g(routing)h
(proposals\))h(do)e(not)h(require)f(an)o(y)h(pack)o(et)g(forw)o(arding)
2040 367 y(methods)i(other)e(than)h(\003ooding.)65 b(In)32
b(contrast,)k(the)c(data-centric)h(stor)o(-)2040 454
y(age)19 b(proposal)h(we)f(present)g(here)g(requires)g(strongly)h
(geographic)g(routing.)2040 542 y(Thus,)g(the)g(data)g(dissemination)h
(method)g(choice)g(may)f(be)g(limited)g(by)g(the)2040
629 y(nature)g(of)e(the)h(underlying)i(pack)o(et)f(routing)f
(mechanisms.)2040 831 y Fh(L6:)33 b(W)-5 b(ide\255ar)m(ea)21
b(collabor)o(ative)f(information)i(pr)l(ocessing:)2040
922 y Fm(These)f(methods)g(are)g(akin)f(to)h(the)f(local)h(collaborati)
n(v)o(e)g(information)g(pro-)2040 1010 y(cessing)32 b(methods)g
(mentioned)g(abo)o(v)o(e,)i(e)o(xcept)e(that)e(the)h(collaborating)2040
1097 y(nodes)19 b(need)f(not)g(be)h(local.)j(An)c(e)o(xample)h(of)e
(such)i(a)e(collaboration)i(is)f(that)2040 1184 y(required)25
b(for)f(tracking)h(an)f(object)h(across)g(a)f(sensor)h(\002eld.)38
b(In)24 b(this)g(case,)2040 1271 y(scalable)19 b(collaborati)n(v)o(e)h
(methods)g(must)e(be)h(b)o(uilt)f(on)i(ef)n(\002cient)e(wide-area)2040
1358 y(data-dissemination)i(algorithms.)k(Zhao)19 b Fl(et)g(al.)f
Fm([25])h(describe)h(a)f(collabo-)2040 1445 y(rati)n(v)o(e)g(tracking)g
(application)h(b)o(uilt)e(on)i(top)f(of)g(directed)g(dif)n(fusion.)2040
1648 y Fh(L7:)33 b(User)n(\255le)o(vel)21 b(tasking)h(and)f(querying:)
2040 1739 y Fm(The)j(highest)g(layer)f(is)g(where)h(users)g(insert)f
(their)h(tasking)g(and)g(querying)2040 1826 y(commands.)35
b(An)22 b(e)o(xample)h(of)f(an)h(approach)h(that)e(\002ts)f(here)i(is)f
(w)o(ork)h(that)2040 1913 y(has)17 b(been)h(done)g(on)f(de\002ning)h
(database)g(semantics)f(for)g(queries)g(on)h(sensor)2040
2001 y(netw)o(orks)i([2,)f(8,)f(14].)2040 2203 y Fn(3.)99
b(ASSUMPTIONS)26 b(AND)f(TERMINOLOGY)2040 2294 y Fm(This)e(section)h
(lays)g(out)f(the)h(conte)o(xt)g(for)f(the)h(dissemination)g
(algorithms)2040 2382 y(discussed)19 b(in)g(the)f(follo)n(wing)g
(section.)24 b(W)-6 b(e)17 b(\002rst)h(state)g(our)g(basic)h(assump-)
2040 2469 y(tions)25 b(about)h(the)e(class)h(of)g(sensornets)h(we)e
(consider)i(and)f(then)h(describe)2040 2556 y(some)20
b(basic)f(concepts)i(re)o(garding)e(sensornet)h(data)g(and)g(ho)n(w)f
(the)o(y)h(are)f(or)o(-)2040 2643 y(ganized.)2040 2845
y Fn(3.1)99 b(Assumptions)2040 2937 y Fm(Projected)30
b(sensornet)h(designs)g(in)f(the)g(literature)f([5])h(dif)n(fer)g
(greatly)g(in)2040 3024 y(their)20 b(characteristics)g(and)h(intended)g
(uses.)27 b(Here)20 b(we)g(focus)h(attention)f(on)2040
3111 y(that)29 b(class)h(of)f(sensornets)h(where)g(wide-area)g(data)f
(dissemination)i(is)d(a)2040 3198 y(needed)20 b(service.)2040
3373 y(W)-6 b(e)23 b(consider)h(lar)o(ge-scale)f(sensornets)i(with)d
(nodes)j(that)e(are)g(spread)h(out)2040 3460 y(o)o(v)o(er)15
b(some)g(well-de\002ned)f(area,)i(whose)f(approximate)g(geographic)i
(bound-)2040 3547 y(aries)i(are)g(kno)n(wn)h(to)f(netw)o(ork)h
(operators.)2040 3721 y(W)-6 b(e)21 b(assume)g(nodes)h(ha)o(v)o(e)f
(short)h(range)f(communication,)i(b)o(ut)e(are)g(within)2040
3808 y(radio)j(range)g(of)g(se)n(v)o(eral)g(other)g(nodes.)39
b(W)-6 b(e)23 b(further)g(assume)i(that)e(nodes)2040
3896 y(kno)n(w)31 b(their)f(o)n(wn)h(locations.)58 b(GPS)29
b(or)i(some)f(other)h(approximate)h(b)o(ut)2040 3983
y(less)22 b(b)o(urdensome)h(localization)g(algorithm)f([3,)g(7,)h(16,)f
(17,)h(20])f(pro)o(vides)2040 4070 y(this)d(information.)25
b(This)19 b(assumption)h(is)f(crucial)g(for)h(our)f(proposed)i(data-)
2040 4157 y(centric)g(storage)g(mechanism.)28 b(W)-6
b(e)20 b(belie)n(v)o(e)h(it)f(a)g(reasonable)i(assumption)2040
4244 y(because)g(in)f(man)o(y)h(cases)g(the)f(sensornet)h(data)g(are)f
(useful)g(only)h(if)e(the)i(lo-)2040 4332 y(cations)d(of)g(their)g
(sources)h(are)f(kno)n(wn.)2040 4506 y(W)-6 b(e)22 b(further)h(assume)h
(that)e(communication)j(to)d(the)h(outside)h(w)o(orld)f(tak)o(es)2040
4593 y(place)j(through)h(one)f(or)g(more)g(access)g(points)g(in)f(the)h
(sensornet,)i(and)e(so)2040 4680 y(getting)i(data)g(from)g(a)g
(sensornet)g(node)h(to)f(the)g(outside)g(w)o(orld)g(requires)2040
4767 y(sending)22 b(the)e(data)h(through)g(the)g(sensornet)g(to)f(the)h
(access)f(point.)28 b(W)-6 b(e)20 b(use)2040 4855 y(the)15
b(term)f Fl(access)h(path)h Fm(to)e(refer)g(to)h(the)f(set)h(of)f
(paths)h(data)g(tak)o(e)g(from)g(sensor)2040 4942 y(nodes)28
b(to)e(the)h(access)g(point\(s\).)47 b(This)26 b(assumption)i(is)f(not)
f(required)i(by)2040 5029 y(our)18 b(DCS)f(mechanism)i
Fl(per)f(se)p Fm(,)g(b)o(ut)g(is)f(part)h(of)g(our)g(model)g(for)g
(comparing)2040 5116 y(costs)h(of)g(dif)n(ferent)g(dissemination)h
(mechanisms.)2040 5290 y(W)-6 b(e)17 b(assume)i(ener)o(gy)g(is)e(a)h
(scarce)g(commodity)h(for)f(sensornet)h(nodes)f([15],)2040
5378 y(such)28 b(that)e(data)h(dissemination)h(algorithms)f(should)g
(seek)h(to)e(minimize)p Black Black eop
%%Page: 3 3
3 2 bop Black Black -152 -69 a Fm(communication)26 b(in)f(order)g(to)f
(e)o(xtend)h(o)o(v)o(erall)g(system)f(lifetime.)39 b(While)-152
19 y(the)26 b(mapping)i(between)e(communication)i(and)f(ener)o(gy)f
(consumption)i(is)-152 106 y(complicated\227it)22 b(depends)h(greatly)f
(on)f(the)h(precise)g(hardw)o(are)g(in)m(v)o(olv)o(ed)-152
193 y(and)c(the)e(pack)o(et)i(transmission)f(pattern\227in)g(what)g
(follo)n(ws)g(we)f(will)g(focus)-152 280 y(on)k(tw)o(o)f(simpli\002ed)f
(metrics)h(of)g(ener)o(gy)h(consumption:)p Black -152
534 a Fe(T)-7 b(otal)19 b(usage:)p Black 38 w Fm(The)g(total)f(number)i
(of)f(pack)o(ets)h(sent)f(in)g(the)g(sensornet)p Black
-152 671 a Fe(Hotspot)g(usage:)p Black 38 w Fm(The)i(maximal)h(number)g
(of)f(pack)o(ets)h(sent)g(by)f(an)o(y)h(par)o(-)35 758
y(ticular)d(sensornet)h(node)-152 952 y(While)e(in)h(the)f(rest)g(of)h
(the)f(paper)h(we)g(treat)f(all)g(nodes)h(as)g(ha)o(ving)g(the)f(same)
-152 1039 y(capabilities,)h(it)f(is)h(lik)o(ely)g(that)f(real)h
(sensornets)h(will)e(ha)o(v)o(e)h(a)g(tiered)g(archi-)-152
1126 y(tecture,)i(where)g(some)g(nodes)h(ha)o(v)o(e)f(v)o(ery)g
(limited)g(data)g(storage)g(capacity)-152 1213 y(and)27
b(others)f(ha)o(v)o(e)g(much)h(more)f(signi\002cant)g(storage)h(\(and)f
(perhaps)h(also)-152 1301 y(more)22 b(battery)f(po)n(wer)h(and)f
(better)g(communication)i(f)o(acilities\).)29 b(Our)21
b(dis-)-152 1388 y(cussion)g(applies)f(to)g(this)f(tiered)h(approach)i
(as)d(well,)g(as)h(long)h(as)e(the)h(these)-152 1475
y(\223macronodes\224)h(are)e(numerous)i(and)e(widely)g(dispersed)h
([4].)-152 1649 y(These)26 b(assumptions)h(describe)f(the)g(physical)g
(en)m(vironment)h(of)f(the)f(sen-)-152 1736 y(sornet.)f(W)-6
b(e)18 b(ne)o(xt)h(discuss)h(ho)n(w)f(these)h(sensornets)g(might)f(be)g
(used.)-152 1940 y Fn(3.2)99 b(Obser)o(v)o(ations)25
b(and)g(Ev)o(ents)-152 2031 y Fm(The)15 b(purpose)h(of)f(sensornets)g
(is)g(to)f(pro)o(vide)i(detailed)f(sensing)h(capabilities)-152
2119 y(across)23 b(a)f(wide)g(geographic)i(area.)32 b(The)22
b(lo)n(w-le)n(v)o(el)g(readings)h(from)f(these)-152 2206
y(sensors,)j(which)e(we)f(call)h Fl(observations)p Fm(,)i(are)e(named)g
(\(as)g(described,)i(for)-152 2293 y(e)o(xample,)k(in)d([1,)i(9]\).)45
b(While)25 b(sensornets)j(gi)n(v)o(e)e(unprecedented)j(access)-152
2380 y(to)d(detailed)g(observ)n(ations)i(of)e(the)g(physical)g(w)o
(orld,)i(sending)f(this)f(o)o(v)o(er)o(-)-152 2467 y(whelming)k(v)o
(olume)g(of)f(observ)n(ations)i(directly)e(to)g(the)h(access)f
(point\(s\))-152 2554 y(w)o(ould)d(quickly)g(e)o(xhaust)f(the)g(ener)o
(gy)h(reserv)o(es)f(of)g(the)g(sensornet.)42 b(F)o(or)o(-)-152
2642 y(tunately)-5 b(,)30 b(in)d(most)h(cases)g(users)g(don')o(t)f(w)o
(ant)h(the)f(complete)h(set)g(of)f(ra)o(w)-152 2729 y(unprocessed)c
(data,)e(b)o(ut)g(rather)g(are)g(more)g(interested)g(in)g(speci\002c)g
Fl(e)o(vents)p Fm(,)-152 2816 y(such)f(as)f(earthquak)o(es)i(or)e
(animal)g(sightings.)-152 2990 y(W)-6 b(e)29 b(use)h(the)f(term)g
Fl(e)o(vents)h Fm(to)f(refer)g(to)g(certain)g(pre-de\002ned)h
(constella-)-152 3078 y(tions)21 b(of)f(lo)n(w-le)n(v)o(el)g(observ)n
(ations.)28 b(F)o(or)20 b(e)o(xample,)h(detailed)f(temperature)-152
3165 y(and)27 b(pressure)f(readings)h(might)e(constitute)h(observ)n
(ations,)j(while)c(a)h(par)o(-)-152 3252 y(ticular)i(combination)i(of)e
(temperature)h(and)g(pressure)g(might)g(de\002ne)f(an)-152
3339 y(\223elephant-sighting\224)23 b(e)n(v)o(ent.)31
b(A)20 b(sensornet)i(system)g(will)e(be)h(designed)i(to)-152
3426 y(detect)18 b(se)n(v)o(eral)f(well-de\002ned)g Fl(types)h
Fm(of)f(e)n(v)o(ents.)23 b(T)-6 b(ypically)h(,)17 b(the)g(lar)o(ge)g(v)
o(ol-)-152 3513 y(ume)22 b(of)f(observ)n(ations)i(prohibits)f
(communicating)h(them)e(directly)g(to)h(the)-152 3601
y(outside)f(w)o(orld.)26 b(Ev)o(ents)20 b(are)f(thus)i(deri)n(v)o(ed)f
(by)g(processing)i(the)d(lo)n(w-le)n(v)o(el)-152 3688
y(observ)n(ations)29 b(within)e(the)g(sensornet)h(through)g
Fl(collabor)o(ative)g(informa-)-152 3775 y(tion)19 b(pr)m(ocessing)h
Fm(techniques.)-152 3949 y(Ev)o(ents)j(can)h(be)f(de\002ned)h(not)f
(only)h(in)f(terms)g(of)g(lo)n(w-le)n(v)o(el)g(observ)n(ations)-152
4036 y(b)o(ut)j(also)g(in)g(terms)g(of)g(other)h(e)n(v)o(ents.)45
b(F)o(or)25 b(instance,)k(detecting)d(an)h(ani-)-152
4124 y(mal)20 b(migration)h(w)o(ould)f(in)m(v)o(olv)o(e)h(man)o(y)f
(indi)n(vidual)h(animal)g(sightings.)27 b(In)-152 4211
y(general,)21 b(there)f(will)f(be)i(a)f Fl(web)g Fm(of)g(e)n(v)o(ents,)
h(with)f(some)g(e)n(v)o(ents)h(de\002ned)g(in)-152 4298
y(terms)26 b(of)f(others.)44 b(These)26 b(e)n(v)o(ents)g(are)g(not)g
(necessarily)g(in)g(a)f(strict)g(hier)o(-)-152 4385 y(archy)-5
b(,)28 b(b)o(ut)d(in)g(the)h(conte)o(xt)g(of)g(a)f(particular)h
(application)g(there)g(is)f(some)-152 4472 y(sense)j(that)f(some)h(e)n
(v)o(ents)g(are)g(lo)n(wer)o(-le)n(v)o(el)f(than)h(others,)h(and)f
(could)g(be)-152 4559 y(used)20 b(to)f(de\002ne)g(the)g(higher)o(-le)n
(v)o(el)g(e)n(v)o(ents.)-152 4763 y Fn(3.3)99 b(T)-9
b(asks,)25 b(Actions,)g(and)h(Queries)-152 4855 y Fm(The)15
b(preceding)h(discussion)f(identi\002ed)g(the)f(v)n(arious)h(types)g
(of)g(information\227)-152 4942 y(observ)n(ations)i(and)e(e)n(v)o
(ents\227that)g(might)g(be)f(pro)o(vided)i(by)f(sensornets.)23
b(W)-6 b(e)-152 5029 y(no)n(w)20 b(describe)f(the)g(operations)h(used)g
(to)f(manipulate)h(these)f(data.)-152 5203 y(Users)j(send)h
(instructions)f(\(by)g(\003ooding)h(or)f(some)h(other)f(global)g
(dissem-)-152 5290 y(ination)i(method\))h(to)f(sensornet)g(nodes)h(to)f
(run)g(certain)g(local)g(identi\002ca-)-152 5378 y(tion)18
b Fl(tasks)p Fm(.)23 b(These)c(tasks)f(could)h(be)f(simple,)g(such)g
(as)g(taking)h(temperature)2040 -69 y(readings,)32 b(or)c(comple)o(x,)k
(such)d(as)g(identifying)g(an)g(animal)f(from)h(a)f(col-)2040
19 y(lection)f(of)g(sensor)h(readings.)48 b(In)27 b(essence,)i(one)f
(can)f(think)g(of)g(tasks)g(as)2040 106 y(do)n(wnloaded)21
b(code.)2040 280 y(Once)g(an)g(e)n(v)o(ent)h(has)f(been)h
(identi\002ed,)f(nodes)g(can)h(tak)o(e)f(one)g(of)g(three)g
Fl(ac-)2040 367 y(tions)p Fm(:)g(a)16 b(node)g(could)g(send)f(e)n(v)o
(ent)h(information)g(to)f(e)o(xternal)g(storage,)h(store)2040
454 y(the)27 b(e)n(v)o(ent)g(information)g(locally)-5
b(,)29 b(or)d(use)h(data-centric)g(storage.)47 b(Recall)2040
542 y(that)19 b(data-centric)g(storage)g(in)m(v)o(olv)o(es)g(storing)g
(the)g(e)n(v)o(ent)h(information)f(at)f(a)2040 629 y(sensornet)26
b(node)f(that)g(is)f(chosen)h(based)h(on)f(the)f(e)n(v)o(ent')l(s)h
(name.)3780 602 y Fo(1)3854 629 y Fm(These)2040 716 y(three)20
b(possible)h(actions\227e)o(xternal)g(store,)e(local)h(store,)g(and)h
(data-centric)2040 803 y(store\227form)c(the)f(core)h(of)f(the)h(three)
f(canonical)i(approaches)g(we)f(describe)2040 890 y(in)i(Section)g(4.)
2040 1065 y(Unless)29 b(the)g(information)h(has)f(been)h(sent)f(to)g(e)
o(xternal)g(storage,)j(at)d(this)2040 1152 y(stage)20
b(the)h(e)n(v)o(ent)f(information)h(is)f(still)f(not)h(in)g(the)g
(user')l(s)g(hands.)28 b Fl(Queries)2040 1239 y Fm(are)e(used)g(to)g
(elicit)f(the)h(e)n(v)o(ent)g(information)g(from)g(the)g(sensornet.)44
b(Ho)n(w)2040 1326 y(queries)27 b(are)g(e)o(x)o(ecuted)h(will)e(depend)
i(on)f(the)g(actions)g(nodes)h(tak)o(e)f(upon)2040 1413
y(e)n(v)o(ent)22 b(detection.)31 b(If)21 b(e)n(v)o(ent)h(information)g
(is)f(stored)h(locally)f(then)h(queries)2040 1500 y(must)h(be)g
(\003ooded)g(to)g(all)f(nodes)i(\(unless)f(the)g(user)g(has)g(prior)g
(kno)n(wledge)2040 1588 y(about)17 b(the)g(location)f(of)h(the)f(e)n(v)
o(ent\).)23 b(If)15 b(e)n(v)o(ent)i(information)g(is)f(stored)h(using)
2040 1675 y(data-centric)28 b(storage,)h(the)f(query)g(can)g(be)f(sent)
h(to)f(the)g(sensornet)h(node)2040 1762 y(associated)20
b(with)e(that)h(e)n(v)o(ent)h(name.)2040 1975 y Fn(4.)99
b(D)m(A)-9 b(T)g(A\255DISSEMIN)n(A)g(TION)25 b(METHODS)2040
2067 y Fm(The)f(main)g(goal)h(in)f(a)g(data-dissemination)h(algorithm)f
(is)g(to)g(e)o(xtract)g(rel-)2040 2154 y(e)n(v)n(ant)30
b(data)f(ef)n(\002ciently)f(from)h(within)f(the)h(sensornet.)53
b(In)29 b(this)f(section,)2040 2241 y(we)c(consider)h(three)e
Fl(canonical)j Fm(methods)e(that)g(combine)h(the)f(pieces)g(de-)2040
2328 y(scribed)19 b(in)e(the)i(preceding)g(section)f(dif)n(ferently)-5
b(,)19 b(yielding)f(three)g(v)o(ery)h(dif-)2040 2415
y(ferent)c(approaches)h(to)f(sensornet)h(design.)22 b(W)-6
b(e)14 b(\002rst)g(describe)h(these)g(meth-)2040 2503
y(ods)20 b(and)f(then)g(compare)h(their)f(costs)g(analytically)-5
b(.)2040 2677 y(All)25 b(the)i(dissemination)g(methods)g(be)o(gin)f(by)
h(\003ooding)g(the)f(tasks)g(to)g(the)2040 2764 y(entire)18
b(sensornet.)24 b(The)18 b(tasks)g(are)h(the)f(set)g(of)g
(identi\002cation)g(instructions,)2040 2851 y(specifying)28
b(which)f(e)n(v)o(ents)h(to)f(detect,)i(ho)n(w)e(to)g(detect)g(them,)i
(and)e(what)2040 2938 y(actions)19 b(to)g(tak)o(e)h(upon)g(detection.)k
(W)-6 b(e)18 b(assume)i(that)f(the)g(tasking)g(instruc-)2040
3026 y(tions)28 b(remain)g(in)f(force)h(for)f(long)i(periods)f(of)f
(time,)i(so)f(that)g(the)f(initial)2040 3113 y(cost)d(of)g(issuing)h
(tasks)f(is)g(dominated)h(by)g(the)f(cost)h(of)f(the)g(ensuing)h(data)
2040 3200 y(processing.)2377 3173 y Fo(2)2040 3374 y
Fm(W)-6 b(e)20 b(also)g(assume)g(that)g(e)n(v)o(ent)h(locations)f(are)g
(not)g(kno)n(wn)h(in)f(adv)n(ance)i(and)2040 3461 y(are)c(distrib)o
(uted)h(randomly)g(throughout)h(the)e(sensornet.)24 b(The)18
b(case)h(where)2040 3549 y(this)e(assumption)i(does)g(not)f(hold)g(is)f
(discussed)i(in)e(the)h(follo)n(wing)g(section.)2040
3723 y(Finally)-5 b(,)22 b(in)g(e)n(v)n(aluating)h(communication)g
(costs)f(we)g(assume)h(asymptotic)2040 3810 y(costs)33
b(of)g Fl(O)p Ff(\()p Fl(n)p Ff(\))g Fm(message)h(transmissions)g(for)f
(\003oods)g(and)h Fl(O)p Ff(\()3784 3757 y Fj(p)p 3846
3757 38 3 v 53 x Fl(n)q Ff(\))f Fm(for)2040 3897 y(point-to-point)20
b(routing)f(where)h Fl(n)f Fm(is)f(the)h(number)h(of)f(nodes.)2040
4111 y Fn(4.1)99 b(Canonical)25 b(Methods)2040 4202 y
Fm(Earlier)19 b(we)g(described)i(three)e(basic)h(actions)g(nodes)g
(could)h(tak)o(e)f(upon)g(de-)2040 4289 y(tecting)25
b(an)g(e)n(v)o(ent.)40 b(These)25 b(lead)f(directly)h(to)f(three)h
(canonical)g(sensornet)2040 4376 y(methods.)2040 4590
y Fh(External)c(Stor)o(a)o(g)o(e)g(\(ES\):)2040 4681
y Fm(Upon)d(detection)g(of)f(e)n(v)o(ents,)h(the)f(rele)n(v)n(ant)h
(data)f(are)g(sent)h(to)f(e)o(xternal)g(stor)o(-)2040
4768 y(age)j(where)g(the)o(y)f(are)h(further)f(processed)i(as)e
(needed.)26 b(This)19 b(entails)g(a)g(cost)p Black 2040
4828 797 4 v 2044 4888 a Fo(1)2077 4916 y Fm(This)f(approach,)h(lik)o
(e)e(all)g(data-centric)h(approaches,)h(requires)f(a)f(naming)2040
4990 y(scheme.)24 b(W)-6 b(e)17 b(do)i(not)f(address)h(this)f(issue)g
(here,)h(b)o(ut)f(merely)g(note)g(that)g(the)2040 5065
y(naming)g(scheme)g(is)f(part)g(of)g(the)g(de\002nition)g(of)h(e)n(v)o
(ents)f(and)h(is)f(supplied)h(by)2040 5140 y(the)h(globally)h
(disseminated)g(tasking)f(instructions.)2044 5201 y Fo(2)2077
5228 y Fm(In)f(situations)f(where)h(tasks)g(are)f(short-li)n(v)o(ed,)h
(the)f(cost)h(of)f(\003ooding)h(tasks)2040 5303 y(dominates)k(all)e
(other)i(costs,)f(and)g(it)g(doesn')o(t)g(matter)f(much)i(which)f(of)g
(the)2040 5378 y(approaches)g(belo)n(w)e(is)g(used.)p
Black Black Black eop
%%Page: 4 4
4 3 bop Black Black -152 -69 a Fm(of)17 b Fl(O)p Ff(\()10
-122 y Fj(p)p 72 -122 38 3 v 53 x Fl(n)p Ff(\))g Fm(for)f(each)h(e)n(v)
o(ent.)23 b(There)17 b(is)f(no)h(cost)g(for)f(e)o(xternal)h(queries)g
(since)-152 19 y(the)22 b(e)n(v)o(ent)h(information)f(is)f(already)i(e)
o(xternal;)g(queries)g(generated)g(by)f(in-)-152 106
y(ternal)j(nodes)h(in)e(the)h(process)h(of)f(e)n(v)o(ent)g(detection)g
(will)f(incur)h(a)g(cost)g(of)-152 193 y Fl(O)p Ff(\()-69
139 y Fj(p)p -7 139 V 54 x Fl(n)q Ff(\))19 b Fm(to)f(reach)i(the)f(e)o
(xternal)g(storage.)-152 392 y Fh(Local)j(Stor)o(a)o(g)o(e)f(\(LS\):)
-152 483 y Fm(Ev)o(ent)30 b(information)h(is)e(stored)h(locally)h(\(at)
e(the)h(detecting)h(node\))f(upon)-152 570 y(detection)20
b(of)f(an)h(e)n(v)o(ent;)f(this)g(incurs)h(no)g(communication)g(costs.)
k(Queries)-152 658 y(are)c(\003ooded)h(to)f(all)g(nodes)h(at)f(a)g
(cost)g(of)g Fl(O)p Ff(\()p Fl(n)p Ff(\))p Fm(.)26 b(Responses)c(are)e
(sent)g(back)-152 745 y(to)f(the)g(source)h(of)f(the)g(query)h(at)e(a)h
(cost)g(of)g Fl(O)p Ff(\()1056 691 y Fj(p)p 1118 691
V 54 x Fl(n)q Ff(\))f Fm(each.)-152 944 y Fh(Data\255Centric)k(Stor)o
(a)o(g)o(e)f(\(DS\):)-152 1035 y Fm(Here,)g(after)g(an)g(e)n(v)o(ent)g
(is)f(detected)i(the)e(data)h(are)g(stored)g(by)h(name)f(within)-152
1122 y(the)c(sensornet.)23 b(The)16 b(communication)i(cost)e(to)g
(store)g(the)g(e)n(v)o(ent)h(is)f Fl(O)p Ff(\()1694 1069
y Fj(p)p 1756 1069 V 53 x Fl(n)p Ff(\))p Fm(.)-152 1209
y(Queries)28 b(are)g(directed)h(to)e(the)h(node)h(that)f(stores)g(e)n
(v)o(ents)h(of)f(that)f(name,)-152 1297 y(which)20 b(returns)f(a)g
(response,)g(both)h(at)f(a)f(cost)i(of)e Fl(O)p Ff(\()1205
1243 y Fj(p)p 1268 1243 V 1268 1297 a Fl(n)p Ff(\))p
Fm(.)-152 1471 y(These)k(three)f(canonical)h(methods)h(ha)o(v)o(e)e(v)o
(ery)h(dif)n(ferent)f(cost)h(structures;)-152 1558 y(we)d(compare)h
(these)f(analytically)h(in)e(the)h(ne)o(xt)h(subsection.)-152
1757 y Fn(4.2)99 b(A)n(ppr)n(oximate)26 b(Communication)f(Costs)-152
1848 y Fm(This)d(section)g(uses)g(a)g(simple)g(analytical)g(model)g(to)
g(deri)n(v)o(e)g(approximate)-152 1936 y(formulae)17
b(for)f(the)g(communication)h(costs)f(for)g(the)g(three)g(canonical)i
(meth-)-152 2023 y(ods;)k(these)f(formulae)g(suggest)h(which)f(method)h
(is)e(best)h(suited)g(for)f(a)h(par)o(-)-152 2110 y(ticular)e
(sensornet)h(w)o(orkload.)658 2083 y Fo(3)-152 2284 y
Fm(The)c(cost)g(structure)g(for)g(the)g(canonical)h(methods)g(is)f
(described)h(by)f(se)n(v)o(eral)-152 2371 y(parameters.)28
b(W)-6 b(e)20 b(consider)h(a)f(sensornet)i(with)d Fl(n)i
Fm(nodes)g(equipped)h(to)e(de-)-152 2459 y(tect)h Fl(T)29
b Fm(e)n(v)o(ent)21 b(types.)28 b(W)-6 b(e)21 b(let)f
Fl(D)698 2473 y Fc(t)t(o)o(t)t(al)838 2459 y Fm(denote)h(the)g(total)f
(number)h(of)g(e)n(v)o(ents)-152 2546 y(detected,)e Fl(Q)f
Fm(denote)h(the)f(number)h(of)f(e)n(v)o(ent)h(types)g(for)f(which)g
(queries)h(are)-152 2633 y(issued,)f(and)h Fl(D)251 2644
y Fc(q)301 2633 y Fm(denote)g(the)e(number)i(of)f(e)n(v)o(ents)g
(detected)g(for)g(each)g(e)n(v)o(ent)-152 2720 y(queried)25
b(for)l(.)36 b(W)-6 b(e)23 b(assume)h(there)f(is)g(no)h(more)g(than)f
(one)h(query)h(for)e(each)-152 2807 y(e)n(v)o(ent)d(type,)f(so)g(there)
g(are)g Fl(Q)g Fm(queries)g(in)g(total.)-152 2982 y(In)d(comparing)h
(costs,)f(we)f(also)h(consider)g(the)g(case)g(where)f(users)h(only)g
(care)-152 3069 y(about)h(a)e(summary)h(of)g(the)f(e)n(v)o(ents)h
(rather)g(than)g(a)f(listing)g(of)g(each)h(one;)i Fl(e)o(.g)o(.,)-152
3156 y Fm(one)i(might)f(just)g(w)o(ant)g(a)g(count)h(of)f(the)g(number)
h(of)f(elephants)h(seen)g(rather)-152 3243 y(than)g(a)f(listing)f(of)h
(each)h(elephant)f(sighting.)-152 3417 y(W)-6 b(e)21
b(compare)h(costs)g(using)g(approximations)h(for)e(both)g(the)h(total)f
(number)-152 3505 y(of)g(pack)o(ets)g(and)h(the)e(pack)o(ets)i(arri)n
(ving)f(at)f(the)h(access)g(point.)28 b(The)21 b(pack)o(et)-152
3592 y(count)26 b(at)e(the)h(access)g(point)g(is)f(a)h(good)h(estimate)
e(of)h(the)g(hotspot)g(usage,)-152 3679 y(since)f(we)f(e)o(xpect)h(the)
g(access)f(point)h(to)f(be)h(the)f(most)h(hea)o(vily)f(used)h(area)-152
3766 y(of)19 b(the)g(sensornet.)p Black -152 4016 a Fe(Exter)o(nal)g
(Storage:)p Black 271 4103 a Fm(T)-6 b(otal:)23 b Fl(D)520
4117 y Fc(t)t(o)o(t)t(al)639 4050 y Fj(p)p 701 4050 V
53 x Fl(n)601 b Fm(Hotspot:)23 b Fl(D)1672 4117 y Fc(t)t(o)o(t)t(al)p
Black -152 4250 a Fe(Local)d(Storage:)p Black 205 4337
a Fm(T)-6 b(otal:)23 b Fl(Qn)10 b Ff(+)g Fl(D)624 4348
y Fc(q)658 4284 y Fj(p)p 720 4284 V 53 x Fl(n)600 b Fm(Hotspot:)24
b Fl(Q)10 b Ff(+)g Fl(D)1824 4348 y Fc(q)p Black -152
4484 a Fe(Data-Centric)19 b(Storage:)p Black 35 4571
a Fm(T)-6 b(otal:)23 b Fl(Q)285 4518 y Fj(p)p 347 4518
V 53 x Fl(n)11 b Ff(+)f Fl(D)516 4585 y Fc(t)t(o)o(t)t(al)636
4518 y Fj(p)p 698 4518 V 53 x Fl(n)h Ff(+)f Fl(D)868
4582 y Fc(q)901 4518 y Fj(p)p 964 4518 V 964 4571 a Fl(n)19
b Fm(\(list\))35 4658 y(T)-6 b(otal:)23 b Fl(Q)285 4605
y Fj(p)p 347 4605 V 53 x Fl(n)11 b Ff(+)f Fl(D)516 4672
y Fc(t)t(o)o(t)t(al)636 4605 y Fj(p)p 698 4605 V 53 x
Fl(n)h Ff(+)f Fl(Q)868 4605 y Fj(p)p 930 4605 V 53 x
Fl(n)19 b Fm(\(summary\))35 4745 y(Hotspot:)24 b Fl(Q)10
b Ff(+)g Fl(D)502 4756 y Fc(q)554 4745 y Fm(\(list\))18
b(or)h(2)p Fl(Q)g Fm(\(summary\))-152 4996 y(In)j(the)g(abo)o(v)o(e,)g
(\(list\))f(indicates)h(a)f(full)h(listing)f(of)g(e)n(v)o(ents)i(is)e
(returned)h(\(re-)-152 5083 y(quiring)29 b(a)e(pack)o(et)i(for)e(each)i
(e)n(v)o(ent\))f(and)g(\(summary\))g(indicates)g(only)h(a)-152
5170 y(summary)20 b(of)f(e)n(v)o(ents)h(is)e(returned)i(\(requiring)f
(only)h(one)f(pack)o(et\).)p Black -152 5215 797 4 v
-148 5276 a Fo(3)-114 5303 y Fm(In)e(a)g(companion)i(paper)f([19],)g
(we)f(v)o(erify)h(the)f(v)n(alidity)h(of)f(these)g(approx-)-152
5378 y(imations)i(through)i(simulation.)p Black 2040
-69 a(These)15 b(calculations)g(suggest)g(a)g(fe)n(w)f(straightforw)o
(ard)h(observ)n(ations.)23 b(First,)2040 19 y(if)f(all)g(other)g
(parameters)h(are)f(held)h(\002x)o(ed,)g(then)f(as)h
Fl(n)f Fm(increases)h(the)f(local)2040 106 y(storage)g(method)h(incurs)
e(the)h(greatest)g(total)f(pack)o(et)h(count.)32 b(Second,)22
b(e)o(x-)2040 193 y(ternal)d(storage)g(al)o(w)o(ays)g(incurs)g(a)g
(lesser)g(total)f(message)i(count)f(than)g(data-)2040
297 y(centric)29 b(storage,)j(b)o(ut)c(the)h(ratio)g(1)14
b Ff(+)3079 256 y Fc(Q)p Fd(+)p Fc(D)3208 265 y Fa(q)p
3079 280 154 3 v 3092 323 a Fc(D)3133 332 y Fa(t)s(o)o(t)s(al)3272
297 y Fm(is)28 b(unlik)o(ely)i(to)f(be)g(great)g(if)2040
384 y(there)c(are)g(man)o(y)g(e)n(v)o(ents)h(detected)f(\(and,)i(if)d
(there)h(is)f(at)h(least)f(one)i(e)n(v)o(ent)2040 471
y(detected)18 b(of)g(each)g(type,)g(this)f(ratio)g(is)g(bounded)j(by)e
(3\).)k(Third,)17 b(if)g Fl(D)3840 482 y Fc(q)3889 471
y Fj(\035)e Fl(Q)2040 558 y Fm(and)23 b(e)n(v)o(ents)f(are)g
(summarized,)i(then)e(data-centric)h(storage)f(has)h(the)f(least)2040
646 y(load)d(\(of)g(all)g(three)g(methods\))g(on)h(the)f(access)g
(path.)24 b(F)o(ourth,)18 b(if)h(e)n(v)o(ents)g(are)2040
733 y(listed)k(and)h Fl(D)2409 747 y Fc(t)t(o)o(t)t(al)2548
733 y Fj(\035)18 b Fl(D)2695 744 y Fc(q)2751 733 y Fm(then)24
b(data-centric)g(storage)g(and)g(local)f(storage)2040
820 y(ha)o(v)o(e)c(signi\002cantly)g(lesser)g(access)h(loads)f(than)g
(e)o(xternal)h(storage.)2040 994 y(These)15 b(observ)n(ations)h(in)e
(turn)h(suggest)g(that)f(data-centric)h(storage)g(is)f(prefer)o(-)2040
1082 y(able)26 b(in)f(cases)h(where)g(\(a\))f(the)g(sensornet)i(is)e
(lar)o(ge,)h(\(b\))g(there)f(are)h(man)o(y)2040 1169
y(detected)18 b(e)n(v)o(ents)g(and)g(not)f(all)g(e)n(v)o(ent)g(types)h
(are)f(queried,)h(so)f(that)g Fl(D)3823 1183 y Fc(t)t(o)o(t)t(al)3958
1169 y Fj(\035)2040 1256 y Fm(max)q Ff([)p Fl(D)2244
1267 y Fc(q)2277 1256 y Fg(;)8 b Fl(Q)p Ff(])p Fm(.)47
b(This)27 b(performance)i(adv)n(antage)g(increases)e(further)h(when)
2040 1343 y(summaries)i(are)g(used.)56 b(Ho)n(we)n(v)o(er)m(,)33
b(if)c(the)h(number)h(of)f(e)n(v)o(ents)g(is)g(lar)o(ge)2040
1430 y(compared)22 b(to)e(the)h(system)f(size,)h Fl(D)2981
1444 y Fc(t)t(o)o(t)t(al)3118 1430 y Fg(>)c Fl(Q)3247
1377 y Fj(p)p 3309 1377 38 3 v 53 x Fl(n)q Fm(,)j(and)h(e)n(v)o(ent)g
(lists)f(\(rather)2040 1517 y(than)f(summaries\))h(are)f(used,)g(then)g
(local)g(storage)h(may)f(be)g(preferable.)2040 1711 y
Fn(4.3)99 b(Additional)25 b(Dissemination)f(Methods)2040
1802 y Fm(The)19 b(three)g(canonical)i(methods)f(described)g(in)f(the)g
(pre)n(vious)h(section)g(cer)o(-)2040 1890 y(tainly)f(do)h(not)f(e)o
(xhaust)h(the)f(design)h(space;)f(combinations)i(of)e(them)g(yield)2040
1977 y(hybrid)h(methods)g(specialized)g(for)f(particular)g(needs.)25
b(Examples)19 b(of)h(such)2040 2064 y(combinations)g(include:)2040
2258 y Fh(Using)i(Data\255Centric)g(Stor)o(a)o(g)o(e)f(for)h(Location)g
(Guidance:)2040 2349 y Fm(F)o(or)f(certain)h(applications,)h(one)g
(might)f(combine)h(LS)d(and)j(DCS)e(by)h(stor)o(-)2040
2436 y(ing)i(detailed)g(e)n(v)o(ent)h(information)f(locally)g(and)g
(using)h(DCS)e(to)h(inform)f(a)2040 2523 y(querier)d(of)g(an)g(e)n(v)o
(ent')l(s)g(location)h(so)f(that)f(subsequent)j(queries)e(can)h(be)f
(di-)2040 2610 y(rected)f(to)g(the)g(proper)h(local)f(store.)2040
2804 y Fh(Using)j(Data\255Centric)g(Stor)o(a)o(g)o(e)f(for)h(Conte)n
(xt:)2040 2895 y Fm(In)h(the)g(course)g(of)g(processing)h(local)f
(data,)h(nodes)g(may)f(\002nd)g(it)f(useful)h(to)2040
2983 y(ha)o(v)o(e)30 b(some)g(conte)o(xt)g(about)g(global)g
(parameters.)56 b(F)o(or)29 b(instance,)j(data-)2040
3070 y(centric)21 b(storage)h(could)f(gi)n(v)o(e)h(nodes)g(access)f(to)
g(the)g(number)h(of)f(other)g(an-)2040 3157 y(imals)i(sighted)g(when)g
(a)g(node)h(is)e(trying)h(to)g(determine)g(if)f(a)h(migration)g(is)2040
3244 y(underw)o(ay)-5 b(.)2040 3438 y Fh(Geo)o(gr)o(aphically)20
b(T)-8 b(ar)m(g)o(eted)20 b(Queries:)2040 3529 y Fm(The)25
b(canonical)i(methods)f(are)g(designed)g(for)g(cases)f(where)h(one)g
(doesn')o(t)2040 3616 y Fl(a)31 b(priori)g Fm(kno)n(w)g(the)g(e)n(v)o
(ent)g(location.)59 b(If)30 b(one)h(already)g(kno)n(ws)h(the)f(lo-)2040
3703 y(cation)26 b(of)h(the)f(e)n(v)o(ent)g(through)h(out-of-band)h
(techniques,)h(then)d(one)h(can)2040 3791 y(direct)i(queries)h(to)f
(that)h(location)f(using)h(geographic)h(routing)f(methods)2040
3878 y(\(see)20 b([23]\).)27 b(This)20 b(LS)g(v)n(ariant)g(stores)g
(data)h(locally)-5 b(,)20 b(and)h(queries)g(are)f(sent)2040
3965 y(\(at)15 b(cost)h Fl(O)p Ff(\()2353 3911 y Fj(p)p
2415 3911 V 54 x Fl(n)p Ff(\))p Fm(\))f(to)h(the)f(rele)n(v)n(ant)h
(locations)g(to)g(retrie)n(v)o(e)f(the)g(desired)h(data.)2040
4052 y(It)i(a)o(v)o(oids)g(the)g(cost)h(of)f(\003ooding)h(in)g(the)f
(canonical)h(LS)f(approach,)h(and)g(the)2040 4139 y(cost)g(of)g
(storing)g(each)h(e)n(v)o(ent)f(in)g(the)g(canonical)h(DCS)e(approach.)
2040 4333 y Fn(5.)99 b(THE)26 b(GEOGRAPHIC)d(HASH)h(T)-9
b(ABLE)2040 4424 y Fm(W)j(e)26 b(no)n(w)i(of)n(fer)f(a)g(brief)f(o)o(v)
o(ervie)n(w)i(of)f(our)g(design)g(for)g(the)g(Geographic)2040
4511 y(Hash)17 b(T)-6 b(able)16 b(\(GHT\))f(system)h(that)g(supports)i
(the)e(data-centric)g(storage)h(ab-)2040 4599 y(straction;)k(the)g
(detailed)f(design)i(and)f(e)n(v)n(aluation)h(of)e(GHT)g(are)g
(described)2040 4686 y(in)f([19].)2040 4860 y(GHT)h(pro)o(vides)i(a)e
Fl(\(k)o(e)n(y)l(,value\))p Fm(-based)i(associati)n(v)o(e)g(memory)-5
b(.)29 b(Ev)o(ents)20 b(are)2040 4947 y(named)h(with)f(k)o(e)o(ys.)28
b(Both)21 b(the)f(storage)h(of)f(an)h(e)n(v)o(ent)g(and)f(its)g(retrie)
n(v)n(al)g(are)2040 5034 y(performed)g(using)h(these)e(k)o(e)o(ys.)26
b(GHT)18 b(is)h(naming-agnostic;)j(an)o(y)d(naming)2040
5122 y(scheme)j(that)f(distinguishes)i(the)e(requisite)g(e)n(v)o(ents)h
(suf)n(\002ces.)31 b(The)21 b(opera-)2040 5209 y(tions)e(GHT)f
(supports)i(are:)p Black 2040 5326 a Fe(Put\()p Fl(k)q
Fg(;)8 b Fl(v)p Fe(\))p Black 37 w Fm(stores)26 b Fl(v)g
Fm(\(the)g(observ)o(ed)i(data\))e(according)h(to)f(the)h(k)o(e)o(y)g
Fl(k)q Fm(,)g(the)2227 5413 y(name)19 b(of)g(the)g(data.)p
Black Black eop
%%Page: 5 5
5 4 bop Black Black Black -152 -69 a Fe(Get\()p Fl(k)q
Fe(\))p Black 38 w Fm(retrie)n(v)o(es)19 b(whate)n(v)o(er)h(v)n(alue)f
(is)g(stored)g(associated)h(with)e(k)o(e)o(y)i Fl(k)q
Fm(.)-152 84 y(In)33 b(terms)f(of)g(functionality)h(\()p
Fl(i.e)o(.,)i Fm(the)d(abo)o(v)o(e)h(interf)o(ace\),)j(GHT)c(is)g(in-)
-152 171 y(spired)18 b(by)f(the)g(ne)n(w)h(generation)g(of)f
(Internet-scale)g(Distrib)o(uted)g(Hash)g(T)-6 b(a-)-152
258 y(ble)24 b(\(DHT\))f(systems)h(such)g(as)g(P)o(astry)-5
b(,)24 b(CAN,)f(Chord,)i(and)f(T)-6 b(apestry)24 b([6,)-152
346 y(18,)c(21,)g(24].)25 b(In)20 b(these)g(systems,)g(nodes)g(are)g
(assigned)h(virtual)e(identi\002ers)-152 433 y(and)j(a)f(data)h
(object')l(s)f(k)o(e)o(y)h(is)f(also)g(hashed)i(to)e(a)g(virtual)g
(identi\002er)l(.)29 b(Gi)n(v)o(en)-152 520 y(a)g(particular)f(k)o(e)o
(y)-5 b(,)31 b(a)d(name-based)i(routing)f(algorithm)g(is)f(then)h(used)
g(to)-152 607 y(locate)f(the)g(node)h(with)f(virtual)f(identi\002er)h
(closest)g(to)f(the)h(k)o(e)o(y')l(s)h(virtual)-152 694
y(identi\002er)l(.)23 b(This)18 b(node)i(then)g(serv)o(es)f(as)g(the)g
(storage)g(node)h(for)f(that)g(k)o(e)o(y)-5 b(.)-152
869 y(Although)16 b(GHT)e(pro)o(vides)h(functionality)g(equi)n(v)n
(alent)h(to)e(that)g(of)h(the)f(DHTs,)-152 956 y(it)20
b(w)o(ould)i(be)f(inappropriate)h(to)e(adopt)i(the)e(DHT)g(routing)i
(algorithms)f(for)-152 1043 y(use)k(on)g(sensornets.)41
b(These)24 b(algorithms)h(typically)g(interconnect)h(nodes)-152
1130 y(in)i(a)g(w)o(ay)g(determined)h(by)f(their)g(logical)g
(identi\002ers)g(in)f(the)h(DHT)f(sys-)-152 1217 y(tem,)19
b(which)g(are)g(lar)o(gely)g(independent)i(of)e(their)f(proximity)i(in)
e(the)h(physi-)-152 1305 y(cal)i(netw)o(ork)h(topology)-5
b(.)30 b(On)21 b(the)f(Internet)h(the)g(IP)f(routing)h(system)g(of)n
(fers)-152 1392 y(connecti)n(vity)f(between)g(nodes)f(that)g(are)f(not)
h(topologically)h(close.)j(But)c(in)-152 1479 y(the)e(ener)o
(gy-constrained)h(sensornet)g(en)m(vironment,)g(maintaining)f(routing)
-152 1566 y(among)j(all)f(pairs)g(of)g(nodes)h(is)e(infeasibly)i(e)o
(xpensi)n(v)o(e.)-152 1740 y(Instead,)29 b(the)e(core)g(idea)h(in)e
(GHT)g(is)h(to)g(use)g(the)g(true)g(geographic)h(\()p
Fl(i.e)o(.,)-152 1828 y Fm(latitude-longitude\))e(space)f(occupied)i
(by)e(the)f(sensornet)i(as)f(the)f(logical)-152 1915
y(identi\002er)15 b(space)i(and)f(use)g(geographic)h(routing)f(as)g
(the)f(underlying)i(name-)-152 2002 y(based)30 b(routing)f(technique.)
53 b(Thus,)31 b(a)e(k)o(e)o(y)g(is)f(hashed)i(to)e(a)h(geographic)-152
2089 y(position)d(and)g(geographic)h(routing)f(is)f(used)g(to)h(locate)
f(the)g(node)h(physi-)-152 2176 y(cally)g(closest)f(to)g(this)h
(position.)43 b(This)25 b(approach)h(allo)n(ws)g(us)f(to)h(achie)n(v)o
(e)-152 2263 y(the)c(required)g(hash-table-lik)o(e)g(functionality)g
(while)f(w)o(orking)h(with)f(only)-152 2351 y(the)e(true)g(physical)h
(connecti)n(vity)g(between)f(nodes.)-152 2525 y(GHT)k(uses)h(GPSR)e
([11],)i(a)g(geographic)h(routing)f(system)g(for)f(multi-hop)-152
2612 y(wireless)g(netw)o(orks.)36 b(Under)23 b(GPSR,)f(a)h(sender)g
(that)g(wishes)g(to)g(transmit)-152 2699 y(pack)o(ets)31
b(to)f(a)g(destination)h(node)f(marks)h(these)f(pack)o(ets)h(with)e
(the)h(des-)-152 2787 y(tination')l(s)d Fl(position)p
Fm(.)412 2759 y Fo(4)491 2787 y Fm(All)f(nodes)h(kno)n(w)g(their)f(o)n
(wn)h(positions)g(and)h(the)-152 2874 y(positions)d(of)f(nodes)h(a)e
(single)h(hop)h(a)o(w)o(ay)f(from)g(them.)38 b(Using)24
b(only)h(this)-152 2961 y(local)18 b(kno)n(wledge,)h(GPSR)e(can)h
(route)g(a)f(pack)o(et)i(to)e(an)o(y)i(destination)f(node.)-152
3135 y(GHT)-6 b(,)17 b(ho)n(we)n(v)o(er)m(,)i(uses)f(geographic)i
(routing)e(in)f(a)h(slightly)g(dif)n(ferent)f(man-)-152
3222 y(ner)l(.)49 b(Under)27 b(GHT)-6 b(,)27 b(unlik)o(e)h(under)g
(GPSR,)e(the)h(originator)h(of)f(a)h(pack)o(et)-152 3310
y(does)20 b Fl(not)e Fm(kno)n(w)i(the)e(node)i(that)e(is)h(the)f(e)n(v)
o(entual)i(destination)f(of)f(a)h(pack)o(et.)-152 3397
y(The)31 b(originator)f(of)h(a)f(GHT)g Fe(Put\(\))f Fm(or)h
Fe(Get\(\))g Fm(for)g(a)h(k)o(e)o(y)g Fl(k)g Fm(hashes)h(the)-152
3484 y(name)27 b Fl(k)h Fm(into)e(geographic)i(coordinates)g(that)e
(act)g(as)g(the)h(destination)g(of)-152 3571 y(the)c(pack)o(et)g(for)f
(that)g(operation.)34 b(The)22 b(hash)h(function)g(is)e(ignorant)i(of)g
(the)-152 3658 y(placement)28 b(of)e(indi)n(vidual)h(nodes)h(in)e(the)g
(topology;)32 b(it)25 b(merely)i(spreads)-152 3745 y(the)20
b(dif)n(ferent)f(k)o(e)o(y)h(names)g(e)n(v)o(enly)g(across)f(the)h
(geographic)h(re)o(gion)e(where)-152 3833 y(the)28 b(netw)o(ork)g(is)f
(deplo)o(yed.)51 b(Thus,)30 b(it)d(is)g(quite)g(lik)o(ely)h(that)f
(there)h(is)f(no)-152 3920 y(node)22 b(at)f(the)g(precise)g
(coordinates)h(the)f(hash)h(function)g(produces.)30 b(F)o(ortu-)-152
4007 y(nately)-5 b(,)20 b(the)f(manner)h(in)f(which)g(GPSR)f(treats)h
(such)g(a)g(pack)o(et)h(is)f(precisely)-152 4094 y(the)24
b(beha)o(vior)h(desired)g(by)f(GHT)-7 b(\227GPSR)22 b(forw)o(ards)j
(the)f(pack)o(et)h(until)e(it)-152 4181 y(reaches)i(the)f(node)i
(geographically)g(closest)e(to)g(the)g(destination)h(coordi-)-152
4268 y(nates.)39 b(Under)25 b(GHT)-6 b(,)24 b(this)f(closest)i(node)g
(consumes)h(and)e(processes)i(the)-152 4356 y(pack)o(et.)e(Note)17
b(that)h(GHT)e(does)j(not)e(change)i(the)f(underlying)h(GPSR)d(rout-)
-152 4443 y(ing)24 b(algorithm;)j(we)c(merely)h(le)n(v)o(erage)h(a)f
(pre)n(viously)h(une)o(xploited)g(char)o(-)-152 4530
y(acteristic)c(of)g(GPSR)e(that)i(allo)n(ws)g(all)f(pack)o(ets)i
(destined)g(for)e(an)i(arbitrary)-152 4617 y(location)e(to)f(be)g
(routed)g(consistently)h(to)f(the)g(node)h(closest)f(to)g(it.)-152
4791 y(The)f(abo)o(v)o(e)i(approach)f(is)f(suf)n(\002cient)g(to)h
(support)g(our)f(GHT)g(interf)o(ace)g(pro-)-152 4879
y(vided)f(sensornet)g(nodes)g(are)f(completely)h(stationary)g(and)g
(reliable.)22 b(Ho)n(w-)-152 4966 y(e)n(v)o(er)m(,)17
b(as)f(with)g(DHTs,)g(much)h(of)f(the)h(subtlety)f(in)g(the)h(GHT)e
(system)i(design)-152 5053 y(arises)g(speci\002cally)g(to)f(ensure)i
(rob)o(ustness)f(and)h(scalability)e(in)h(the)f(f)o(ace)i(of)-152
5140 y(the)26 b(man)o(y)h(sorts)f(of)g(f)o(ailures)g(possible)g(in)g(a)
g(distrib)o(uted)g(system.)44 b(GHT)p Black -152 5215
797 4 v -148 5276 a Fo(4)-114 5303 y Fm(A)25 b(sender)h(maps)h(the)e
(destination')l(s)h(identi\002er)g(to)f(its)g(current)h(position)-152
5378 y(using)20 b(a)f(location)g(database,)h(such)f(as)g(GLS)f([13].)p
Black 2040 -69 a(uses)i(a)f(no)o(v)o(el)g Fl(perimeter)h(r)m(efr)m(esh)
g(pr)m(otocol)g Fm(to)f(pro)o(vide)h(both)g(persistence)2040
19 y(and)h(consistenc)o(y)h(when)f(nodes)g(f)o(ail)f(or)h(mo)o(v)o(e.)
28 b(This)20 b(protocol)h(replicates)2040 106 y(stored)16
b(data)f(for)h(k)o(e)o(y)g Fl(k)h Fm(at)e(nodes)h(around)h(the)e
(location)h(to)f(which)h Fl(k)h Fm(hashes,)2040 193 y(and)23
b(ensures)g(that)g(the)f(appropriate)i(storage)f(node)g(for)f
Fl(k)i Fm(is)e(chosen)i(con-)2040 280 y(sistently)-5
b(.)2040 454 y(By)15 b(hashing)g(k)o(e)o(ys,)h(GHT)e(spreads)h(storage)
g(and)g(communication)h(load)f(be-)2040 542 y(tween)20
b(dif)n(ferent)g(k)o(e)o(ys)h(e)n(v)o(enly)g(throughout)h(the)e
(sensornet.)27 b(When)20 b(man)o(y)2040 629 y(e)n(v)o(ents)31
b(with)g(the)f(same)h(k)o(e)o(y)g(are)g(stored,)j(GHT)29
b(a)o(v)o(oids)i(concentrating)2040 716 y(communication)22
b(and)g(storage)f(at)f(their)h(shared)g(home)h(node)f(by)g(emplo)o(y-)
2040 803 y(ing)j Fl(structur)m(ed)i(r)m(eplication)p
Fm(,)g(whereby)f(e)n(v)o(ents)g(with)e(the)i(same)f(k)o(e)o(y)h(can)
2040 890 y(be)19 b(di)n(vided)h(among)g(multiple)f(mirrors.)2040
1065 y(GHT)h(fundamentally)i(requires)f(that)f(a)h(node)g(kno)n(w)h
(its)e(o)n(wn)h(geographic)2040 1152 y(position.)j(While)18
b(this)g(assumption)i(seems)g(reasonable)g(for)e(most)h(sensor)o(-)2040
1239 y(nets,)g(an)g(open)g(question)h(is)e(ho)n(w)h(\(if)f(at)h(all\))f
(one)h(might)g(achie)n(v)o(e)h(DCS)d(us-)2040 1326 y(ing)k(only)h
(approximate)g(geographic)h(information,)e(or)g(better)g(still,)f
(with-)2040 1413 y(out)k(requiring)g(an)o(y)h(position)f(information)g
(at)f(all.)37 b(This)23 b(question)i(is)e(the)2040 1500
y(subject)c(of)g(our)h(continuing)g(research.)2040 1689
y Fn(6.)99 b(CONCLUSION)2040 1780 y Fm(W)-6 b(e)24 b(belie)n(v)o(e)g
(future)h(sensornets)g(will)e(incorporate)i(man)o(y)g(dif)n(ferent)f
(data)2040 1867 y(dissemination)15 b(mechanisms)h(and)f(users)g(will)e
(choose)j(among)g(them)e(based)2040 1954 y(on)27 b(the)f(particular)g
(circumstances.)46 b(In)26 b(this)g(paper)g(we)g(proposed)i(data-)2040
2041 y(centric)f(storage)g(as)g(a)g(no)o(v)o(el)g(approach)i(to)e
(wide-area)g(data)g(dissemina-)2040 2129 y(tion.)33 b(W)-6
b(e)21 b(identi\002ed)i(the)f(settings)g(where)g(data-centric)h
(storage)g(may)f(be)2040 2216 y(the)c(preferred)h(method)f(because)i
(of)d(its)h(ener)o(gy)g(ef)n(\002cienc)o(y)-5 b(.)24
b(W)-6 b(e)17 b(pro)o(vided)2040 2303 y(a)28 b(frame)n(w)o(ork)i(for)e
(reasoning)h(about)h(data)e(dissemination)h(that)g(di)n(vides)2040
2390 y(the)22 b(design)i(space)f(into)f(three)g(canonical)i
(approaches,)g(and)f(ga)o(v)o(e)g(a)f(sim-)2040 2477
y(ple)d(model)h(for)e(characterizing)i(their)f(respecti)n(v)o(e)g(ener)
o(gy)h(costs.)2040 2652 y(W)-6 b(e)14 b(brie\003y)g(described)i(the)e
(design)i(of)e(GHT)g(and)h(our)g(approach)h(to)e(achie)n(v-)2040
2739 y(ing)24 b(data-centric)f(storage,)i(b)o(ut)e(there)g(are)g
(doubtless)h(other)g(approaches.)2040 2826 y(In)15 b(particular)m(,)h
(the)f(GRID)f(location)h(system)h(\(GLS\))d([13])i(can)h(be)f(e)o
(xtended)2040 2913 y(to)29 b(pro)o(vide)h(a)e(similar)h(capability)-5
b(.)53 b(GLS)28 b(constructs)i(and)f(maintains)g(a)2040
3000 y(distrib)o(uted)22 b(database)i(that)e(maps)g(node)i(addresses)f
(to)f(geographic)i(posi-)2040 3087 y(tions.)i(While)19
b(the)h(goal)h(in)e(GLS)g(is)h(to)f(pro)o(vide)i(a)f(node)h(location)f
(service,)2040 3175 y(for)k(our)g(sensornet)h(application,)h(this)d
(database)i(is)f(merely)g(an)g(unneces-)2040 3262 y(sary)18
b(le)n(v)o(el)h(of)f(indirection;)g(we)g(map)h(e)n(v)o(ent)f(names)h
(directly)f(to)g(locations.)2040 3349 y(The)26 b(SCOUT)e([12])i
(location)g(tracking)g(system)g(might)g(also)f(be)h(used)g(in)2040
3436 y(a)21 b(similar)g(manner)l(.)30 b(While)21 b(SCOUT)f(uses)i
(hierarchical)f(addressing)i(and)2040 3523 y(routing)j(based)g(on)g
(landmark)h(routing,)g(GHT)e(uses)h(GPSR,)d(a)j(\003at)e(rout-)2040
3610 y(ing)g(algorithm)f(wherein)h(nodes)g(are)g(addressed)g(with)f
(geographic)i(coor)o(-)2040 3698 y(dinates.)2040 3872
y(A)19 b(Linux)g(v)o(ersion)g(of)g(the)f(GHT)h(design)g(for)g(DCS)f(is)
g(under)i(de)n(v)o(elopment)2040 3959 y(for)c(iP)-7 b(A)l(Qs)15
b(communicating)i(with)e(both)i(802.11)g(radios)f(and)g(mote)g(radios.)
2040 4046 y(In)25 b(our)f(initial)g(applications)i(of)e(the)h(system,)h
(we)e(will)f(e)o(xperiment)j(with)2040 4133 y(e)n(v)o(ent)d(naming)g
(schemes)h(to)n(w)o(ard)f(the)f(goal)h(of)g(realizing)f(the)h
(bene\002ts)f(of)2040 4221 y(DCS)c(fully)-5 b(.)2040
4409 y Fn(7.)99 b(REFERENCES)p Black 2077 4496 a Fm([1])p
Black 38 w(W)-7 b(.)18 b(Adjie-W)m(inoto,)g(E.)g(Schw)o(artz,)h(and)h
(H.)e(Balakrishnan,)i(The)2202 4583 y(Design)f(and)h(Implementation)g
(of)f(an)g(Intentional)g(Naming)2202 4670 y(System,)f(In)h
Fl(Pr)m(oceedings)h(of)f(the)g(Symposium)h(on)f(Oper)o(ating)2202
4757 y(Systems)g(Principles)p Fm(,)g(pp.)g(186\226201,)i(\(Charleston,)
e(South)2202 4845 y(Carolina,)g(December)g(1999\).)p
Black 2077 4980 a([2])p Black 38 w(P)-8 b(.)18 b(Bonnet,)h(J.)f(Gehrk)o
(e,)i(and)f(P)-8 b(.)18 b(Seshadri,)h(Querying)g(the)g(Physical)2202
5067 y(W)-6 b(orld,)18 b(IEEE)g(Personal)h(Communications)h(Magazine,)g
(Special)2202 5155 y(Issue)f(on)h(Netw)o(orking)f(the)g(Physical)g(W)-6
b(orld,)18 b(\(October)h(2000\).)p Black 2077 5290 a([3])p
Black 38 w(N.)f(Bulusu,)h(J.)g(Heidemann,)h(and)f(D.)f(Estrin,)g
(GPS-Less)g(Lo)n(w)h(Cost)2202 5378 y(Outdoor)g(Localization)g(for)g(V)
-8 b(ery)18 b(Small)g(De)n(vices,)h(IEEE)e(Personal)p
Black Black eop
%%Page: 6 6
6 5 bop Black Black 10 -69 a Fm(Communications)20 b(Magazine,)g
(Special)f(Issue)g(on)g(Smart)g(Spaces)10 19 y(and)h(En)m(vironments,)f
(\(October)h(2000\).)p Black -114 175 a([4])p Black 37
w(A.)e(Cerpa,)h(J.)g(Elson,)f(D.)h(Estrin,)e(L.)h(Girod,)h(M.)g
(Hamilton,)g(and)g(J.)10 262 y(Zhao,)g(Habitat)g(monitoring:)24
b(Application)19 b(Dri)n(v)o(er)g(for)g(W)m(ireless)10
349 y(Communications)h(T)-5 b(echnology,)21 b(In)d(A)m(CM)h(SIGCOMM)10
436 y(W)-6 b(orkshop)20 b(on)g(Data)e(Communications)j(in)d(Latin)h
(America)g(and)10 523 y(the)g(Caribbean,)h(\(Costa)e(Rica,)h(April)f
(2001\).)p Black -114 679 a([5])p Black 37 w(Defense)i(Adv)n(anced)g
(Research)g(Projects)e(Agenc)o(y)-5 b(,)20 b(Sensor)10
766 y(Information)g(T)-5 b(echnology,)20 b Fk(http://www.darpa.mil/)10
854 y(ito/research/sensit)p Fm(.)p Black -114 1010 a([6])p
Black 37 w(A.)e(Ro)n(wstron)i(and)f(P)-8 b(.)18 b(Druschel,)h(P)o
(astry:)k(Scalable,)18 b(Distrib)o(uted)10 1097 y(Object)h(Location)g
(and)h(Routing)f(for)g(Lar)o(ge-scale)g(Peer)o(-to-peer)10
1184 y(Systems,)g(In)g Fl(Pr)m(oceedings)g(of)g(the)g(18th)h(IFIP/A)n
(CM)d(International)10 1271 y(Confer)m(ence)k(on)e(Distrib)o(uted)g
(Systems)g(Platforms)f(\(Middle)o(war)m(e\))p Fm(,)10
1358 y(\(Heidelber)o(g,)h(German)o(y)-5 b(,)19 b(No)o(v)o(ember)h
(2001\).)p Black -114 1514 a([7])p Black 37 w(L.)e(Girod)h(and)h(D.)e
(Estrin,)g(Rob)o(ust)h(Range)g(Estimation)g(Using)10
1601 y(Acoustic)g(and)h(Multimodal)g(Sensing,)f(In)g
Fl(Pr)m(oceedings)g(of)g(the)10 1689 y(IEEE/RSJ)f(Confer)m(ence)i(on)f
(Intellig)o(ent)h(Robots)f(and)h(Systems)p Fm(,)10 1776
y(\(Maui,)f(Ha)o(w)o(aii,)f(October)i(2001\).)p Black
-114 1932 a([8])p Black 37 w(R.)e(Go)o(vindan,)i(J.)f(Hellerstein,)f(W)
-7 b(.)18 b(Hong,)h(S.)f(Madden,)10 2019 y(M.)h(Franklin)g(and)g(S.)f
(Shenk)o(er)m(,)i(The)f(Sensor)g(Netw)o(ork)g(as)g(a)10
2106 y(Database,)g(preprint,)g(\(2002\).)p Black -114
2262 a([9])p Black 37 w(J.)g(Heidemann,)g(F)-6 b(.)18
b(Silv)n(a,)g(C.)h(Intanagonwiw)o(at,)h(R.)e(Go)o(vindan,)10
2349 y(D.)g(Estrin,)g(and)i(D.)e(Ganesan,)i(Building)f(Ef)n(\002cient)f
(W)m(ireless)10 2437 y(Sensor)h(Netw)o(orks)h(with)e(Lo)n(w-le)n(v)o
(el)h(Naming,)g(In)g Fl(Pr)m(oceedings)h(of)10 2524 y(the)f(Symposium)h
(on)g(Oper)o(ating)f(Systems)h(Principles)p Fm(,)e(pp.)10
2611 y(146\226159,)j(\(Alberta,)d(Canada,)i(October)f(2001\).)p
Black -152 2767 a([10])p Black 38 w(C.)f(Intanagonwiw)o(at,)i(R.)f(Go)o
(vindan,)h(and)f(D.)f(Estrin,)g(Directed)10 2854 y(Dif)n(fusion:)24
b(A)18 b(Scalable)h(and)h(Rob)o(ust)f(Communication)h(P)o(aradigm)10
2941 y(for)f(Sensor)g(Netw)o(orks,)g(In)g Fl(Pr)m(oceedings)h(of)f(the)
g(Sixth)g(Annual)10 3028 y(A)n(CM/IEEE)e(International)j(Confer)m(ence)
g(on)g(Mobile)f(Computing)10 3116 y(and)h(Networking)f(\(Mobicom\))p
Fm(,)h(\(Boston,)f(Massachusetts,)h(August)10 3203 y(2000\).)p
Black -152 3359 a([11])p Black 38 w(B.)e(Karp)h(and)h(H.T)-6
b(.)18 b(K)o(ung,)h(Greedy)h(Perimeter)e(Stateless)g(Routing,)10
3446 y(In)h Fl(Pr)m(oceedings)h(of)f(the)g(Sixth)g(Annual)g(A)n
(CM/IEEE)e(International)10 3533 y(Confer)m(ence)k(on)e(Mobile)g
(Computing)h(and)g(Networking)10 3620 y(\(Mobicom\))p
Fm(,)f(\(Boston,)g(Massachusetts,)i(August)e(2000\).)p
Black -152 3776 a([12])p Black 38 w(S.)f(K)o(umar)m(,)h(C.)f
(Alaettinoglu,)h(and)h(D.)e(Estrin,)g(SCalable)10 3863
y(Object-tracking)i(through)g(Unattended)g(T)-5 b(echniques)20
b(\(SCOUT\),)10 3951 y(In)f Fl(Pr)m(oceedings)h(of)f(the)g(8th)g
(International)h(Confer)m(ence)g(on)10 4038 y(Network)f(Pr)m
(otocols\(ICNP\))p Fm(,)f(\(Osaka,)h(Japan,)g(No)o(v)o(ember)h(2000\).)
p Black -152 4194 a([13])p Black 38 w(J.)f(Li,)e(J.)i(Jannotti,)g(D.)f
(DeCouto,)h(D.)g(Kar)o(ger)m(,)f(and)i(R.)e(Morris,)h(A)10
4281 y(Scalable)g(Location)g(Service)g(for)g(Geographic)h(Ad-hoc)g
(Routing,)10 4368 y(In)f Fl(Pr)m(oceedings)h(of)f(the)g(Sixth)g(Annual)
g(A)n(CM/IEEE)e(International)10 4455 y(Confer)m(ence)k(on)e(Mobile)g
(Computing)h(and)g(Networking)10 4543 y(\(MobiCom)g(2000\))p
Fm(,)f(\(Boston,)g(Massachusetts,)h(August)g(2000\).)p
Black -152 4699 a([14])p Black 38 w(S.)e(Madden,)i(M.)f(Shah,)g(J.)f
(Hellerstein,)h(and)g(V)-10 b(.)19 b(Raman,)10 4786 y(Continuously)i
(Adapti)n(v)o(e)e(Continuous)h(Queries)g(o)o(v)o(er)f(Streams,)f(In)10
4873 y Fl(Pr)m(oceedings)i(of)f(the)g(A)n(CM)f(SIGMOD)h(Confer)m(ence)p
Fm(,)h(\(Madison,)10 4960 y(WI,)e(June)i(2002\).)p Black
-152 5116 a([15])p Black 38 w(G.)e(Pottie)h(and)g(W)-7
b(.)18 b(Kaiser)m(,)h(W)m(ireless)f(Inte)o(grated)h(Sensor)10
5203 y(Netw)o(orks)h(\(WINS\):)d(Principles)h(and)i(Approach,)10
5290 y Fl(Communications)g(of)f(the)g(A)n(CM)p Fm(,)f(V)-10
b(ol.)19 b(43,)g(Number)g(5,)g(pp.)g(51\22658,)10 5378
y(\(May)h(2000\).)p Black 2040 -69 a([16])p Black 38
w(N.)e(Priyantha,)h(A.)f(Chakraborty)-5 b(,)20 b(and)g(H.)e
(Balakrishnan,)i(The)2202 19 y(Crick)o(et)f(Location)g(Support)g
(System,)g(In)g Fl(Pr)m(oceedings)h(of)e(the)2202 106
y(Sixth)h(Annual)h(A)n(CM/IEEE)c(International)k(Confer)m(ence)h(on)
2202 193 y(Mobile)e(Computing)h(and)g(Networking)f(\(Mobicom\))p
Fm(,)h(\(Boston,)2202 280 y(Massachusetts,)g(August)f(2000\).)p
Black 2040 427 a([17])p Black 38 w(N.)f(Priyantha,)h(A.)f(Liu,)g(H.)h
(Balakrishnan,)g(and)h(S.)e(T)-5 b(eller)m(,)17 b(The)2202
514 y(Crick)o(et)i(Compass)h(for)e(Conte)o(xt-A)-7 b(w)o(are)20
b(Mobile)f(Applications,)h(In)2202 601 y Fl(Pr)m(oceedings)g(of)f(the)g
(Se)o(venth)h(Annual)f(A)n(CM/IEEE)e(International)2202
689 y(Confer)m(ence)j(on)g(Mobile)f(Computing)h(and)g(Networking)2202
776 y(\(Mobicom\))p Fm(,)f(\(Rome,)g(Italy)-5 b(,)18
b(July)i(2001\).)p Black 2040 923 a([18])p Black 38 w(S.)e(Ratnasamy)-5
b(,)19 b(P)-8 b(.)18 b(Francis,)g(M.)h(Handle)o(y)-5
b(,)20 b(R.)e(Karp,)h(and)2202 1010 y(S.)f(Shenk)o(er)m(,)h(A)g
(Scalable)g(Content-Addressable)h(Netw)o(ork,)f(In)2202
1097 y Fl(Pr)m(oceedings)h(of)f(the)g(A)n(CM)f(SIGCOMM)p
Fm(,)h(\(San)f(Die)o(go,)h(California,)2202 1184 y(August)g(2001\).)p
Black 2040 1331 a([19])p Black 38 w(S.)f(Ratnasamy)-5
b(,)19 b(B.)g(Karp,)f(L.)g(Y)l(in,)h(F)-6 b(.)18 b(Y)-8
b(u,)18 b(D.)g(Estrin,)2202 1418 y(R.)g(Go)o(vindan,)i(and)g(S.)e
(Shenk)o(er)m(,)h(GHT)l(:)f(A)h(Geographic)h(Hash)2202
1505 y(T)-6 b(able)19 b(for)g(Data-Centric)f(Storage)h(in)g
(SensorNets,)g(In)2202 1593 y Fl(Pr)m(oceedings)h(of)f(the)g(F)m(ir)o
(st)e(A)n(CM)i(International)h(W)-7 b(orkshop)20 b(on)2202
1680 y(W)l(ir)m(eless)f(Sensor)h(Networks)f(and)h(Applications)f(\(WSN)
n(A\))p Fm(,)2202 1767 y(\(Atlanta,)f(Geor)o(gia,)h(September)g
(2002\).)p Black 2040 1914 a([20])p Black 38 w(A.)f(Sa)o(vvides,)h
(C.-C.)f(Han,)g(and)i(M.)f(B.)f(Sri)n(v)n(asta)o(v)n(a,)g(Dynamic)2202
2001 y(Fine-Grain)g(Localization)i(in)e(Ad-Hoc)i(Netw)o(orks)f(of)g
(Sensors,)g(In)2202 2088 y Fl(Pr)m(oceedings)h(of)f(the)g(Se)o(venth)h
(Annual)f(A)n(CM/IEEE)e(International)2202 2175 y(Confer)m(ence)j(on)g
(Mobile)f(Computing)h(and)g(Networking)2202 2263 y(\(Mobicom\))p
Fm(,)f(\(Rome,)g(Italy)-5 b(,)18 b(July)i(2001\).)p Black
2040 2410 a([21])p Black 38 w(I.)e(Stoica,)g(R.)h(Morris,)f(D.)h(Kar)o
(ger)m(,)f(M.)h(F)-6 b(.)18 b(Kaashoek,)i(and)2202 2497
y(H.)e(Balakrishnan,)i(Chord:)k(A)18 b(Scalable)h(Peer)o(-to-peer)g
(Lookup)2202 2584 y(Service)g(for)f(Internet)h(Applications,)h(In)f
Fl(Pr)m(oceedings)g(of)g(the)g(A)n(CM)2202 2671 y(SIGCOMM)s
Fm(,)g(\(San)f(Die)o(go,)h(California,)g(August)g(2001\).)p
Black 2040 2818 a([22])p Black 38 w(K.)f(Y)-7 b(ao,)19
b(R.)f(Hudson,)i(C.)e(Reed,)h(D.)f(Chen,)h(and)h(F)-6
b(.)18 b(Lorenzelli,)2202 2905 y(Blind)h(Beamforming)g(on)h(a)f
(Randomly)h(Distrib)o(uted)e(Sensor)2202 2992 y(Array,)h(In)f
Fl(IEEE)g(J)n(ournal)i(on)g(Selected)f(Ar)m(eas)h(in)2202
3080 y(Communication)p Fm(,)g(V)-10 b(ol.)18 b(16,)i(Number)f(8,)g
(\(October)g(1998\).)p Black 2040 3226 a([23])p Black
38 w(Y)-10 b(.)19 b(Y)-8 b(u,)18 b(D.)g(Estrin,)g(and)i(R.)e(Go)o
(vindan,)i(Geographical)g(and)2202 3314 y(Ener)o(gy-A)-7
b(w)o(are)19 b(Routing:)24 b(A)19 b(Recursi)n(v)o(e)g(Data)g
(Dissemination)2202 3401 y(Protocol)g(for)g(W)m(ireless)f(Sensor)h
(Netw)o(orks,)g(UCLA)f(Computer)2202 3488 y(Science)h(Department)g(T)-5
b(echnical)19 b(Report,)g(UCLA-CSD)2202 3575 y(TR-01-0023,)h(\(May)f
(2001\).)p Black 2040 3722 a([24])p Black 38 w(B.)f(Y)-10
b(.)19 b(Zhao,)g(J.)f(K)o(ubiato)n(wicz,)h(and)h(A.)e(Joseph,)i(T)-6
b(apestry:)23 b(An)2202 3809 y(Infrastructure)c(for)g(F)o
(ault-tolerant)f(W)m(ide-area)h(Location)g(and)2202 3896
y(Routing,)g(T)-5 b(ech.)19 b(Rep.)f(UCB/CSD-01-1141,)h(Uni)n(v)o
(ersity)h(of)2202 3984 y(California)f(at)f(Berk)o(ele)o(y,)h(Computer)h
(Science)f(Department,)2202 4071 y(\(April)f(2001\).)p
Black 2040 4218 a([25])p Black 38 w(F)-6 b(.)18 b(Zhao,)h(J.)f(Shin,)h
(and)g(J.)g(Reich,)f(Information-Dri)n(v)o(en)i(Dynamic)2202
4305 y(Sensor)f(Collaboration)h(for)e(T)m(racking)i(Applications,)f(In)
g Fl(IEEE)2202 4392 y(Signal)h(Pr)m(ocessing)f(Ma)o(gazine)p
Fm(,)h(\(March)g(2002\).)p Black Black eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF