A caminho de estratétias práticas para comunicação com reuso espacial em redes sem fio sob o modelo SINR

Abstract

Resumo: As transmissoes em redes de comunicacao sem fio ocorrem por um meio compartilhado, no qual ha incidencia de interferencia entre transmissoes simultaneas. A interferencia, quando suficientemente elevada, impossibilita que o sinal seja corretamente recebido. Portanto, devem ser utilizados mecanismos, como algoritmos de escalonamento, que coordenam as transmissoes. Esta tese investiga estrategias de comunicacao que utilizam o modelo SINR (Signal-to-Interference-plus-Noise Ratio). Este modelo utiliza a relacao sinal ruido mais interferencia como criterio de decisao sobre a possibilidade de recepcao de um sinal, considerando a interferencia cumulativa das transmissoes. O modelo SINR permite a utilizacao de reuso espacial, que possibilita, dadas certas condicoes, a comunicacao concorrente entre dispositivos, ainda que se encontrem na mesma area de alcance. A primeira contribuicao deste trabalho consiste em uma implementacao do modelo SINR sob o simulador OMNET++, resultando em um simulador ao qual algoritmos desenvolvidos sob o modelo SINR podem ser implementados e consequentemente avaliados. A segunda contribuicao esta na implementacao de uma estrategia de escalonamento em redes sem fio densas sob o modelo SINR encontrada na literatura. Embora o algoritmo implementado tenha sido rigorosamente especificado e provada a sua eficiencia, em nossos experimentos de simulacao verificamos que a estrategia possui passos fundamentais para a sua execucao que podem levar a escalonamentos inviaveis. Como terceira contribuicao, foi entao desenvolvida uma heuristica de escalonamento sob o modelo SINR. Esta heuristica estima a possivel interferencia proveniente de todo transmissor para estabelecer quais transmissoes aumentam o reuso espacial. O universo de solucoes possiveis para o problema e modelado por meio de um grafo, e um algoritmo para o calculo do maior conjunto independente de vertices (largest independent vertex set) e utilizado para a obtencao do escalonamento. A estrategia e avaliada por simulacao em cenarios de diferentes densidades, e os resultados indicam sua capacidade em obter um escalonamento com reuso espacial. A quarta contribuicao desta tese e uma solucao bioinspirada para o problema do escalonamento. A solucao proposta baseia-se em uma heuristica genetica utilizada para encontrar um escalonamento que melhor utilize o reuso espacial, ou seja, um escalonamento de tamanho minimo ou proximo ao minimo. Resultados experimentais sao apresentados, incluindo um teste de convergencia, que mostra que o algoritmo e capaz de convergir para uma solucao. Simulacoes exaustivas, incluindo comparacoes com outras estrategias, confirmam sua capacidade em produzir solucoes proximas ao otimo para o problema do escalonamento.

Abstract: Wireless communication networks are based on transmissions over a shared medium. Multiple simultaneous transmissions interfere with one another and when the interference is sufficiently high, it becomes impossible for the signal to be correctly received at the destination. Therefore, it is necessary to employ strategies to coordinate communications, such as scheduling algorithms. This thesis investigates communication strategies based on the SINR (Signal-to-Interference-plus-Noise Ratio) model. This model uses the signal-tonoise plus interference ratio as a decision criterion to determine whether a transmission can be successfully received, considering the cumulative interference of all transmissions. The SINR model allows spatial reuse, which consists of the silmultaneous transmissions by multiple devices, even if they are in the same coverage area. The first contribution of this work consists of an implementation of the SINR model under the OMNET++ simulator, resulting in a simulator which allows algorithms developed under the SINR model to be implemented and evaluated. The second contribution of this thesis is the implementation of an existing scheduling strategy for dense wireless networks under the SINR model. Although the implemented algorithm had been rigorously specified and its efficiency prove by the authors, in our simulation experiments we verified that the strategy has fundamental steps that can lead to unfeasible scheduling. As a third contribution, a heuristic is proposed to allow efficient schedules under the SINR model. This heuristic estimates the possible interference from every transmitter to establish which transmissions increase spatial reuse. The universe of possible solutions to the problem is modeled as a graph, and an algorithm for computing the largest independent vertex set is employed to obtain the schedule. The strategy was evaluated by simulation in scenarios with different densities, and the results indicate its ability to produce efficient schedules with spatial reuse. The fourth contribution of this thesis is a bioinspired solution to the scheduling problem under the SINR model. The proposed solution is based on a genetic heuristic used to find a schedule that best uses spatial reuse, that is, a schedule of minimum size or close to the minimum. Experimental results are presented, including a convergence test, which confirms the efficiency of the algorithm. Exhaustive simulations, including comparisons with other strategies, confirm its ability to produce near-optimal solutions.