Multi-objective Cluster Head Selection in Underwater Wireless Sensor Networks: An Influence Maximization Perspective with Adaptive Evolutionary Optimization

Resumo Técnico: Seleção de Cabeça de Cluster Multi-objetivo em Redes de Sensores Sem Fio Subaquáticas

Formulação do Problema
Este artigo aborda o problema de Seleção de Cabeça de Cluster Multi-objetivo (MOCHS) em Redes de Sensores Sem Fio Subaquáticas (UWSNs). Os métodos de agrupamento existentes frequentemente dependem de indicadores locais ou pontuações escalares que não conseguem capturar o efeito de serviço coletivo de um conjunto de Cabeças de Cluster (CH) selecionado ou o compromisso inerente entre a capacidade de serviço e o fardo da CH. Os autores formulam o MOCHS como um problema de otimização bi-objetivo por rodada. Os dois objetivos conflitantes são:

1. Capacidade de Serviço Ponderada Esperada: Maximizar a probabilidade de que os nós sensores vivos possam entregar dados ao sumidouro (sink) através de caminhos acústicos multi-salto viáveis via CHs selecionados.
2. Fardo Operacional: Minimizar o custo total (energia e carga operacional) associado à seleção e operação das CHs escolhidas.

O problema é limitado pela topologia da rede, confiabilidade do link acústico, energia residual e elegibilidade da CH. Crucialmente, os autores tratam a seleção de CH não como uma decisão local de etapa única, mas como um processo repetido onde as decisões atuais influenciam a energia residual e a viabilidade futura.

Metodologia
A abordagem proposta, LA-MOCHS (Seleção de Cabeça de Cluster Multi-objetivo Consciente do Tempo de Vida), integra teoria dos grafos, otimização submodular e algoritmos evolutivos.

1. Reformulação de Influência Baseada em Grafos:
   Os autores reformulam o objetivo de serviço como uma função de cobertura ponderada do tipo "influência" sobre um grafo de comunicação probabilístico. Neste modelo, um conjunto de CHs selecionado atua como um conjunto semente, e um nó é "servido" se puder alcançar uma CH via um caminho acústico vivo, e essa CH puder realizar o uplink com sucesso para o sumidouro.

   • Fundamentação Teórica: O artigo prova que, sob esta reformulação, o objetivo de serviço esperado é normalizado, monótono e submodular sobre o conjunto de candidatos a CH elegíveis. Esta propriedade estrutural conecta a seleção de CH em UWSN à maximização de influência e problemas de seleção de subconjuntos.

2. Algoritmo LA-MOCHS:
   O LA-MOCHS é uma estrutura evolutiva de horizonte recuante (receding-horizon) baseada em Pareto projetada para resolver o problema MOCHS por rodada enquanto preserva o tempo de vida da rede. Ele opera em duas camadas acopladas:

   • Loop Externo (Implantação de Horizonte Recuante): Em cada rodada, o estado atual da rede é observado, um arquivo de Pareto de configurações de CH viáveis é gerado e uma configuração é implantada. O estado da rede (energia, topologia) é então atualizado antes da próxima rodada.
   • Loop Interno (Solucionador por Rodada): Um solucionador de seleção de subconjuntos evolutivo baseado em Pareto busca configurações de CH diversas e não dominadas. Os componentes principais incluem:
     • Seleção de Âncora Adaptativa: Ajusta dinamicamente o número de subconjuntos de referência com base no tamanho do conjunto elegível e no orçamento de avaliação.
     • Alocação de Avaliação em Dois Estágios: Aloca o orçamento computacional primeiro para sondar âncoras e, em seguida, para focar em regiões promissoras.
     • Aquecimento Greedy (Warm-Starting): Inicializa a busca com soluções determinísticas viáveis (ex: melhor singleton, maximização de serviço greedy) para fornecer pontos de referência.
     • Mutação Consciente de Viabilidade: Garante que as soluções descendentes satisfaçam as restrições de cardinalidade de CH e viabilidade de agrupamento (alcançabilidade membro-para-CH).

Principais Contribuições
O artigo apresenta cinco contribuições primárias:

1. Formulação do Problema: Define o MOCHS como um problema de otimização bi-objetivo que captura explicitamente o compromisso entre a capacidade de serviço esperada e o fardo da CH, evitando a escalarização.
2. Reformulação Baseada em Teoria de Grafos: Interpreta o efeito de serviço de um conjunto de CH como uma função de cobertura de serviço end-to-end probabilística induzida pela comunicação acústica subaquática multi-salto.
3. Prova Teórica: Prova que o objetivo de serviço esperado é uma função de conjunto normalizada, monótona e submodular, fornecendo uma base teórica para o uso de otimização de subconjuntos do tipo influência.
4. Desenvolvimento de Algoritmo: Propõe o LA-MOCHS, um solucionador consciente do tempo de vida que combina ancoragem adaptativa, alocação de orçamento em dois estágios, aquecimento greedy e mutação consciente de viabilidade.
5. Validação Empírica: Realiza simulações de tempo de vida em malha fechada (closed-loop) e benchmarks de rodada única para demonstrar que o método melhora o tempo de vida da rede ao preservar configurações viáveis ao longo de rodadas repetidas.

Resultados Experimentais
Os autores avaliaram o LA-MOCHS contra dez baselines (incluindo EPOL, POMC, NSGA-II, SPEA2 e MOEA/D) em vários tamanhos de rede (50 a 500 nós) e regras de implantação.

• Tempo de Vida em Malha Fechada: O LA-MOCHS demonstrou a preservação de tempo de vida médio mais consistente entre os solucionadores operacionais completos. Ele alcançou o melhor tempo de meio-vida de morte de nós (HND) não censurado em sete de oito configurações testadas.
• Viabilidade vs. Qualidade de Rodada Única: Uma descoberta crítica é que a vantagem do LA-MOCHS não advém de uma qualidade de fronte de Pareto de rodada única uniformemente superior (medida por Hypervolume ou IGD). De fato, alguns baselines produziram arquivos mais densos ou de maior qualidade em rodadas isoladas. No entanto, esses baselines frequentemente terminavam precocemente devido a condições de "não-viabilidade" (esgotamento de CHs viáveis).
• Mecanismo: A melhoria no tempo de vida provém de um comportamento de implantação consciente do fardo. O LA-MOCHS evita seleções de CH excessivamente agressivas que esgotam a energia ou a viabilidade nas rodadas iniciais, mantendo assim um estado de rede viável para as rodadas subsequentes.

Significância e Alegações
O artigo afirma que a principal significância do LA-MOCHS reside em sua capacidade de unir as restrições físicas de UWSN e a otimização estrutural de grafos. Ao aproveitar a natureza submodular do objetivo de serviço e empregar uma estratégia de horizonte recuante, o método prioriza a viabilidade de longo prazo em vez da maximização de serviço imediata e agressiva.

Os autores afirmam modestamente que o LA-MOCHS não é um otimizador de tempo de vida global offline que maximiza diretamente métricas como HND ou LND como um objetivo único. Em vez disso, é um solucionador de horizonte recuante que resolve repetidamente o compromisso serviço-fardo por rodada. Seu sucesso é atribuído à interação entre a busca de subconjuntos informada pelo grafo, a construção de arquivo consciente do fardo e o processo de implantação de horizonte recuante, que coletivamente evitam o particionamento prematuro da rede ou o esgotamento de nós. O trabalho sugere que, para UWSNs, a qualidade da fronte de Pareto de uma única rodada é menos crítica do que a relevância de implantação da configuração selecionada para estados futuros da rede.