Estudo sobre: "Energy-efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm"

2010-01-08T05:16:00.000-08:00

Bom, este primeiro post será um tanto extenso e específico. Trata-se do estudo do artigo "Energy-efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm".

Neste primeiro momento, nosso objetivo é assimilar o problema do controle de cobertura em redes sensoriais sem fio (RSSF) seguido da compreensão de modelo preliminar do problema de cobertura, para só então, conhecer a solução proposta pelo paper. Feito isso, podemos partir para novas tentativas (ou propostas) de minimização do número de nós ativos (working) de forma a manter uma completa cobertura de uma determinada região repleta de sensores. Vale ressaltar que este estudo é apoiado pelo prof. Stênio Sã (UFJF).

É importante salientar que este post será constantemente atualizado até que seja finalizado o estudo e, inclusive, o arquivo de interpretação abaixo, também será atualizado de forma concomitante ao post.

Obrigado e boa leitura.

Nécio de Lima Veras

Link para o arquivo original (inglês) : Controle de Cobertura em WSN.

Link para a interpretação em portugês (formato odp): Interpretação By Nécio Veras

Resumo

Por conta das restrições de energia e recursos computacionais disponíveis em um nó sensorial, o número de nós distribuídos para monitorar de forma completa uma determinada área é frequentemente elevado se forem usados procedimentos determinísticos. Ativando apenas um número necessário de sensores em um momento particular é uma forma de economizar energia de um sistema global. Este artigo propõe um novo esquema de controle de cobertura baseado em um agoritmo genético multi-objetivo. Um número mínimo de sensores é selecionado em um ambiente densamente distribuído preservando a máxima cobertura. Ao contrário do modelo binário de detecção sensorial (Binary Detection Sensor Model), um modelo de detecção mais preciso é aplicado em combinação com um esquema de controle de cobertura. Resultados simulados mostram que nosso algoritmo (ECCA) pode atingir performance balanceada (equilibrada) em diferentes tipos de modelos sensoriais de detecção enquanto mantém altas taxas de coberturas. Com o mesmo número de sensores implantados, nosso esquema é favorável em comparação com outros esquemas.

Introdução

As redes sensoriais sem fio (WSN) têm emergido como uma ferramenta promissora para o monitoramento físico do mundo, utilizando redes auto-organizadas de sensores sem fio alimentados por baterias que podem "sentir", processar e comunicar. Com isso, elas podem ser implantadas mais rapidamente e com custos mais baixos, assim, permitindo em larga escala, monitoramento e acompanhamento sob-demanda de uma ampla gama de aplicações, tais como, alarme de perigo, rastreamento de veículo, vigilância de campo de batalha, monitoramento residêncial, etc...

Um rede de nós sensoriais possuem usualmente capacidades limitadas de processamento e comunicação sem fio, além também de ser equipadas com baterias de energia limitada. Além disso, é impraticável ou inviável a reposição energética por troca de baterias nestes dispositivos em muitas aplicações. Por exemplo, monitoramento habitacional requer operações contínuas durantes meses e para estruturas civis o tempo de vida das operações são vários anos. Isso, mais que justifica a importância da maximização do tempo de vida destas baterias.

Para um trabalho científico, é aceito como resultado uma rede sensorial que tenha obrigatoriamente uma alta e densa distribuição (acima de 20 nós por m3) de nós para se prolongar o tempo de vida desta rede. Entretanto, se todos os nós sensoriais operarem simultaneamente, haverá redundância de dados, colisões de comunicação sem fio e interferências. Isso irá causar um grande consumo de energia (desperdício).

Como fazer uma cobertura de toda uma área sensível com o mínimo de atividades de nós de maneira que não exista um ponto cego e a conectividade seja significativamente mantida?

Assim, a cobertura torna-se um problema sério em redes sensoriais de larga escala quando cem mil nós são aleatoriamente implantados.

O problema de cobertura é uma das mais importantes questões em redes sensoriais sem fio, com efeitos diretos na eficiência e na capacidade das redes sensoriais. Geralmente pode ser considerada como uma medida de QoS (qualidade de serviços) em uma rede sensorial. Atualmente as soluções são baseadas em agendamento (escalonamento) de parte dos nós, com isso, a idéia central é encontrar o número ótimo (ideal) de nós ativos enquanto mantêm a cobertura e a conectividade. O problema em encontrar o número máximo de cobertura em uma rede sensorial está descrito em Power efficient organization of wireless sensor networks [5], quando uma cobertura é definida como um conjunto de nós que podem cobrir completamente uma área monitorada, e uma solução centralizada para este problema é proposta no referido trabalho. Além disso, eles provam completude NP (np-completeness) para este problema.

Cobertura de rede está diretamente relacionado com o consumo de energia de redes. No esquema S-MAC (An energy-efficient MAC protocol for wireless sensor networks) [6], o consumo de energia é reduzido permitindo uma seleção aleatória de sensores para entrar em estado de hibernação. Os sensores hibernados, periodicamente se levantarão para recuperar pacotes armazenados nos seus nós vizinhos.

Uma exploração distribuída baseada em mecanismo de controle de densidade para uma cobertura robusta de sensoriamento é proposta em (PEAS: A robust energy conserving protocol for long-lived sensor networks) [7] e é chamada de PEAS. Um conjunto de nós são ativados para manter a cobertura enquando outros são colocados em modo de hibernação para conservar energia. Ao ajustar a faixa exploratória de nós, diferentes redundância de coberturas podem ser alcançadas. Embora o algoritmo garanta que a distância entre qualquer par de nó que esteja trabalhando (working) seja no mínimo a faixa de exploração (ou percepção), ele não preserva completamente a cobertura original de sensoriamento depois de desligar alguns nós.

Ambos, (Grid coverage for surveillance and target location in distributed sensor networks) [8] e (Low power 0/1 coverage and scheduling techniques in sensor networks) [9] aplicam técnicas de programação linear para selecionar um conjunto mínimo de nós ativos para manter a cobertura. Mesmo alcançando a conservação de energia através do agendamento de nós para hibernação, este não é uma nova abordagem. Nenhum dos algoritmos existentes satisfazem de forma completa o conjunto de requisitos das redes sensoriais sem fio. Vários algoritmos apontam para encontrar uma solução ótima baseada em informações locais (ótimo-local). Em (Span: An energy-efficient coordination algorithm for topology maintenance in ad hoc wireless networks)[10], um algoritmo é proposto para desligar nós baseado nas necessidades de conectividade de um vizinho. Eles visam reduzir o sistema de consumo de energia sem perda significativa de conectividade da rede.

Um algortimo, chamado de GAF (Geographical Adaptive Fidelity) foi proposto em (Geography-informed energy conservation for ad hoc routing) [11], usando informações de localizações geográficas para dividir uma área fixa em grades retangulares. Dentro de cada grade, ele mantém apenas um nó ativo (acordado) para encaminhar pacotes. Os dois esquemas de agendamento de nós (acima descritos) desligam nós a partir de uma perspectiva de comunicação, sem considerar a cobertura de sensoriamento. Enquanto eventos incomuns podem acontecer a qualquer momento e em qualquer lugar, a regra geral para cada nó é sentir (perceber) em redes sensoriais sem fio. Portanto, se desligarmos apenas nós que não estão participando do redirecionamento de dados, certamente regiões da área implantada pode tornar-se um ponto cego (Energy efficient robust sensing coverage in large sensor networks) [12]. Na verdade, a rede sensorial deve permanecer conectada a fim de que as informações coletadas pelos nós sensoriais possam ser retransmitidas para coletores ou controladores de dados.

Um importante resultado foi provido em (Maintaining sensing coverage and connectivity in large sensor networks) [13], que afirma que se a faixa de comunicação Rc é, pelo menos, duas vezes a faixa de percepção (sensing) Rs, uma cobertura completa de uma área convexa implica em conectividade de um nó ativo (working).

Baseado nestes resultados, os autores propuseram um algoritmo distribuído, localizado, chamado de Controle de Densidade Geográfica Ideal (Optimal Geographical Density Control) – (OGDC). O OGDC assume que a densidade sensorial é tão alta que um sensor pode ser encontrado em qualquer ponto desejável. Entretanto, isto parecer ser irreal na prática. Wang et al propôs o protocolo de configuração de cobertura (Integrated coverage and connectivity configuration in wireless sensor networks) [14] (CCP) que pode dinamicamente configurar a rede para prover diferentes níveis de cobertura requeridos pelas aplicações. Para facilitar o cálculo dos pontos de interseção, todos os nós mantên uma tabela com informações de vizinhança e, periodicamente, envia um aviso a todos (broadcast), um “hello” contendo suas localizações e status atuais. Para este caso, quando a faixa de comunicação for pelo menos o dobro da faixa de percepção (Rc < 2Rs)

Buscando maximizar o tempo de vida da rede através da economia de energia e, ao mesmo tempo, satisfazer o requisito de cobertura, um novo algotimo de busca, o ECCA (Energy-efficient Coverage Control Algorithm), inspirado pelo algoritmo genetico multi-objetivo (MOGA [15]), é proposto neste artigo para minimizar o número de nós ativos (working) enquanto mantêm a cobertura completa.

O campo sensorial é representado por uma grade em duas dimensões, e estas provêm uma medida do campo sensorial. A granularidade da grade, ou seja, a distância entre dois pontos na grade, pode ser ajustado para causar um “trade off” no tempo computacional do ECCA com eficácia na mensuração da medida de cobertura. A detecção de cada sensor é considerada como um círculo na grade bidimensional. O centro de cículo denota o sensor enquanto que o raio indica a faixa de detecção do sensor.

Primeiro, consideramos um modelo de detecção binária em que um alvo é certamente detectado (ou não detecado) pelo sensor se ele estiver dentro (ou fora) deste círculo. Então, introduzimos o modelo de probabilidade realista em que a probabilidade do sensor detectar um alvo depende da posição relativa do alvo.

O restante deste trabalho está organizado da seguinte forma. Na próxima seção, o trabalho preliminar do modelo de cobertura em redes sensoriais (WSN ou RSSF) sem fio é discutido.

Na seção 3, um algoritmo chamado Energy-efficient Control Algorithm (ECCA) é proposto para calcular o melhor conjunto de sensores. A seção 4 mostra a simulação dos resultados para validar nossa análise. Finalmente, a seção 5 descreve as conclusões e os trabalhos futuros.

Assim, fechamos o primeiro momento em nosso estudo: "Assimilar o problema do controle de cobertura em redes sensoriais sem fio". É necessário agora compreender o modelo preliminar de cobertura proposto pelo trabalho e, consequentemente, a formulação do problema.

Abraços e até breve!

Espaço virtual para estudos computacionais

Estudo sobre: "Energy-efficient coverage control in wireless sensor networks based on multi-objective genetic algorithm"