Energy efficiency for user-centric routing

Abstract

This document presents the outcome of the PhD work carried out within the context of the Doctoral Programme in Computer Science (MAP-i) of the Universities of Minho, Aveiro and Porto. The PhD work started in 2008 in the context of MAP-i which the author wishes to research in wireless networking, specifically related to Internet architecture layer 3. Then the scientific advisor presented a hot topic that considers recent advances in wireless technology such as Wireless Fidelity (Wi-Fi), giving rise to new types of portable devices and to new types of connectivity models, e.g., User-centric Networks (UCN). The topic was exactly what the author wanted to work. We had meetings and did a roadmap for the thesis proposal in July 2009. The proposed roadmap was to develop novel routing metrics, algorithms, and if necessary, a protocol or improvements to existing protocols, for scenarios where information routing may be provided by end-user devices, and where networking nodes are essentially characterized by having restricted networking resources (energy) and a highly nomadic behavior. During this phase, the analysis of a set of routing families and protocols to user-centric environments provided us grounds to further focus on energy-efficiency routing aspects, as energy efficiency is key aspect due the global warming. There is a global effort concerning ways to improve the network operation in regards to such efficiency. Then, the brainstorming phase covered the related work on energy-efficient routing metrics and approaches, which we have found a gap regarding energy-aware metrics for multihop routing that considers heterogeneous mobile devices. As user-centric wireless environments rely on traditional multihop routing approaches, in order to provide energy efficiency in UCNs, this document discusses the potential of current energy-aware routing approaches for wireless networks, and whether or not they may make sense when applied to routing in user-centric environments. It also proposes concepts that could assist in making multihop routing more efficient in terms of energy awareness that consider heterogeneous devices, without necessarily having to change operational aspects of the underlying algorithms, or protocols. Then, we propose and validate heuristics to improve network lifetime based on current multihop approaches. This line of thought has been debated where we propose and validate a new set of routing metrics which provide nodes with an energy-aware ranking based on existing notions such as energy consumption models, energy capacity of a node, as well as residual energy of a node. Out of such work stem two types of metrics: i) a metric that takes into consideration the perspective of a single node (father), the Energy-awareness Node Ranking (ENR); ii) a second metric that takes into consideration the perspective of both the father and son nodes - potential successors available in a path, the Energy-awareness Father-Son (EFS) metric. Hence, this thesis discusses and validates energy-aware routing metrics which can be applied to any available routing protocol. It validates the performance of the metrics based on two main branches of multihop routing, namely, link-state and distance-vector approaches. The validation is performed based upon discrete event simulations. Such metrics have been validated in the context of the Ad-Hoc on-demand Distance Vector (AODV) protocol and of the Optimized Link State Routing (OLSR) protocol, where we have proved significant improvements when applied to those protocols. The evaluation shows that the metrics significantly improve network lifetime, without incurring significant penalties in terms of network operation. In order to validate the metrics in real test bed, we have submitted a routing architecture specification for energy-aware metrics to the Internet Engineering Task Force (IETF) as an Internet Draft to the ROLL working group. Besides AODV and OLSR, we also discuss the applicability of the proposed metrics in Routing Protocol for Low-Power and Lossy Networks (RPL), because of its relevance in the context of the IETF as a potential standard related to the Green Internet.

Este documento representa o resultado dos trabalhos de doutoramento no contexto do Programa Doutoral em Ciência da Computação (MAP-i - Doctoral Programme in Computer Science) das Universidades do Minho, Aveiro e Porto. Os trabalhos de doutoramento começou em 2008 no contexto do MAP-i no qual o autor gostaria de pesquisar na área de redes sem fio, especificamente relacionado a camada 3 da arquitetura Internet. Em seguida, a orientadora científica apresentou um tema relevante que considera os recentes avanços na tecnologia sem fio, como Wireless Fidelity (Wi-Fi), dando origem a novos tipos de dispositivos portáteis e novos tipos de modelos de conectividade, por exemplo, redes centradas no usuário (User-centric Networks - UCN). O tema era exatamente o que o autor queria trabalhar. Tivemos reuniões e definimos um plano de trabalho para a apresentação da proposta de tese em Julho de 2009. O plano proposto foi desenvolver novas métricas de roteamento, algoritmos e, se necessário, um protocolo ou melhorias para os protocolos existentes, para cenários onde o roteamento de informações pode ser fornecido por meio de dispositivos do usuário final. E onde os nós de rede são essencialmente caracterizado por possuir recursos de redes limitados (energia) e um comportamento altamente nômade. Durante esta fase, a análise de um conjunto de famílias de protocolos de roteamento para ambientes centrados no usuário forneceunos motivos para o foco em aspectos de roteamento energeticamente eficiente, como a eficiência energética é um aspecto fundamental devido ao aquecimento global. Há um esforço global sobre formas de melhorar a operação da rede no que diz respeito a tal eficiência. Em seguida, na fase de brainstorming, pesquisa exaustiva de trabalhos relacionados sobre métricas e abordagens de roteamento eficientes em termos energéticos, no qual foi encontrado uma lacuna em relação a métricas de energia para roteamento de múltiplos saltos, e que consideram os dispositivos móveis heterogêneos. Como os ambientes sem fio centrado no usuário operam nas abordagens tradicionais de roteamento com múltiplos saltos, a fim de proporcionar a eficiência energética em UCNs, este documento discute o potencial das atuais abordagens de roteamento energeticamente eficiente para redes sem fio, e se podem ou não fazer sentido quando aplicada ao roteamento em ambientes centrados no usuário. O documento propõe ainda conceitos que podem ajudar o roteamento de múltiplos saltos ser mais eficiente em termos de energia considerando dispositivos heterogêneos, sem necessariamente ter que mudar os aspectos operacionais dos algoritmos ou protocolos. Então, temos proposto e validado heurísticas para melhorar o tempo de vida da rede com base nas atuais abordagens de roteamento múltiplos saltos. Esta ideia tem sido debatida, e temos proposto e validado um novo conjunto de métricas de roteamento que fornecem aos nós um ranking de energia com base em conceitos existentes, tais como os modelos de consumo de energia, capacidade de bateria de um nó, bem como energia residual do nó. Assim, este trabalho propõe dois tipos de métricas: i) uma métrica que leva em consideração a perspectiva de um único nó (o pai), chamada Energy-awareness Node Ranking (ENR), ii ) a segunda métrica que leva em consideração a perspectiva tanto do nó pai como dos nós filhos - potenciais sucessores num caminho, chamada Energy-awareness Father-Son (EFS). Assim, esta tese discute e valida métricas de roteamento energeticamente eficientes que podem ser aplicadas a qualquer protocolo de roteamento disponível. A validação da performance da métrica é baseada em duas principais abordagens de roteamento de múltiplos saltos, ou seja, estado de enlace (link-state) e vetor de distância (distance-vector). A validação de desempenho é realizada com base em simulações de eventos discretos. Tais métricas foram validadas no contexto do protocolo Ad-Hoc on-demand Distance Vector (AODV) e do protocolo Optimized Link State Routing (OLSR), onde provamos melhorias significativas quando aplicado a esses protocolos. A avaliação que tem sido efetuadas, mostra que as métricas melhora significativamente o tempo de vida da rede, sem incorrer em penalidades significativas em termos de funcionamento da rede. A fim de tentar validar as métricas em ambiente de teste real, temos submetido ao Internet Engineering Task Force (IETF) como Internet Draft, uma especificação de arquitetura de roteamento para métricas energeticamente eficientes para o grupo de trabalho ROLL. Para além do AODV e OLSR, discute-se ainda a aplicação das métricas propostas no protocolo Routing Protocol for Low-Power and Lossy Networks (RPL), pela sua relevância no contexto do IETF como potencial padronização relacionado com Green Internet.