C:/Users/Frederico/Documents/pesquisa/producao/congressos ... · A contribuiçao de nosso trabalho consiste na proposiç˜ ao de uma soluç˜ ao baseada em al-˜ goritmos geneticos

Redes de sensores sem fio modeladas como redes small world: umaheurısticabaseada em algoritmos geneticos

Andr e S. Ruela1, Andre L. L. Aquino 1,Frederico G. Guimaraes1, Raquel da S. Cabral2

1Departamento de Computacao – Universidade Federal de Ouro PretoCampus Morro do Cruzeiro, Bauxita, Ouro Preto, MG

2Departamento de Engenharia Eletrica – Universidade Federal de Minas GeraisAv. Antonio Carlos, 6627, Pampulha, Belo Horizonte, MG

{andrebardo,frederico.g.guimaraes,raquelcabral}@gmail.com

[email protected]

RESUMO

Este trabalho propoe um algoritmo genetico para modelar as redes de sensores sem fiocomo redessmall world. Nos desenvolvemos uma heurıstica baseada em algoritmos gene-ticos para encontrar a configuracao de rede, cuja estrutura de comunicacao possua carac-terısticas de uma redesmall world, em que o caminho medio mınimoe reduzido enquanto ocoeficiente de agrupamentoe mantido alto. O trabalho tem como ponto de partida um mod-elo matematico para o problema de alocacao dehubs, desenvolvido para determinar os nosque serao configurados comohubs. Deste modelo com algumas consideracoes adicionais,desenvolvemos a formulacao adotada no algoritmo genetico. Os resultados revelam quenossa metodologia permite a configuracao de redes com ate milhares de nos como umaredesmall worldminimizando o consumo de energia.

PALAVRAS CHAVE. Algoritmos Geneticos. RedesSmall World. Redes de SensoresSem Fio.Area de classificacao principal. OC - Otimizacao Combinatoria.

ABSTRACT

This work proposes a genetic algorithm to model the wireless sensor networks as a smallworld one. We develop an heuristic approach based on genetic algorithms for finding anetwork configuration such that its communication structure presents the characteristicsof a small world network, in which the minimal average path is reduced while the clustercoefficient is kept high. The work begins with the mathematical model of the hub locationproblem, developed to determine the nodes which will be configured as hubs. From thismodel and some additional considerations, we develop the formulation adopted within thegenetic algorithm. The results reveal that our methodology allows the configuration ofnetworks with more than a hundred nodes with characteristics of small world networks,thus minimizing the energy consumption.

KEYWORDS. Genetic algorithms. Small World Networks. Wireless Sensor Networks.Main area. OC - Combinatorial Optimization.

XLI SBPO 2009 - Pesquisa Operacional na Gestão do Conhecimento Pág. 2695

1. IntroducaoUma rede de sensores sem fio (RSSF) consiste de dispositivos distribuıdos e auto-

nomos, chamados nos sensores, que trabalham de forma cooperativa com o objetivo demonitorar condicoes fısicas e ambientais, como por exemplo, temperatura, som, luminosi-dade, vibracao, pressao, movimento e poluentes. Todos esses fatores fazem com que asRSSFs possam ser utilizadas numa variedade de aplicacoes como monitoramento de am-bientes, biotecnologia, controle e monitoramento industrial, saude publica, transporte econtrole medico (Akyildiz et al., 2002; Arampatzis et al., 2005).

Os nos sensores dessas redes possuem restricoes de energia, tempo de resposta e largurade banda, que devem ser consideradas na concepcao de algoritmos e protocolos eficientespara as RSSFs. Por exemplo, o tempo de resposta, quando muito alto, pode invalidar ainformacao que esta sendo propagada. Com isso, um fator importante no projeto dessasredese a diminuicao do tempo de resposta.

Os fenomenos monitorados pelas RSSFs sao reportados, por uma comunicacao semfio ad-hoc(Royer e Toh, 1999), para um elemento externoa rede, conhecido como nosink. Uma forma de propagacao “inocente”, conhecida como inundacao e ilustrada naFigura 1(a), considera apenas o meio de comunicacao real, onde o fenomeno monitoradoepropagado entre todos os sensores da rede ate alcancar o nosink(Maroti, 2004). Entretanto,essa estrategia demanda muita comunicacao gerando um grande consumo de energia e umtempo de resposta muito alto.

Sink

Sensor

Hub

(a) Inundacao.

Sink

Sensor

Hub

(b) Arvore.

Sink

Sensor

Hub

(c) Small world.

Figura 1: Propagacao do fenomeno em RSSFs.

Uma alternativa comuma propagacao “inocente”, conhecida como roteamento emarvore e ilustrada na Figura 1(b), permite a configuracao de todos os sensores para en-viar os dados apenas para um no sensor especıfico. A escolha do no para o qual os dadosserao enviados dependera da polıtica estabelecida pela aplicacao, no gerale utilizada apolıtica de menor caminho (Qiu et al., 2009). Note que, do ponto de vista de comunicacao,os enlaces entre os nos que nao propagam a informacao sobre o fenomeno ainda existem,ou seja, todos os nos percebem o sinal que esta sendo transmitido.

No entanto, se considerarmos as aplicacoes que utilizem milhares de nos trabalhando deforma autonoma e cooperativa (Estrin et al., 2001), algumas estrategias baseadas emarvorepodem nao ser escalaveis. Uma alternativa, proposta neste trabalho como roteamentosmallworld e ilustrada na Figura 1(c), consiste na utilizacao de nos sensores com um alcance decomunicacao diferenciado, de tal forma que com a utilizacao desses nos, o caminho medioentre os demais nos sensores e osinkseja reduzido (Sharma e Mazumdar, 2005; Guidoniet al., 2007) podendo assim economizar os recursos da rede.

Redes do tiposmall world, surgiram com o experimento de Milgram (1967) que intro-duz a nocao de “mundo pequeno” na perspectiva das relacoes humanas, pois uma pessoa


estarelacionada a todas as outras pessoas do mundo diretamente ou indiretamente por meiode poucos intermediarios. Em (Watts e Strogatz, 1998; Watts, 2003), os autores formal-izam as ideias desmall worlde propoem uma forma de mensurar as caracterısticas de umarede do tiposmall worldque permitem classifica-la como tal. Para isso, a rede deve apre-sentar um elevado coeficiente de agrupamento, ou seja, uma fracao de nos que sao vizinhosentre si; e um caminho medio, em numero de saltos, entre a origem e o destino, pequenoem relacao ao tamanho da rede. Dessa forma, para modelar uma rede de sensores comouma redesmall world precisamos identificar o coeficiente de agrupamento elevado, quegeralmente ocorre, e obter um caminho medio pequeno entre qualquer par de nos na rede,por meio da insercao de ligacoes entre nos distantes na rede.

Tomando como motivacao a necessidade de economizar os recursos da rede mantendo-a escalavel, este trabalho apresenta uma heurıstica baseada em algoritmos geneticos para amontagem de uma estrutura de roteamento para a propagacao de dados baseada emsmallworld. Este trabalho toma como ponto de partida o trabalho de Guidoni et al. (2007)que utiliza sistemas do tipo eixo-raio aplicados a RSSFs modeladas como redessmallworld e apresenta um modelo matematico para a atribuicao dehubsnuma rede de sen-sores de tal forma que a sua estrutura de comunicacao possua caracterısticassmall world.A contribuicao de nosso trabalho consiste na proposicao de uma solucao baseada em al-goritmos geneticos e na extrapolacao do numero de nos considerados nas solucoes apre-sentadas, chegando ate 1024 nos. Vale destacar que o trabalho de Guidoni et al. (2007)considera apenas redes de ate 32 nos. Na metodologia proposta, o modelo matematicoapresentado em Guidoni et al. (2007)e usado como ponto de partida para a formulacaodo calculo dos valores de aptidao dos indivıduos da populacao do algoritmo genetico, queutiliza codificacao binaria. A forma de representacao adotada e o calculo dos valores deaptidao incorporam diretamente algumas premissas e restricoes do problema.

Este trabalho segue com a secao 2, onde definimos o problema que estamos tratando,bem como o modelo matematico utilizado. Na secao 3, apresentamos a nossa solucaobaseada em algoritmos geneticos. Na secao 4, apresentamos os resultados referentes aaplicacao do algoritmo para obtencao da melhor configuracao para diversas RSSFs. Porfim, na secao 5, concluımos o trabalho indicando futuras direcoes.

2. Definicao do problemaPara uma rede ser consideradasmall worlddevemos ter as seguintes caracterısticas: (i)

o caminho medio mınimo entre quaisquer pares de nos deve ser pequeno; e (ii) o coefi-ciente de agrupamento deve ser alto. O caminho medio mınimo representa a quantidademınima de saltos em media entre qualquer par de nos da rede. E o coeficiente de agru-pamento define a probabilidade de dois nos vizinhos possuırem um outro no vizinho emcomum (Watts e Strogatz, 1998).

Inicialmente, considere uma rede como sendo um grafo regularG= (V,E), ondeV rep-resenta o conjunto de nos sensores eE o conjunto de arestas que representam os enlacessem fio dos nos na rede. Nesse caso todos os nos sao homogeneos possuindo um mesmoraio de comunicacao, com isso a forma de propagar a informacao sobre os fenomenosmonitorados deve seguir as estrategias de inundacao ou emarvore como ilustrado nas Fig-uras 1(a) e 1(b).

No entanto, para agregar caracterısticassmall worlda G e necessario adicionar novasligacoese′1,e

′2, . . .e

′n, com n≪ |E|, assim, a nova rede pode ser representada pelo grafo

Gsw = (V,E′), ondeE′ = E ∪ {e′1,e′2, . . .e

′n}. Nesse caso terıamos alguns nos com um

raio de comunicacao diferenciado, para permitir que o caminho medio de propagacao da


informacao seja reduzido. Com isso, podemos utilizar a estrategiasmall world(Figura 1(c))para propagar a informacao. Esses nos diferenciados serao chamados dehubs.

Logo, o problema a ser abordado nesse trabalho pode ser enunciado como segue:Problema: Dada uma RSSF representada como G, quais nos v∈V podem ser reconfigu-rados de tal forma que seja possıvel obtermos uma nova rede do tipo Gsw, onde o consumototal de energiae minimizado?

Com o objetivo de encontrar uma solucao adequada para o problema acima mencionadonos baseamos no modelo anteriormente discutido em Guidoni et al. (2007). A formulacaoaqui apresentadae baseada nas seguintes definicoes:

• SejaV o conjunto de nos. Para qualquer par de nos (i, j) com i, j ∈ V, represen-tando um ponto de origem e de destino, respectivamente, tem-sewi j que consiste nademanda de fluxo do no i para o no j, sendo normalmentewi j 6= w ji .

• SejaK o conjunto dehubs, tal queK ⊆ V. O custo de reconfiguracao do no k ∈ Ke representado porak e diz respeito ao consumo de energia do no k, caso ele sejareconfigurado.

• Sejaci jkm o custo unitario de propagacao do no i ate o no j passando peloshubs kem, tal quei, j ∈V e k,m∈ K e esta relacionado ao que a rede ira gastar durante esseprocesso.

Observe que o custo unitario de propagacaoe a composicao de tres segmentos do cam-inho do no i ate o no j. Assim, temos queci jkm = cik + αckm+ cm j, ondecik e cm j saoos custos unitarios de propagacao do no i(m) ate o no k( j) e αckm e o custo unitario depropagacao com desconto entre oshubs ke m. O parametroα representa a economia deescala alcancada pelo uso doshubs(α ≤ 1). Vale destacar que quando nos nos referimos acusto estamos sempre considerando o consumo de energia do no ou da rede.

As variaveis de decisao do modelo saoyk, que possui valor 1 se o no k e instalado comohube 0 caso contrario; exi jkm quee o fluxo do no i ate o no j roteado via oshubs ke m,nessa ordem.

O modeloe dado por:

Min

[

∑k∈K

akyk + ∑i∈V

∑j∈V

∑k∈K

∑m∈K

ci jkmxi jkm

]

(1)

Sujeito a

∑k∈K

xi jkm≤ wi j ym ∀i, j ∈V;m∈ K (2)

∑m∈K

xi jkm≤ wi j yk ∀i, j ∈V;k∈ K (3)

∑k∈K

∑m∈M

xi jkm = wi j ∀i, j ∈V (4)

xi jkm≥ 0 ∀i, j ∈V;k,m∈ K (5)

yk ∈ {0,1} ∀k∈ K (6)


A funcao objetivo (1)e composta por dois termos. O primeiro representa o custo de en-ergia de instalacao doshubse o segundo termoe o custo de energia total de propagacao.O conjunto de restricoes (2) e (3) garantem que as demandas dos pares origem–destinoso sao roteadas porhubsinstalados. A restricao (4) assegura que as demandas dos paresorigem–destino sao roteadas via algum par dehubs. Quandok = m, o roteamento so acon-tece via umunico hub. Finalmente, as restricoes (5) e (6) garantem nao negatividade eintegralidade das solucoes, respectivamente.

3. Solucao baseada em algoritmos geneticosOs Algoritmos Evolutivos sao algoritmos inspirados em ideias e princıpios gerais da

evolucao por selecao natural. O processo de evolucao na naturezae responsavel pela com-plexidade e diversidade dos organismos vivos, que se especializam em uma entre as diver-sas possibilidades de existencia e sobrevivencia que o ambiente oferece (Darwin E Huxley,2003). O processo de evolucao pode ser visto sob certos aspectos como um processo deotimizacao de sistemas naturais, caracterıstica que motivou o desenvolvimento de Algorit-mos Evolutivos, e da Computacao Evolutiva em geral, e sua utilizacao na otimizacao desistemas projetados pelo ser humano. Atualmente, a Computacao Evolutivae umaareade pesquisa madura mas em grande desenvolvimento (Mitchell, 1998; Fogel, 2005; Eibene Smith, 2008). Esse desenvolvimento nasultimas decadas tem aumentado o domıniode aplicacao dessas ferramentas e melhorado seu desempenho em diversos contextos. Aclasse de algoritmos evolutivos apresenta hoje varias famılias de metodos, dentre as quaisa famılia dos Algoritmos Geneticose provavelmente a mais popular (Mitchell, 1998).

No contexto de problemas de otimizacao combinatoria, muitas tecnicas Metaheurısticasemergiram nosultimos trinta anos (Blum e Roli, 2003), e, dentre elas, os algoritmosgeneticos tem se mostrado ferramentas importantes na solucao desses problemas, devidoas caracterısticas de capacidade de busca global e capacidade de tratar problemas naolineares, nao convexos e com restricoes complexas. Apenas em carater ilustrativo, con-siderando problemas de sequenciamento da producao, de acordo com Allahverdi et al.(2008), a metaheurıstica mais utilizada para resolver essa classe de problemase o Algo-ritmo Genetico (Goldberg, 1989; Mitchell, 1998), seguido pelo metodo Busca Tabu (Glovere Laguna, 1997).

Dadas essas caracterısticas, optou-se neste trabalho por desenvolver uma heurısticabaseada em algoritmos geneticos para o problema de configuracao da estrutura de rotea-mento para a propagacao de dados numa RSSF baseada emsmall world. A metodologiaproposta parte do modelo matematico descrito na secao 2 para desenvolver uma codificacaoadequada para os indivıduos da populacao e uma formulacao apropriada para a funcao deavaliacao de aptidao, dois ingredientes basicos na composicao de um algoritmo genetico.A seguir detalhamos as consideracoes feitas no desenvolvimento do algoritmo.

3.1. Consideracoes iniciaisO modelo matematico descrito na secao 2 e apresentado em (Guidoni et al., 2007)

representa uma formulacao mais geral, que pode ser bastante simplificada se considerarmosum no sinkfixo.

Na metodologia proposta, adotamos codificacao binaria dos indivıduos do algoritmogenetico. Cada indivıduo p(i) na populacao Pt , ver nomenclatura adicional descrita natabela 1,e representado por uma cadeia deN bits, em que um 0 na posicao k indica queo no k nao esta configurado como umhub e um 1 na posicao k indica que o no k estaconfigurado como umhub. Dessa forma, o indivıduo codifica quais nos estao configuradoscomohubs, e portanto representa uma estrutura de roteamento candidata.


Tabela 1: Descricao das variaveis do algoritmoVari avel Descricao

N Numero de nos do problemaY Conjunto deındices dos nos simples, nao configurados comohubsK Conjunto deındices dos noshubsPt Populacao do algoritmo genetico na geracaotCI Custo de energia total de configuracao dos noshubsCP Custo de energia total de propagacao dos dados na rede ate o no sinkak Custo de energia de configuracao do no k comohubdi j Distancia do no i ao no jci j Custo de energia unitario de propagacao do no i para o no jwi Fluxo de dados do no i – demanda de comunicacaoµ Tamanho da populacaoρm Taxa de mutacao da populacaoρc Taxa de cruzamento da populacao

i, j,k Variaveis de controle

Al em disso, podemos adotar a seguinte simplificacao no calculo do custo de energiatotal de propagacao dos dados na rede para uma dada configuracao codificada por umindivıduo da populacao:

• Dado o indivıduo p(i) ∈ Pt que codifica o conjuntoK ⊆V deındices dos nos config-urados comohubs, tem-se o conjuntoY dos nos nao configurados comohubs, de talforma queY∪K = V eY∩K = /0.

• Todo no i ∈Y envia todo o seu fluxo de dados para ohub k∈ K de menor custo deenergia associadocik, geralmente ohubmais proximo, se o custo de energia unitariode propagacao for diretamente proporcionala distanciadik.

• Entre cada um dos noshubse o no sink, o roteamento de menor custo de energiaeobtido pelo algoritmo de Dijkstra, respeitando o numero maximo de saltos permiti-dos.

Finalmente, consideram-se as seguintes restricoes:

• A distancia entre todo no i ∈ Y e o hub para o qual ele envia seu fluxo deve sermenor do que o raio de comunicacao r do no, ou seja, deve-se terdi j < r, ∀i ∈Y ej = argmink dik, k∈ K.

• A distancia entre cadahub e todos os outroshubsdeve ser menor do que o raio decomunicacao dohub, configurado como sendo igual a 3r, ou seja, deve-se terdi j < 3r,∀i, j ∈ K. Essa restricao visa garantir que os nos hubsformem um grafo completoentre si.

Dadas essas consideracoes iniciais, temos a seguinte formulacao

y∗ = argminCI +CP (7)


Sujeito a

di j < r, ∀i ∈Y, j = argmink dik,k∈ K (8)

di j < 3r, ∀i, j ∈ K (9)

yk ∈ {0,1}, ∀k∈V (10)

em queCI e o custo de energia de instalacao dado por

CI = ∑k

akyk

eCP e o custo de energia de propagacao dos dados.Cada indivıduo do algoritmo genetico e avaliado considerando-se a formulacao (7)-

(10). Caso a configuracao representada pelo indivıduo viole alguma das restricoes, essaviolacaoe penalizada e somada aCI +CP. Esse valor finale usado no calculo do valor deaptidao do indivıduo.

3.2. Operadores basicosO algoritmo genetico implementado utiliza selecao por torneio binario para a reproducao,

cruzamento com dois pontos de corte com probabilidadeρc = 0.8, e mutacao do tipo in-versao de bit com probabilidadeρm = 0.1 (Goldberg, 1989; Mitchell, 1998).

A estrutura geral do algoritmo genetico implementadoe mostrada no algoritmo 1.

Algoritmo 1: Algoritmo Genetico para a configuracao da redesmall worldEntrada: Numero de nosN, custo de energia de instalacaoak, matriz de distancias

dos nosdi j , matriz de custos de energia unitarios de propagacaoci j ,demanda de comunicacaowk, tamanho da populacaoµ, taxa de mutacaoda populacaoρm e taxa de cruzamentoρc.

Saıda: Nos configurados comohubs, custos de energia totaisCI eCP.inıcio1

t← 0 {contador de geracoes}2

Pt = {p(1), . . . , p(µ)}← Inicializar Populac~ao(N)3

enquantot < tmax faca4

Ft ← Avaliar Populac~ao(Pt ,ak,di j ,ci j ,wk)5

t∗, p∗best← Armazenar Melhor(Pt ,Ft)6

P′

t ← Selec~ao por torneio(Pt ,Ft)7

P′′

t ← Cruzamento(P′

t ,ρc)8

P′′′

t ← Mutac~ao(P′′

t ,ρm)9

Pt+1← Substituic~ao(Pt ,P′′′

t )10

t← t +111

fim12

fim13

O algoritmo comeca com uma populacao de µ indivıduos gerados aleatoriamente,que codificam configuracoes candidatas para o problema. Cada geracao t consiste naexecucao iterativa dos operadores geneticos que caracterizam o algoritmo. Na avaliacaoda populacao, linha 5, a formulacao (7)-(10)e utilizada com penalizacao de quaisquerrestricoes que sejam violadas pela configuracao candidata. Na linha 7, tem-se a etapa de


selecao dos indivıduos para a reproducao, em que optou-se pela selecao estocastica portorneio binario. Nesta forma de selecao, dois indivıduos sao selecionados aleatoriamenteentre a populacao e competem entre si de forma determinıstica, istoe, o melhor indivıduoentre os dois vence ee selecionado para a reproducao e armazenado emP

′

t . Os melhores in-divıduos possuem portanto maior probabilidade de serem selecionados para a reproducao.Nas linhas 8 e 9, uma nova populacao e formada a partir dos indivıduos selecionados,usando-se os operadores de cruzamento e mutacao. Esses operadores sao constituıdospor heurısticas especıficas e em geral com algum componente de aleatoriedade. Convemdestacar que embora os operadores geneticos apresentem algum grau de aleatoriedade, abusca realizada pelo algoritmo genetico esta longe de ser uma busca aleatoria, pois o op-erador de selecao possui uma componente de determinismo que orienta o algoritmo nadirecao das melhores regioes do espaco de busca. Assim como na natureza a selecao nat-ural e forca motriz na evolucao e na criacao de complexidade, nos algoritmos geneticos ooperador de selecaoe o mecanismo responsavel pelo progresso acumulativo e direcionadodo algoritmo.

Finalmente, na linha 10, um operador de substituicao forma a populacao da proximageracao a partir dePt e seus descendentesP

′′′

t . A substituicao pode ser vista como um oper-ador de sobrevivencia. No algoritmo genetico, tipicamente adota-se uma substituicao de-terminıstica, em queP

′′′

t substituiPt , porem outras formas de substituicao estao disponıveisem algoritmos evolutivos.

4. Resultados e avaliacoesConsideramos que ao aplicarmos o nosso algoritmo genetico e possıvel obter uma

configuracao aceitavel para os nos de uma rede de sensores, de tal forma que tenhamosuma rede do tiposmall worldque economiza energia no trafego de pacotes, considerandoo fluxo e a distancia entre os nos. Para validar essa premissa avaliamos o numero de noshubs instalados, o coeficiente de agrupamento e o caminho medio mınimo obtido comnossa solucao. A avaliacao da nossa solucaoe baseada nas seguintes consideracoes:

• Execucao: Foram realizadas 20 execucoes em cada uma das 10 instancias de tamanhoda rede, utilizando o algoritmo genetico descrito na secao 3 e implementado em lin-guagem Java. O algoritmo genetico foi executado com populacao deµ = 50 in-divıduos, por 500 geracoes1. Os testes foram executados em uma maquina com pro-cessador Intel Quadcore 2.4GHz com 2GB de memoria. Os resultados apresentadosconsideram a media das instancias utilizadas.

• Topologia da rede: A densidade da redee mantida constante e todos os nos tem amesma configuracao dehardware. Considerando a rede com umaareaA = L×L ono sink e localizado na posicao (0×0) e o no origem localizado em(L×L). Paramantermos a densidade constante, a obtencao daareae dada por,A= π r2 |S|/d, onder e o alcance do radio,|S| e o numero de sensores ed e a densidade da rede (escolhidaarbitrariamente com o valor 8,4791).

• Custos de energia de instalacao: O custo de energia de instalacao ak de um no kcomohub e inversamente proporcionala distancia dek aosink, ou seja, quanto maisdistante dosinkmenor sera o custo de energia para instalark comohub, pois para osnos proximos aosinko consumo de energia sera maior.

1Inicialmente esse numero (500) foi escolhido empiricamente, no entanto apos uma analise de convergencia observa-mos que esse numero era suficiente para as instancias consideradas no trabalho.


• Demanda dos nos: E definido pelo fluxo de dados que cada no possui (wi). Comotemos umunicosink localizado em(0,0) os nos mais proximos a ele terao um maiorfluxo, pois precisarao rotear mais pacotes do que os nos que estao mais distantes. Porexemplo, considerando que osink possui uma demanda,wsink = ∑N

i wi, sendoN onumero de nos.

• Custo de energia propagacao dos dados: O custo de energia de transportee dadopor Ci, j = widi, j , ondewi representa a quantidade de pacotes quei precisa rotear(demanda) edi, j representa a distancia entrei, j.

• Configuracao de saıda: ConsiderandoG = (V,E) o grafo de entrada eGb = (V,Eb)o grafo obtido com genetico. A saıdae dada pelo grafosmall world Gsw = (V,Esw),ondeEsw= E∪Eb. Com isso, calculamos o coeficiente de agrupamento e o caminhomedio mınimo. Alem disso, obtemos como saıda a quantidade de noshubsutilizados.

A tabela 2 apresenta os resultados do algoritmo genetico ao variar a quantidade denos da rede em(128,256,512,1024). Os valores analisados sao: (i) quantidade dehubsinstalados - QC; (ii) coeficiente de agrupamento - CA; e (iii) caminho medio mınimo -CMM.

Tabela 2: Resultados referentesa variacao do numero de nos na rede (SW- small world).Nos Hubs Tempo (s) Coeficiente de agrupamento Caminho medio

grafo regular grafoSW grafo regular grafoSW

128 11 44 0.689 0.691 2.550 2.659256 24 353 0.657 0.650 3.381 2.729512 68 4394 0.633 0.655 3.739 2.6191024 252 49119 0.624 0.706 3.558 2.475

A partir dos resultados, podemos observar que com a utilizacao da tecnica proposta,conseguimos construir uma rede com caracterısticassmall world. Para uma rede ser con-sideradasmall world, o CA do grafo resultante deve ser semelhante ou ligeiramente maiordo que o do grafo regular, o que pode ser observado nos resultados apresentados. Comrelacao ao CMM, podemos observar que para as redes analisadas(256,512,1024), o CMMfoi reduzindo em 20%, 30% e 31% respectivamente. Para garantir que a distancia entrequalquer par de nos nao ultrapasse o limite pre-estabelecido na definicao do problema, saonecessarios 11, 24, 68 e 252hubsrespectivamente para as diferentes quantidades de nos darede.

Na figura 2,e ilustrada a razao entre o CA e CMM entre os grafos regular esmallworld. Podemos observar quea medida que a quantidade de nos, ou seja, o diametro2 darede aumenta, a razao entre os CMMs diminui, por conseguinte, o CMM no grafosmallworld diminui em relacao ao grafo regular. Podemos observar tambem que,a medida quea quantidade de nos da rede aumenta, a razao entre os CAs aumenta em torno de 15%,o quee esperado para uma rede com caracterısticassmall world, pois seu CA deve sersemelhante ao do grafo regular. Ja a razao do caminho medio mınimo decaia medida queo numero de nos na rede aumenta.

2Diametroe o maior caminho entre qualquer par de nos da rede.


Small world vs. grafo regular

Número de nós

CM

M(G

’)/C

MM

(G)

e C

A(G

’)/C

A(G

)CMM(G’)/CMM(G)CA(G’)/CA(G)

128 256 512 1024

0.6

1.0

1.4

1.8

Figura 2: Razao do CA e CMM entre os grafos regular esmall world.

5. Conclusoes e trabalhos futurosAs redes de sensores sem fio possuem restricoes de recursos, tais como baixo poder

computacional, largura de banda reduzida e, especialmente, fonte de energia limitada. Oalto consumo de energia pode ser observado quando o fluxo de dados em cada no e altoe quando o numero de vizinhose grande. Alem disso, essas redes podem ser modeladascomo redes do tiposmall world, onde o coeficiente de agrupamentoe alto e o caminhomedio mınimo entre cada par de nos na redee pequeno. A partir da formulacao apresen-tada, obtivemos uma configuracao com um caminho medio mınimo pequeno entre qual-quer par de nos, obtendo assim, uma configuracaootima para a rede, onde alguns nos saoescolhidos comohubsgarantindo o menor consumo de energia.

A partir dos resultados obtidos foi possıvel identificar as caracterısticas de coeficientede agrupamento e caminho medio mınimo entre qualquer par de nos nas configuracoes derede avaliadas. Observamos que com a utilizacao de nossa abordagem, o caminho mediomınimo reduziu e o coeficiente de agrupamento aumentou para todos os cenarios avaliados.Com isso, a partir da nossa abordagem, foi possıvel obter redes do tiposmall world.

Como trabalhos futuros, pretendemos avaliar a solucao empregada em funcao da en-ergia residual total da rede com e sem o uso da nossa abordagem. Alem disso, iremosavaliar nossa solucao considerando algoritmos memeticos. Implementaremos uma versaodistribuıda para o genetico aqui apresentado, com o objetivo de executar a solucao internana rede. Por fim, apresentaremos uma solucao exata para um numero reduzido de nos, detal forma que possamos comparar essa solucao com nossa abordagem baseada em algorit-mos geneticos.

ReferenciasIan F. Akyildiz, WellJan Su, Yogesh Sankarasubramaniam, e Erdal Cayirci, A survey

on sensor networks,IEEE Communications Magazine, 40(8):102–114, agosto 2002.

A. Allahverdi, C. T. Ng, T. C. E. Cheng, e M. K. Kovalyov, A survey of schedulingproblems with setup times or costs,European Journal of Operational Research, 187(3):985–1032, 2008.


T. Arampatzis, J. Lygeros, e S. Manesis,A survey of applications of wireless sensorsand wireless sensor networks,13th IEEE Mediterranean Conference on Control andAutomation (MED’05), paginas 719–724, Hawaii, USA, junho 2005, IEEE ComputerSociety.

Christian Blum e Andrea Roli, Metaheuristics in combinatorial optimization: overviewand conceptual comparison,ACM Computing Surveys, 35(3):268–308, setembro 2003.

Charles Darwin E Julian Huxley, The Origin Of Species: 150th Anniversary Edition,Signet Classics, 2003.

Agoston E. Eiben e James E. Smith,Introduction to Evolutionary Computing, NaturalComputing Series, Springer, 2008.

Deborah Estrin, L. Girod, G. Pottie, e M. Srivastava, Instrumenting the world with wire-less sensor networks,26th IEEE International Conference on Acoustics, Speech, andSignal Processing (ICASSP’01), volume 4, paginas 2033–2036, Salt Lake City, Utah,USA, junho 2001, IEEE Computer Society.

David B. Fogel, Evolutionary Computation: Toward a New Philosophy of Machine Intel-ligence, IEEE Press Series on Computational Intelligence, Wiley-IEEE Press, tereceiraedicao, 2005.

F. Glover e M. Laguna, Tabu Search, Kluwer Academic Publishers, 1997.

David E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning,Addison-Wesley Professional, 1989.

Daniel L. Guidoni, Andr e Luiz Lins Aquino, Raquel da Silva Cabral, Antonio Al-fredo Ferreira Loureiro, e Antonio Otavio Fernandes, Sistemas do tipo eixo-raioaplicadosa redes de sensores sem fio modeladas como redes small world,39 SimposioBrasileiro de Pesquisa Operacional (SBPO’07), paginas 1–12, Fortaleza, CE, Brasil,agosto 2007, SOBRAPO.

Mikl os Maroti, Directed flood-routing framework for wireless sensor networks,5thACM/IFIP/USENIX International Conference on Middleware (Middleware’04), vol-ume 78, paginas 99–114, Toronto, Ontario, Canada, outubro 2004, ACM.

Stanley Milgram, The small world problem,Psychology Today, 2:60–67, 1967.

Melanie Mitchell, An Introduction to Genetic Algorithms, Complex Adaptive Systems,The MIT Press, 1998.

Wanzhi Qiu, Efstratios Skafidas, e Peng Hao, Enhanced tree routing for wireless sensornetworks,Ad Hoc Networks, 7(3):638–650, maio 2009.

Elizabeth M. Royer e Chai-Keong Toh, A review of current routing protocols for ad-hocmobile wireless networks,IEEE Personal Communications, 6(2):46–55, abril 1999.

Gaurav Sharma e Ravi Mazumdar, Hybrid sensor networks: A small world,6th ACMInternational Symposium on Mobile Ad Hoc Networking and Computing (MobHoc’05),paginas 366–377, Urbana-Champaign, Illinois, USA, maio 2005, ACM.


Duncan J. Watts,Small Worlds: The Dynamics of Networks Between Order and Random-ness, Princeton University Press, 2003.

Duncan J. Watts e S. H. Strogatz, Collective dynamics of ’small-world’ networks.,Na-ture, 393(6684):440–442, junho 1998, ISSN 0028-0836.
