ࡱ> 02/bjbjUU :"??QQQQQeeee q e}}}}}}}} >Q}}}}}QQ}}}}}}Q}Q}}}}}}}e}}0}}}Q} }}}}}}}}}}}}}}}}}}}}}}}}} : Abstract A usual way to collect data in a Wireless Sensor Network (WSN) is by the support of a special agent, called data mule, that moves between sensor nodes and performs all communication between them. Using this problem as base, we tackled two versions of the problem: the first one where the mule has a global view, i.e., has the complete knowledge of all sensors and possible routes between them, and the second one where the mule must to decide its route based only on local informations obtained from the neighbors of the current visited sensor. The first version dealt with the Data Mule Scheduling Problem (DMSP). The DMSP is $\mathcal{NP}$-hard since it is a generalization of the Traveling Salesman Problem. In DMSP, in addition to the Data Mule Routing, it is necessary to plan the speed that this mule will use and also to schedule the attendance of the sensors in this route. Exact mathematical programming models and sequential heuristic algorithms for the problem are studied. Two different formulations using mixed integer linear programming and methods based on the GRASP and GVNS metaheuristics were proposed, in addition we generated instances for their validation. In the second version, the focus is on the construction of the route that the data mule must follow to serve all nodes in the WSN. This second version deals with the case when the data mule does not have a global view of the network, i.e., a prior knowledge of the network as a whole. Thus, at each node, the data mule makes a decision about the next node to be visited based only on a limited local knowledge of the WSN. Considering this realist scenario, two locality sensitive heuristics are proposed. These heuristics differ by the criterion of choice of the next visited node, while the first one uses a simpler greedy choice, the second one uses the geometric concept of convex hull. They were executed in instances of the literature and their results were compared both in terms of route length and in number of sent messages as well. For this version, some theoretical results, a mathematical formulation, and some lower bounds for the global view scenario are also proposed, in order to provide some parameters to evaluate the quality of the solutions given by the locality sensitive heuristics. Keywords: Wireless Sensor Networks; Data Mule Routing; Locality Sensitive Heuristics; Resumo Uma maneira usual de coletar dados em uma Rede de Sensores sem Fio (\textit{Wireless Sensor Networks} -- WSN) atrves de um agente especial, chamado mule de dados, que se move entre os ns sensores e realiza toda a comunicao entre eles. Ao se tratar da coleta de dados em uma WSN utilizando a mula de dados como meio de comunicao entre os sensores da rede, foram escolhidas duas abordagens para esse problema: a primeira onde a mula de dados tem uma viso global, ou seja, tem o conhecimento completo de todos os sensores e possveis rotas entre eles; e a segunda onde a mula deve decidir sua rota baseada apenas em informaes locais obtidas dos vizinhos do sensor que est sendo visitado em dado momento. A primeira abordagem tratou o Problema de Sequenciamento de Mula de Dados (Data Mule Scheduling Problem DMSP). O DMSP um problema classificado como NP-Difcil, uma vez que uma generalizao do Problema do Caixeiro Viajante (Traveling Salesman Problem). Ao tratarmos o DMSP, alm de realizar a definio da rota, necessrio planejar a velocidade que esta mula utilizar em seu trajeto e tambm sequenciar o atendimento dos sensores nesta rota. So estudados modelos de programao matemtica e algoritmos heursticos sequenciais para o problema. Foram propostas formulaes matemticas utilizando programao linear inteira mista e mtodos baseados nas metaheursticas GRASP e GVNS. Alm disso, instncias para a validao dos mtodos foram geradas. Na segunda abordagem, o foco est na construo da rota que a mula de dados deve seguir para atender todos os ns na WSN. Esta segunda verso aborda o caso em que a mula de dados no possui uma viso global da rede, ou seja, um conhecimento prvio da rede como um todo. Assim, em cada n, a mula de dados toma uma deciso sobre o prximo n a ser visitado com base apenas em um conhecimento local limitado do WSN. Considerando este cenrio realista, duas heursticas sensveis localidade so propostas. Estas heursticas diferem entre si pelo critrio de escolha do prximo n visitado, enquanto a primeira usa uma escolha gulosa mais simples, a segunda usa o conceito geomtrico de envoltria convexa. Eles foram testadas em instncias da literatura e seus resultados foram comparados tanto em termos de durao da rota quanto em nmero de mensagens enviadas. Para esta verso, alguns resultados tericos, uma formulao matemtica e alguns limites inferiores para o cenrio de viso global tambm so propostos, a fim de fornecer alguns parmetros para avaliar a qualidade das solues fornecidas pelas heursticas sensveis localidade. Palavras-chave: Rede de Sensores sem Fio; Roteamento de Mula de Dados; Heursticas Sensveis Localidade.   WX^au( hBr/6]hBr/ hBr/5\ hBr/^J  VWX_`$$a$$a$8P:pBr/. A!n"n#n$n% Dp^ 666666666vvvvvvvvv66666686666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtH\`\ Normal*$0CJKHOJPJQJ^J_HaJmHnHsHtHDA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List NN 0Ttulo1 $xCJOJPJQJ^JaJ8B8 0 Body Text d X/X 3b0Body Text Char$CJKHOJPJQJ^JaJnHtH$/"$ 0List<"2< 0Caption  $xx6],B, 0ndice $PK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] "Br/Kq3@@@UnknownG*Ax Times New Roman5Symbol3" ArialI xP!Liberation Serif?(SimSunG& xP!Liberation SansG.R<(Microsoft YaHeiACambria Math" JXgJXg  0 $PKq3!xxHelioHelioOh+'0t   0 < HT\dlHelioNormal_WordconvHelio2Microsoft Office Outlook@@Wj@Wj ՜.+,0 hp|    Title  !"#$%&()*+,-.1Root Entry Fp31TableWordDocument:"SummaryInformation(DocumentSummaryInformation8'CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q