Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
BALANCEAMENTO DA DISSIPAÇÃO DE POTÊNCIA NO ROTEAMENTO
EM REDE DE SENSORES
Ricardo S. de Camargo
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
Av. Antônio Carlos, 6627 – 31.270-010 – Belo Horizonte – MG
[email protected]
Gilberto de Miranda Jr.
Departamento de Engenharia de Produção
Universidade Federal de Minas Gerais
Av. Antônio Carlos, 6627 – 30.161-010 – Belo Horizonte – MG
[email protected]
Geraldo R. Mateus
Departamento de Ciência da Computação
Universidade Federal de Minas Gerais
Av. Antônio Carlos, 6627 – 31.270-010 – Belo Horizonte – MG
[email protected]
Abstract
The recent breakthroughs on Wireless Sensor Networks (WSN) have offered new challenges to
network designers. One of these great challenges is the power dissipation of sensor networks, and,
therefore, energy consumption. The inefficient use of energy on WSNs may result in serious problems,
such as total disconnection of subnetworks, making them unreachable. In this work, a new nonlinear
model is proposed to tackle the power dissipation for routing problems on WSNs. The power
dissipation balancing for routing problems on WSNs is solved by the Generalized Benders
Decomposition method. Computational results, although limited, are encouraging: lower total power
dissipation of the network and greater remaining lifetime battery of the sensors.
Resumo
Os recentes avanços em Rede de Sensores sem Fio (RSSF) têm oferecido novos desafios aos
projetistas de redes. Um desses grandes desafios consiste no balanceamento da potência dissipada
pelos sensores, e, conseqüentemente, no consumo de energia. O uso ineficiente da energia em RSSF
pode causar sérios problemas, tais como a desconexão total de subredes, tornando-as inacessíveis. No
presente trabalho, um novo modelo não linear é proposto abordando a dissipação de potência no
roteamento em RSSFs. O problema de roteamento com balanceamento de dissipação de potência é
resolvido através do método de decomposição de Benders generalizado. Os resultados computacionais
obtidos, apesar de limitados, são encorajadores: menor dissipação total de potência da rede e maior
tempo de vida residual das baterias dos sensores.
1 Introdução
Nos últimos anos, os avanços da micro-eletrônica, da minituarização e dos equipamentos de
comunicação sem fio possibilitaram o desenvolvimento de uma tecnologia visionária: as redes de
sensores sem fio (RSSF).
As RSSFs são um tipo especial de rede cujos nós são sensores autônomos e compactos, dotados
de limitado poder de computação e memória, que podem comunicar uns com os outros sem fio. O
principal objetivo dessas redes é o de monitorar o ambiente físico no seu entorno, podendo medir
desde temperatura à intensidade luminosa, vibração, som, radiação, entre outros, dependendo da
aplicação fim da rede.
Numa aplicação de RSSFs, os nós sensores monitoram o ambiente, disseminando as
informações coletadas para outros nós que, eventualmente, podem pré-processá-las ou repassá-las para
um observador [25]. Os nós que geram os dados são denominados nós fontes. Os dados gerados por
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
uma RSSF chegam ao observador através de pontos de acesso da rede que podem ser estações rádio
base e/ou os próprios nós sensores, chamados de nós sorvedouros ou monitores. Em função da
limitação do raio de comunição, a comunição entre os nós fontes e os pontos de acesso da rede é do
tipo multi-hop. Os dados são enviados de sensor para sensor, até alcançar os nós sorvedouros. Isto
implica que cada nó sensor é um roteador potencial de tráfego, uma vez que, normalmente, nem todos
os sensores têm um canal de comunição direto com o ponto de acesso. Esse tipo de comunição, nós
comunicando diretamente entre si através de enlaces de comunicação sem fio, permite com que as
RSSFs possam ser vistas como um tipo especial de rede ad hoc [14].
Apesar das RSSFs serem semelhantes às redes do tipo ad hoc, existem algumas diferenças
tradicionais. Uma delas é o elevado número e a alta densidade de nós que compõe uma RSSF.
Escalabilidade é essencial para se ter uma boa resolução de sensoriamento [24]. Outra característica
importante de uma RSSF é a limitação do sensor. Sensores possuem recursos escassos tais como
pouca memória, pouco poder de processamento, raio de alcance de comunicação limitado e,
principalmente, como são alimentados por baterias, pouca energia. Normalmente, como os sensores
são empregados em lugares de difícil acesso, inóspitos, a troca ou a recarga das baterias pode ser uma
tarefa inconveniente. Em função dessa escassez de energia e, apesar dos sensores serem estáticos, a
topologia de uma RSSF é dinâmica. Durante períodos de inatividade, sensores podem entrar num
estado de economia de energia tornando-se temporariamente inativos ou, até mesmo, deixando de
funcionar, quando a energia da bateria acaba [20].
Em RSSFs, o uso eficiente e a conservação de energia são dois dos aspectos mais importantes a
serem considerados por um projetista no projeto dessas redes, uma vez que ambos são fatores chaves
no prolongamento do tempo de vida de uma RSSF [11]. O tempo de vida de cada sensor depende
principalmente da sua dissipação de energia, que por sua vez está relacionado com a atividade que o
sensor está realizando: transmissão, recepção, monitoração, processamento de informação e dormindo
(economizando energia). Além disso, como os nós sensores podem funcionar como roteadores na
conexão de outros nós ao sorvedouro, a conectividade da rede diminui gradativamente com a exaustão
da bateria dos sensores [27]. Isto pode resultar em subredes de nós totalmente desconectadas,
inacessíveis. Portanto, além dos desafios tradicionais de projeto de uma rede ad hoc (cobertura,
número mínimo de nós, garantia de entrega do fluxo de dados), no projeto de uma RSSF têm-se dois
novos desafios: o nível de consumo de energia e, conseqüentemente, o tempo de vida da rede.
No presente trabalho, propomos uma nova abordagem para balancear o consumo de energia dos
sensores ao realizar o roteamento de dados, dado que a cobertura esteja garantida. O balanceamento é
baseado em uma função não linear do consumo de energia que um sensor tem ao rotear o fluxo de
dados para um outro sensor. Essa abordagem não só permite um balanceamento melhor da dissipação
de potência, como diminui a energia consumida e a colisão de pacotes, melhorando o mapa total de
energia da rede e, por conseqüência, prolongando o tempo de vida da RSSF.
O restante do artigo está organizado da seguinte forma: na seção 2, alguns trabalhos
relacionados ao roteamento de pacotes em RSSFs são apresentados; na seção 3, o modelo de RSSF
usado, assim como as considerações de energia utilizadas e o modelo matemático proposto; na seção 4
e 5, o algoritmo empregado na solução da nova abordagem é detalhado e os testes e análises
realizados, respectivamente. Finalmente, a última seção contém as conclusões deste trabalho.
2 Trabalhos Relacionados
O trabalho apresentado lida com o roteamento em RSSFs, que inclui a garantia de conectividade
entre os nós sensores e a formação de uma topologia que garanta o fluxo de dados dos nós fontes ao nó
sorvedouro. São apresentados a seguir alguns trabalhos relacionados ao tema.
Considerando apenas os métodos e os algoritmos de roteamento, Rodoplu e Meng [23] propõem
um protocolo de conexão de energia mínima baseado no algoritmo Bellman-Ford de menor caminho.
Gomez et al. [10] investigam um algoritmo de roteamento para redes ad hoc representando a potência
de transmissão por custos lineares.
Ganesan et al. [6] apresentam curvas de tradeoff de energia e robustez através de um algoritmo
que permite o roteamento de dados através de vários caminhos, ou multipath routing. Através da
simulação, Ganesan et al [6] mostram que, apesar de não ser eficiente quanto ao consumo de energia,
o algoritmo deles apresenta certa robustez, isto é garante a entrega dos dados no nó sorvedouro.
Ganesan et al assumem a existência de vários caminhos de menor comprimento, considerando 2 tipos
1602
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
básicos de menor caminho. No primeiro tipo considerou apenas caminhos com nós disjuntos, isto é, o
sensor pertencente a um menor caminho, não pode pertencer a outro caminho. No segundo tipo,
relaxa-se a necessidade de nós disjuntos, permitindo-se que apenas alguns nós, próximos ao
sorvedouro, possam pertencer a mais de um menor caminho. Esse segundo tipo recebe o nome de
braided multipath routing.
Krishanamachari, Estrin, e Wicker em [13] estudam três abordagens para construção de uma
árvore de roteamento em redes de sensores sem fio planas e ainda avaliam o impacto de agregação de
dados nessas redes. As três abordagens são: Fonte Mais Próxima, Árvores de Caminho Mínimo e
Árvore Incremental Gulosa. Na primeira abordagem os nós fontes enviam seus dados ao nó que se
encontra mais perto do sorvedouro. Na segunda abordagem cada fonte envia seus dados pelo caminho
mais curto entre ele e o sorvedouro. Finalmente na última estratégia a topologia de disseminação é
uma árvore formada pelo caminho mínimo entre o nó sorvedouro e o nó fonte mais próximo, sendo o
nó mais próximo incluído a cada etapa na topologia.
Em [28], Zhou e Krishnamachari estudam a formação de uma árvore de disseminação através de
abordagens de escolha dos pais na árvore, tais como: a seleção Earliest First que consiste na escolha
do nó pai como sendo o primeiro nó que se candidata; a seleção Nearest first que corresponde na
seleção do nó mais próximo ao nó pai como candidato; a seleção Aleatória que consiste na escolha do
pai totalmente ao acaso; e, finalmente, a seleção Aleatória ponderada que funciona atribuindo aos
candidatos pesos em função do número de vizinhos, quanto maior o número de vizinhos menor o peso.
Através desses pesos, atribui-se uma probabilidade para cada nó, sendo posteriormente então
escolhido o pai.
Heinzelman et al [12] desenvolveram o LEACH (low-energy adaptive clustering hierarchy), um
protocolo que distribui a dissipação de energia através da formação de agrupamentos de sensores
(clusters) e da escolha de um desses sensores como líder responsável pelo gerenciamento de um
agrupamento.
A grande maioria dos algoritmos de roteamento são baseados no modelo de propagação de
ondas do tipo espaço livre (free space). Nesse modelo, a influência da superfície da Terra é desprezada
ao se explicar o comportamento da onda de rádio durante a transmissão e recepção. Os efeitos
indesejáveis durante a propagação de onda não são considerados. Os dois principais efeitos
indesejáveis são: (i) o shadowing, ou seja, o efeito que a potência do sinal recebido varia devido à
obstruções no caminho de propagação entre o transmissor e o receptor; e (ii) o multipath fading, ou a
interferência causada na recepção do sinal devido à ondas de sinais refletidas em obstáculos. Esse
último efeito causa degradações significativas no desempenho da transmissão e recepção. Catovic et
al. [4] propõem um modelo de roteamento no qual esses efeitos indesejáveis são simplificados e
representados através de uma função não linear. Akyildiz et al. [2] e Ganesan et al. [6] apresentam um
bom exame da literatura sobre a área.
No presente trabalho, um modelo não linear de roteamento considerando a dissipação de
potência é proposto. Contrário as estratégias de roteamento multi-caminhos (multipath routing), a
proposta desse artigo é fazer o roteamento balanceando-se a dissipação de potência pela rede através
de uma topologia de roteamento baseado em árvore. Esse balancemanto é conseguido ao se calcular
a não linearidade inerente a dissipação de potência durante o uso da energia em sistemas eletroeletrônicos. Essa abordagem se mostra coerente à rede de sensores, uma vez que uma das grandes
preocupações no projeto de rede de sensores é o tempo de vida da mesma. A robustez (garantia de
entrega dos pacotes ao sorvedouro) obtida por estratégias do tipo multipah routing não se justifica
plenamente ao se ter um tempo de vida da rede consideravelmente reduzido. As estratégias multipath
routing apresentam um maior consumo de energia [6]. Na próxima seção, o modelo não linear é
apresentado em maiores detalhes.
3 Formulação Matemática
Considerando que os sensores são idênticos, possuindo os mesmos equipamentos de
transmissão, uma quantidade limitada de energia da bateria e antenas omnidirecionais, podemos fazer
as seguintes considerações.
3.1 Definições
Uma RSSF é representada por um grafo direcionado G (V , E ) , onde V é o conjunto de nós
1603
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
sensores, E é o conjunto de arcos que representam os enlaces válidos de comunição entre os nós
sensores. Um arco, ou um enlace de comunição entre 2 nós i e j , é representado por (i, j ) ∈ E , onde
i , j ∈ V . Seja ainda o nó o , o nó sorvedouro que deve receber os dados de um número | K | , onde
K é o conjunto de nós sensores ativos. Cada sensor ativo possui uma demanda d k diferente, onde
k∈K e K ⊆V .
A existência ou não de um arco (i, j ) , nó i conseguindo se comunicar com nó j , depende da
potência de transmissão usada pelo nó i . Isto é, quanto maior o raio de alcance do transmissor, maior
a potência necessária. Como a potência de transmissão é diretamente proporcional ao quadrado da
distância, ou seja, uma relação não linear, pode-se então discretizar os raios de alcance de um sensor
em intervalos e, conseqüentemente, as respectivas potências de transmissão usadas para cada raio.
Dessa forma, temos o parâmetro bij que representa a potência usada estabelecer o arco (i, j ) . A figura
1 ilustra os diversos raios e suas respectivas potências de transmissão.
Figura 1: Alcance de transmissão e potência necessária
Como mencionado anteriormente, uma das maiores preocupações no projeto de uma RSSF é o
uso eficiente da energia, resultando na busca por métodos que minimizem a potência usada na
comunicação [21]. Considerando que o consumo de energia é dada pelas 4 atividades básicas de um
sensor: sensoreamento, recepção, computação e transmissão, temos, considerando a potência apenas,
que a potência total, P
, consumida é dada pela equação (1), onde P , P , P e P são,
total
s r c
t
respectivamente, as potências gastas no sensoreamento, recepção, computação e transmissão.
P
=P +P +P +P
(1)
total s r c t
Como a única dissipação de potência que depende da distância é a da transmissão,
permanecendo constantes as demais parcelas, podemos reescrever a equação (1) como a equação (2),
onde d é um valor constante indicando a sobrecarga das atividades de sensoreamento, recepção e
computação.
(2)
Ptotal = Pt + d
Podemos escrever a potência de transmissão, apresentada pela equação (3), em função do
número de pacotes g que são enviados pelo arco (i, j ) ; do número de bits de cada pacote, B ; da
ij
corrente necessária para a transmissão de 1 bit no arco (i, j ) , representada por a ; e onde R é a
resistência do sensor [20].
(3)
Pt = RI 2 = R ( g ij Ba ) 2 = c( g ij ) 2 , onde c = R( Ba) 2
A equação (3) é uma equação quadrática em função do fluxo de dados que passa pelo arco
(i, j ) . Podemos então criar uma função não linear que penaliza a sobrecarga de fluxo de dados num
determinado arco (i, j ) . Essa função permite o roteamento dos pacotes por rotas alternativas,
conseqüentemente, implicando numa diminuição da potência de transmissão total e num tempo de
vida da rede maior. A função que penaliza a sobrecarga de fluxo no arco (i, j ) é denominada τ ij ( g ij ) .
A função não linear τ ij ( g ij ) permite a elaboração do modelo de programação matemática a ser
apresentado na próxima seção. Esse modelo permite a seleção dos arcos que fazem a menor dissipação
de potência do sistema e, portanto, um uso mais eficiente da energia da rede. A seleção desses arcos
1604
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
cria as rotas dos nós fontes até o nó sorvedouro. Como há um balanceamento da dissipação total de
potência do sistema, alguns nós podem funcionar como nós do tipo multi-hop (nós de transbordo).
3.2 Modelo Matemático
O modelo de programação não linear responsável pelo roteamento de uma RSSF balanceando a
potência possui as seguintes variáveis de decisão:
⎧1 se o arco (i, j ) é estabelecido;
xij = ⎨
⎩0 caso contrário.
f :
fluxo de pacotes passando no arco (i, j ) originários do sensor k ;
ijk
g :
fluxo total da pacotes passando pelo arco (i, j ) .
ij
E os seguintes parâmetros:
b :
potência de ativação do arco (i, j ) ∈ E ;
ij
c :
ijk
o:
potência por unidade de pacote gasta no processamento dos
pacotes que passam no arco (i, j ) originários do sensor k ;
nó sorvedouro responsável por receber todos os dados de
sensoreamento;
número de pacotes originados no sensor k .
d :
k
O modelo matemático M é dado por:
⎧
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
M⎨
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪
⎪⎩
min
sujeito a:
∑
( i , j )∈E
[bij xij + τ ij ( g ij ) + ∑ cijk f ijk ]
(4)
k ∈K
∑ f −g ≤0
− ∑ f = −d
∀(i, j ) ∈ E
(5)
para nó o e ∀k ∈ K
(6)
∀k ∈ K
(7)
∀j ∈ V − {o} e j ≠ k e ∀k ∈ K
(8)
f ijk ≤ d k xij
∀(i, j ) ∈ E e ∀k ∈ K
(9)
f ijk ≥ 0
∀(i, j ) ∈ E e ∀k ∈ K
(10)
gij ≥ 0
∀(i, j ) ∈ E
(11)
xij ∈ {0,1}
∀(i, j ) ∈ E
(12)
k ∈K
ijk
( j , o )∈E
∑f
( k , i )∈E
−
kik
∑f
( i , j )∈E
ij
jok
k
= dk
ijk
+
∑f
( j , l )∈E
jlk
=0
A função objetivo (4) possui 3 parcelas: a primeira contabiliza a potência usada para ativar os
arcos; a segunda penaliza o uso abusivo (sobrecarga) dos arcos, enquanto a terceira parcela calcula o
custo linear operacional de se receber e processar os pacotes. As restrições (5) calculam o fluxo total
de dados que passa pelo arco (i, j ) . As restrições (6) garantem que o fluxo total originado no sensor
fonte k , que chega ao nó sorvedouro, é igual ao número de pacotes gerados em k , enquanto as
restrições (7) garantem que o fluxo total dos pacotes que saem do sensor fonte k é igual ao número de
pacotes gerados nesse sensor. As restrições (8) garantem a conservação de fluxo de pacotes nos nós
que fazem apenas o transbordo de pacotes. O acoplamento das variáveis x e f é realizado pelas
restrições (9), garantindo asssim que o fluxo de pacotes no arco (i, j ) só é permitido se o arco existir
e a potência bij é consumida. A potência bij é pré-processada através do modelo free-space de
propagação de sinais. As restrições (10) a (12) são, respectivamente, as restrições de não negatividade
dos fluxos de pacotes f ijk e g ij , e de integralidade (binária) da variável xij . Duas formulações
semelhantes, mas feitas para o projeto de redes do tipo multicasting, podem ser encontradas em [19,
1605
Pesquisa Operacional e o Desenvolvimento Sustentável
23].
27 a 30/09/05, Gramado, RS
Uma propriedade teórica importante para se destacar é que, para τ ij ( g ij ) = 0, (i, j ) ∈ E , o
modelo se reduz a uma formulação multiproduto para o problema de Steiner em grafos direcionados,
como demonstrado por Maculan e outros [5, 26, 15, 9].
Como a função de penalidade é uma função quadrática e como o parâmetro c ≥ 0 , veja (3),
temos portanto uma função convexa. Logo podemos resolver o modelo não linear inteiro misto M
através do método de Decomposição de Benders Generalizado [8], conforme ilustrado na próxima
seção.
4 Algoritmo
O modelo não linear inteiro misto M é resolvido por uma decomposição cruzada baseada no
método de Decomposição de Benders Generalizado [3, 8]. Apesar de ter sido originalmente
desenvolvido para problemas de programação inteira mista, a parte não linear pode ser incorporada ao
método desde que seja tratada separadamente por algum método de solução para problemas não
lineares, e incorporada á decomposição de forma apropriada [8]. O método de Decomposição de
Benders tem sido empregado com sucesso, ao longo das décadas, na resolução de problemas de
projeto de sistemas de distribuição de multiprodutos de larga escala [7, 16].
Vários autores trabalharam em extensões e melhorias do método de Decomposição de Benders.
Magnanti e Wong [16] propõem uma metodologia de escolha das variáveis duais para melhorar a
desempenho do método. McDaniel e Devine [18] conseguem acelerar o método propondo uma
relaxação temporária das restrições de integralidade do problema mestre. Balas e Bergthaller [1]
apresentam uma abordagem elegante para a geração de cortes de Benders antes do início das iterações
do método de Decomposição de Benders.
Basicamente, o problema original é decomposto em dois problemas chamados: problema mestre
(PM) e subproblema (SP). O PM, explicado em detalhes na seção 4.1, obtém uma solução viável que
garante a existência de uma árvore que conecta o sorvedouro aos nós fontes, gerando assim um limite
inferior (LI); enquanto que o SP, explicado na seção 4.2, obtém um limite superior (LS) e
desigualdades válidas que são adicionadas ao PM a cada iteração do algoritmo. Nessas desigualdades
válidas, as penalidades (função não linear) de dissipação de potência são incorporadas através da
derivada do fluxo total passando no arco (i, j ) , variável g ij . Quando o LS é igual ao LI, o algoritmo
pára, obtendo-se assim a solução ótima.
4.1 Problema Mestre
O método de Decomposição de Benders se fundamenta essencialmente em manipulações da
projeção do problema seguido por estratégias de dualização de soluções, linearização externa (outer
linearization) e a relaxação do problema. Vamos projetar o modelo M no espaço das variáveis
topológicas x , resultando no seguinte problema implicito:
min
x∈ X
∑b x
( i , j )∈E
ij ij
+ v( x)
onde X = {x | para valores de x fixados há fluxo de dados satisfazendo (5) - (11)}
calculado resolvendo-se o seguinte problema:
v( x) = min
[τ ij ( g ij ) + cijk f ijk ] sujeito a (9)
( f , g )∈G
∑
( i , j )∈E
∑
k ∈K
(13)
e v(x)
é
(14)
Para valores de x fixado e onde G = {( f , g ) | f ≥ 0 e g ≥ 0 satisfazendo (5) - (8)} .
A necessidade da viabilidade de fluxo referentes às variáveis topológicas x ∈ X indicam uma
arborescência, isto é, há um caminho de cada nó sensor k ∈ K até o nó sorvedouro o . Essa
arborescência assegura a viabilidade da projeção do problema (13), dispensando a necessidade de
outras restrições de viabilidade de fluxo. Além disso, como o problema (14) possui: (i) uma função
objetivo convexa diferenciável, (ii) restrições lineares e (iii) a existência assegurada de um mínimo
pela minimização de uma função convexa num conjunto compacto não vazio, as condições de KarushKunh-Tucker são necessárias e suficientes para a otimalidade do problema. Dessa forma o problema
(14) é passível de técnicas de dualização [8].
Dualizando as restrições de acoplamento (9) através do vetor de variáveis duais α ≥ 0 , a
1606
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
solução do problema (14) pode ser dado por, dado que x ∈ X :
⎡
⎡
⎤⎤
v( x) = max ⎢ min ∑ ⎢τ ij ( g ij ) + ∑ cijk f ijk + α ijk ( f ijk − d k xij ) ⎥ ⎥
(
f
,
g
)
∈
G
α ≥0
( i , j )∈E ⎣
k ∈K
⎦⎦
⎣
[
]
(15)
Fazendo algumas operações algébricas, o problema (13) então é equivalente à:
⎡
⎡
⎡
⎤⎤⎤
min ⎢ ∑ bij xij + max ⎢ ∑ ∑ − α ijk d k xij + min ∑ ⎢τ ij ( gij ) + ∑ (cijk + α ijk ) f ijk ⎥ ⎥ ⎥
(16)
x∈ X
( f , g )∈G
α ≥0
( i , j )∈E ⎣
k ∈K
⎦ ⎦ ⎦⎥
⎣( i , j )∈E k ∈K
⎣⎢( i , j )∈E
Sabendo que o supremo é o último LS e usando a ajuda da variável t representando o melhor LI
[
]
na soma de custos de dissipação de potência, o problema (4)-(12) é equivalente ao PM:
∑b x
min
t , x∈ X
ij ij
( i , j )∈E
+t
(17)
sujeito a:
t≥−
∑ ∑α
( i , j )∈E k ∈K
ijk
⎡
⎤
τ ij ( gij ) + ∑ (cijk + α ijk ) f ijk ⎥
⎢
( f , g )∈G
( i , j )∈E ⎣
k ∈K
⎦
d k xij + min
t≥0
∑
∀α ≥ 0
(18)
(19)
O método de Decomposição de Benders Generalizado resolve o problema (17)-(19) baseado na
estratégia de relaxação. Apenas algumas das restrições (18) são considerandas, ignorando-se as
demais. Isso resulta num procedimento que adiciona iterativamente as restrições (18) ao PM quando
necessário. Então, numa iteração h , o valor ótimo v( x h ) é obtido através do problema (16) após a
recuperação dos valores dos multiplicadores α h para uma dada topologia x h .
v( x) = −
∑ ∑α
( i , j )∈E k ∈K
h
ijk
⎡
⎤
τ ij ( gij ) + ∑ (cijk + α ijkh ) f ijk ⎥
⎢
( f , g )∈G
( i , j )∈E ⎣
k ∈K
⎦
d k xijh + min
∑
(20)
Fazendo algumas simplificações e operações algébricas, obtém-se o seguinte corte de Benders
do PM, conhecido como tipo I:
t ≥ v( x h ) +
∑ ∑α
( i , j )∈E k ∈K
h
ijk
d k ( xijh − xij )
(21)
Como a solução do problema mestre é uma arborescência, em qualquer iteração h , pode-se
fazer por construção
α ijkh d k xijh = 0 , obtendo-se o seguinte PM relaxado (PMR):
∑ ∑
( i , j )∈E k ∈K
min
t , x∈ X
∑b x
( i , j )∈E
ij ij
sujeito a:
t ≥ v( x h ) −
+t
∑ ∑α
( i , j )∈E k ∈K
(22)
h
ijk
d k xij
∀h ∈ H
(23)
xij ∈ {0,1}
∀(i, j ) ∈ E (24)
(25)
t≥0
Onde H na restrição (23) é o conjunto de cortes de Benders necessários para se obter a solução
ótima do problema original (4)-(12).
Infelizmente, o PMR (22)-(25) não garante que a solução ótima obtida a cada iteração h seja
uma arborescência. Em uma dada iteração, pode acontecer que a solução obtida contenha ciclos. Para
evitar a adição de cortes de viabilidade, conhecidos como cortes de Benders do tipo II, e perder uma
iteração do PMR na obtenção do ótimo do problema (4)-(12), restrições topológicas usando as
variáveis x são adicionadas ao PMR.
min
t , x∈ X
∑b x
( i , j )∈E
ij ij
+t
(26)
sujeito a:
1607
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
t ≥ v( x h ) −
∑ ∑α
h
ijk
d k xij
∀h ∈ H
(27)
≥1
para nó o
(28)
∑x
=1
∀k ∈ K
(29)
∑x
−
∀l ∈ V − k − {o}
(30)
∑x
≤1
∀i ∈ V
(31)
xij + x ji ≤ 1
∀(i, j ) ∈ E
(32)
xij ∈ {0,1}
t≥0
∀(i, j ) ∈ E
∑x
( j , o )∈E
( k , i )∈E
( l , j )∈E
( i , j )∈E
( i , j )∈E k ∈K
jo
ki
lj
ij
∑x
( i , l )∈E
il
≥0
(33)
(34)
Restrições (28) impõem que pelo menos um arco chega no nó sorvedouro o . Restrições (29)
estabelecem que apenas um arco deixa cada nó fonte k . Restrições (30) garantem que o número de
arcos saindo de um nó sensor de transbordo não é menor do que o número de arcos chegando no
mesmo. Restrições (31) não permitem que o número de arcos saindo de um nó sensor seja maior do
que 1. Finalmente, restrições (32) evitam a ocorrência dos ciclos envolvendo 2 arcos.
A estratégia de adicionar os cortes de Benders do tipo I a cada iteração, restrições (27), requer a
obtenção dos valores ótimos do vetor de multiplicadores α h e de v( x h ) . Esses valores são obtidos
resolvendo-se o SP, assunto da seção 4.2.
4.2 Subproblema
Dada uma arborescência Ah , obtida resolvendo-se o PMR, obtêm-se os valores x h . Usando
esses valores, pode-se calcular o valor de v( x h ) através de uma série de problemas triviais de fluxo
em rede. O subproblema a ser resolvido numa iteração h para um valor de x h ∈ X fixado é:
⎡
⎤
τ ij ( g ij ) + ∑ cijk f ijk ⎥
⎢
g ≥ 0, f ≥ 0
( i , j )∈E ⎣
k ∈K
⎦
min
∑
(35)
sujeito as restrições de (5)-(9):
As restrições (5) são satisfeitas na igualdade quando uma solução ótima é encontrada, pois a
função τ ij ( g ij ) é convexa e crescente. Em razão disso, dualizam-se as restrições (5) usando os
multiplicadores Lagrangeanos β ≥ 0 . Dessa forma, o subproblema pode ser separado em 2
subproblemas: um possuindo apenas as variáveis de fluxo f ijk ; e outro tendo somente as variáveis g ij .
Os multiplicadores são responsáveis pelo acoplamento desses 2 subproblemas. A dualização d ( β ) é
dada por (36):
d (β ) =
∑ min ∑ (c
k ∈K
f k ≥0
( i , j )∈E
ijk
+ β ij ) f ijk +
∑
( i , j )∈E
[
min τ ij ( g ij ) − β ij g ij
g ij ≥ 0
]
(36)
onde cada f k é o vetor de fluxos do produto k que é viável nas restrições (6)-(9) para uma dada
topologia x h .
A solução ótima de (36) está associada com a solução ótima dos valores de β ijh , dessa forma,
para cada g ij ∈ E , a parcela correspondente da função Lagrangeana (36) deve ser mínima. Então, isso
implica que o valor de β ijh é dado a cada iteração por:
β ij = τ ' ( gij )
ij
(37)
Após o cálculo de β ij , pode-se resolver os 2 subproblemas facilmente. O primeiro termo é
h
1608
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
resolvido separadamente para cada produto k um problema de fluxo em rede para um dado x h ;
enquanto o segundo termo é resolvido trivialmente. Na próxima seção 5, os resultados computacionais
e algumas análises são apresentados.
5 Resultados Computacionais
5.1 Exemplo
A figura 2 ilustra um exemplo de aplicação do algoritmo descrito na seção 4. A figura mostra
uma área de sensoreamento com 15 sensores e um sorvedouro no canto esquerdo superior. Neste
exemplo, todos os nós são considerados sensores fonte, isto é, possuem pacotes a serem enviados ao
sorvedouro. Todos os sensores possuem as mesmas características, a mesma quantidade de energia e o
mesmo número de pacotes a serem enviados.
Na solução sem balanceamento de dissipação de potência, a potência dissipada é 20% maior do
que ao se usar o balanceamento. O mapa de energia restante das baterias, após o roteamento sem
balanceamento, mostra claramente que os sensores A, B e C estão praticamente sem energia,
apagados, região escura; enquanto que, ao se fazer o roteamento com balanceamento, o tempo de vida
(energia) dos sensores é maior, mesmo com a sobrecarga nos sensores D e E.
Sem balanceamento
Com balanceamento
Mapa de energia sem balancemanto,
após roteamento da demanda
Mapa de energia com balancemanto,
após roteamento da demanda
Figura 2: Exemplo de uma rede sem e com o balanceamento de potência
5.2 Instâncias
Baseando-se nesse pequeno exemplo, 3 classes de problemas de RSSF foram gerados,
totalizando 30 instâncias testes diferentes. A área de sensoreamento foi fixada em uma área de 50 m x
50 m com o sorvedouro no canto esquerdo superior do quadrado. A posição dos sensores na área foi
feita de maneira aleatória segundo uma distribuição uniforme, porém garantindo a cobertura de toda a
área. A tabela 1 apresenta: o tamanho das instâncias geradas; o número de sensores monitorando a
área, coluna |V|; o número de arcos (i,j), coluna |E|; assim como o número de sensores fonte sorteados
|K|; e o número de variáveis inteiras e contínuas que cada instância possui.
Nas instâncias da classe 1, o número de sensores usados para monitorar a área e os possíveis
enlaces de comunicação entre eles foram gradativamente aumentados até alcançarem os valores de 80
e 220, respectivamente. Nessa classe, os nós com fluxo de pacotes a serem enviados para o sorvedouro
foram limitados a um número aleatório menor do que 25% do número total de sensores.
Nas instâncias da classe 2, o número de arcos (enlaces de comunição) foi gerado de forma que
poucas rotas alternativas entre os sensores fontes e o sorvedouro existissem. Para aumentar a
complexidade de roteamento, o número de sensores com pacotes a serem enviados foi aumentado para
cerca de 85% do número total de sensores presentes na área.
Tabela 1: Dimensão dos problemas testes.
1609
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
classe
1
2
3
Problema
|V|
|E|
|K|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
12
16
16
20
25
30
35
40
46
50
55
60
65
70
80
10
12
14
16
18
20
21
22
24
25
50
50
50
50
100
36
30
60
60
80
90
100
110
120
130
140
150
170
200
220
21
26
31
36
40
48
52
55
47
50
126
126
200
200
200
3
4
4
3
4
5
6
7
8
8
8
9
10
12
12
8
10
12
14
16
18
19
20
22
20
8
12
12
24
16
Número de variáveis
Inteiras Contínuas
36
108
30
120
60
240
60
180
80
320
90
450
100
600
110
770
120
960
130
1.040
140
1.120
150
1.350
170
1.700
200
2.400
220
2.640
21
168
26
260
31
372
36
504
40
640
48
864
52
988
55
1.100
47
1.034
50
1.000
126
1.008
126
1.512
200
2.400
200
4.800
200
3.200
Finalmente, nas instâncias da classe 3, um número elevado de arcos foi gerado, garantido assim
um número maior de rotas possíveis dos sensores fonte até o sorvedouro. O número total de sensores
foi fixado em 50 nós, enquanto que os sensores fontes foram sorteados aleatoriamente mantendo-se
uma distância mínima do sorvedouro. Em todas as instâncias, a demanda foi também sorteada
aleatoriamente segundo uma distribuição normal. A instância 30 foi apresentada apenas para mostrar
certa escalabilidade do algoritmo.
5.3 Resultados
Os testes computacionais foram realizados num Pentium IV 2.4 GHz com 1 Gb de memória
RAM e executando o sistema operacional Fedora (Linux). O algoritmo implementado foi
desenvolvido em C, fazendo uso da interface de programação do pacote de otimização gratuito, GLPK
3.1 [17].
A tabela 2 apresenta os resultados obtidos. Nas colunas 2 e 4, os valores de dissipação de
potência são mostrados. Na coluna 2, os valores foram obtidos usando-se o modelo M, sem a função
não linear de penalização, e o pacote de otimização GLPK 3.1. Na coluna 4, os valores de dissipação
de potência foram obtidos através do algoritmo proposto, isto é, com balanceamento de dissipação de
potência. As colunas 3 e 5 apresentam o menor tempo residual de bateria entre todos os sensores sem e
com balanceamento de dissipação de potência, respectivamente. Esse tempo residual é calculado pela
equação T =
C
de tempo de vida teórica da bateria dado por [20], onde: T é o tempo de vida, C é a
I
capacidade da bateria em ampère x hora e I é corrente de descarga, ou seja, a corrente consumida,
dada em ampères.
A coluna 6 apresenta o tempo de computação para se obter a solução ótima usando o algoritmo
proposto, com balanceamento de dissipação de potência. Como se pode ver, o tempo computacional é
abaixo de 15 minutos (900 segundos). Os tempos de computação usando apenas o GLPK 3.1 não
1610
27 a 30/09/05, Gramado, RS
Pesquisa Operacional e o Desenvolvimento Sustentável
foram apresentados. Nas instâncias 8 a 30, o tempo computacional do GLPK 3.1 foi superior a 15
minutos.
Tabela 2: Dissipação de potência, menor tempo residual de bateria dos sensores e tempo de CPU [s].
Problema
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Sem Balanceamento
Menor
Solução
Tempo
ótima
residual
579.500
1,15
688.835
5,11
85.654
4,70
49.368
3,39
520.694
5,41
826.485
4,68
635.257
4,56
630.029
4,57
4.366.234
5,53
489.331
2,27
643.097
4,22
488.895
5,55
548.572
3,38
67.402
3,83
856.977
5,36
475.391
0,71
5.686.102
4,97
6.971.122
3,33
593.003
4,78
5.825.494
3,75
4.470.778
1,81
6.958.054
1,25
72.716
2,86
5.847
3,73
536.811
0,88
7.829.254
5,09
4.780.054
0,92
51.198
0,97
518.080
2,06
4.614.526
3,28
Com Balanceamento
Menor
Solução
Tempo
ótima
residual
482.797
1,49
612.605
6,95
15.958
5,29
30.421
3,48
498.766
8,68
119.506
8,86
236.683
7,45
402.077
5,37
239.838
5,82
444.464
4,97
150.869
6,28
304.491
6,44
458.839
3,43
46.145
4,39
637.409
6,19
346.913
0,72
4.788.766
5,75
1.724.383
4,16
173.085
6,85
4.122.298
7,07
1.326.469
5,17
454.546
1,46
61.434
6,53
4.688
4,22
285.780
3,91
5.167.738
8,95
4.238.169
1,01
43.462
2,39
332.950
4,29
1.600.174
6,72
Tempo
CPU
[s]
4,26
3,84
3,90
7,12
7,88
12,60
20,10
31,72
70,52
231,90
257,32
412,48
685,28
713,70
774,34
42,68
80,24
134,90
127,66
600,18
436,00
657,30
754,36
718,42
834,28
19,88
14,68
141,54
355,46
365,36
A figura 3 apresenta o ganho percentual do menor tempo residual de bateria dos sensores. Podese observar que o ganho de tempo residual é maior para os problemas da classe 3, instâncias 26 a 30.
Isso pode ser explicado, pelo elevado número de sensores (redundância) e arcos (rotas alternativas).
Nas instâncias da classe 2, houve uma tendência de crescimento do ganho, com excessão dos
problemas 22 e 24. Esse comportamento pode ser em parte explicado pelo elevado número de sensores
fonte enviando pacotes para o sorvedouro. Esse número elevado permite o agrupamento de tráfego e,
conseqüentemente, um ganho de escala durante a transmissão. Ao se balancear a dissipação de
potência desse ganho de escala, tem-se uma maior eficiência do uso da energia da bateria.
Os ganhos percentuais dos problemas da classe 1, instâncias 1 a 15, não foram tão significativos
quanto os da classe 3, porém apresentaram um tempo residual maior, 35% em média, do que o
roteamento sem balanceamento de dissipação de potência.
Figura 3: Ganho percentual do menor tempo de vida de bateria dos sensores
Apesar de um pequeno aumento no tempo residual de vida de cada sensores, a economia da
1611
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
dissipação total de potência da RSSF foi considerável. Como se pode ver através da figura 4, a
economia na dissipação total de potência é significativa, sendo algumas ordens de grandeza de
diferença entre o roteamento sem o balanceamento e o com balanceamento de potência.
Figura 4: Comparação do ganho (%) do menor tempo de vida residual e ganho de economia da
dissipação total de potência (escala logarítmica)
6 Conclusões
No presente trabalho, uma nova abordagem para o problema de roteamento em RSSF é
apresentada. Uma função não linear é proposta com o objetivo de penalizar a sobrecarga da
transmissão de pacotes durante o roteamento. Essa função é responsável pelo balanceamento da
dissipação de potência na rede, sendo anexada ao modelo M de roteamento em RSSF. Além desse
novo modelo, um algoritmo baseado na decomposição de Benders é usado para resolução do modelo
não linear. Essa nova abordagem mostrou-se bastante aderente à realidade dos sensores, uma vez que
diminuiu a potência total dissipada pela rede e aumentou o menor tempo residual de vida das baterias
entre os sensores, conforme comprovado pelos experimentos computacionais realizados.
Como trabalhos futuros, novos resultados computacionais para novas instâncias serão
investigados, restrições de cobertura serão adicionadas ao modelo não linear M e novas estratégias de
resolução serão desenvolvidas.
7 Referências
[1] Balas, E. e Bergthaller, C. (1983), Benders’ Method Revisited. Journal of Computational and
Applied Mathematics, 9, 3-12.
[2] Akyildiz, I. F., Su, W., Sankarasubramaniam, Y. e Cyirci. E. (2002) Wireless sensor networks:
A survey. Computer Networks, 38 (4), 393–422, March.
[3] Benders, J. F. (1962) Partitioning procedures for solving mixed integer variables programming
problems. Numerische Methematik, 4, 238–252.
[4] Catovi, A., Tekinay, S., e Otsu., T. (2002) Reducing transmit power and extending network
lifetime via user cooperation in the next generation wireless multihop netwoks. Journal of
Communications and Networks, 4 (4), 351–362, December.
[5] Claus, A. e Maculan, N. (1983) Une nouvelle formulation du probème de Steiner sur un
graphe. Technical Report 280, Centre de Recherche sur les Transports, Université de
Montréal, Canada.
[6] Ganesan, D., Govindan, R., Shenker, S. e Estrin, D. (2002) Highly resilient, energy efficient
multipath routing in wireless sensor networks. Mobile Computing and Communications
Review, 1 (2), 1-13.
[7] Geoffrion, A. M. e Graves, G. W. (1974) Multicomodity distribution system design by
Benders decomposition. Management Science, 20, 822–844.
[8] Geoffrion, A.M. (1972) Generalized Benders Decomposition, Journal of Optimization Theory
and Applications, 10:4, 237-260.
[9] Goemans, M. X. e Mying, Y.-S. (1993) A catalogue of Steiner tree formulations. Networks,
23:19–28.
[10] Gomez, J., Campbell, A. T., Naghshineh, M. e Bisdikian, C. (2001) Conserving transmission
power in wireless ad hoc networks. In Proceedings of the 9th International Conference on
Network Protocols. ICNP 2001, Riverside, California, November.
[11] Havinga, P. J. M. e Smith, G. J. M. (2000). Design techniques for low-power systems. Journal
of Systems Architecture, 46:1–21.
[12] Heinzelman, W. R., Chandrakasan, A., e Balakrishnan, H. (2000). Energy-Efficient
1612
Pesquisa Operacional e o Desenvolvimento Sustentável
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
27 a 30/09/05, Gramado, RS
Communication Protocol for Wireless Microsensor Networks. In Proceedings of the 33rd
Hawaii International Conference on System Sciences, 1-10, Maui, Hawaii.
Krishanamachari, B., Estrin, D., e Wicker, S. (2002). The impact of data aggregation in
wireless sensor networks. In Proc. of the 22nd International Conference on Distributed
Computing Systems, 575–578, Vienna, Austria.
Loureiro, A. A. F., Nogueira, J. M. S., Ruiz, L. B., de F. Mini, R. A., Nakamura, E. F., e
Figueiredo, C. M. S. (2003). Redes de sensores sem fio. In Mini Curso: Livro Texto, 179–226.
SBRC.
Maculan, N., Arpin, D., e Nguyen, S. (1988). Le problème de Steiner sur un graphe orienté:
Formulations et relaxations. Matemática Aplicada e Computacional, 7, 109–118.
Magnanti, T. L. e Wong, R. T. (1984). Network design and transportation planning: Models
and algorithms. Transportation Science, 18, 1–55.
Makhorin, A. (2001). GLPK - The GNU linear programming kit. Moskow Aviation Institute,
Moscou, Rússia. http://www.gnu.org/software/glpk (12/07/2005).
McDaniel, D. e Devine, M. (1977) A modified Benders’ Partitioning Algorithm for Mixed
Integer Programming. Management Science, 24 (3), 312-319.
Miranda, G. J. (2004). Facility Location and Network Design with Congestion Costs and
Interdependency. Tese de doutorado, Universidade Federal de Minas Gerais, Departamento de
Ciência da Computação.
Park, S. e Srivastava, M. B. (2001). Simulating networks of wireless sensors. In Society, I. C.,
editor, Proceedings of the 33rd Conference on Winter Simulation, 1330–1338.
Raghunathan, V., Schurgers, C., Park, S., e Srivastava, M. (2002). Energy aware wireless
microsensor networks. IEEE Signal Processing Magazine, 19 (2), 40–50.
Randazzo, C. e Luna, H. (2001). A comparison of optimal methods for local access
uncapacitated network design. The Annals of Operations Research, 106, 263–286.
Rodoplu, V. e Meng, T. H.. (1999) Minimum energy mobile wireless networks. IEEE Journal
on Selected Areas In Communications, 17 (8), 1333–1344, August.
Sohrabi, K., Gao, J., e V. Ailawadhi, G. J. P. (2000). Protocols for self-organization of a
wireless sensor network. IEEE Personal Communications, 7, 16–27.
Tilak, S., Abu-Ghazaleh, N. B., e Heinzelman, W. (2002). A taxonomy of wireless
microsensor network models. ACM SIGMOBILE Mobile Computing and Communications
Review, 6 (2), 28–36.
Wong, R. (1984). A dual ascent algorithm for the Steiner problem in directed graphs.
Mathematical Programming, 28, 271–287.
Yuen, W. H. e Sung, C. W. (2003). On energy efficiency and network connectivity of mobile
ad hoc networks. In ICDCS ’03: Proceedings of the 23rd International Conference on
Distributed Computing Systems, 38–46, Providence, Rhode Island, USA. IEEE Computer
Society.
Zhou, C. e Krishnamachari, B. (2003). Localized topology generation mechanisms for selfconfiguring sensor networks. In Proceedings of the IEEE GLOBECOM 2003, 22, 1269–1273,
San Francisco, USA.
1613