Distributed Slot Sharing For STDMA Multi-hop Wireless Networks

Multi-hop Wireless Networks(MWNs) are composed of a group of nodes without fixed infrastructure assistance and fixed construction. Nodes in MWN communicate to each other in a multiple-hop mode. Variable of MWNs such as wireless Ad Hoc networks, Wireless Sensor Networks(WSN) and Wireless Mesh Networks(WMN) are commonly used in disaster relief, smart home, remote field, vehicular communication and so on. Meanwhile, advanced services such as real-time multi- media streaming and high throughput web access accommodated by multi-hop wireless networks require enhanced Quality of Service(Qo S) which translates into strict delay and high throughput requirements. At the same time, due to limitations in the battery size, nodes in a multi-hop wireless networks such as wireless mesh networks may onlybe able to store small amounts of energy which can be expressed by temporal highest power limits of the communicate nodes. Therefore, developing dynamic resource allocation and sc heduling algorithms taking corresponding limitation into account is one of the prime considerations in the design of multi-hop wireless networks. This paper focuses on the exploration of Resource Combinatorial Optimization(RCO) algorithms for Spatial Time Division Multiple Access(STDMA) medium access control(MAC) protocols in MWNs to optimally trade off power consumption against transmission rates with a reasonable computational complexity.(1) To maximize the number of simultaneous transmissions in a given time slot, i.e., maximize the spatial reuse of the whole system resources and to optimize the power consumption of the network. We introduce an Optimal Power Control(OPC) algorithm for STDMA MAC protocols based multi-hop wireless networks. The motivation for this study is two fold, namely, maximizing the spatial reuse of the system resources and maximizing power efficiency. We develop a mathemat ical formulation for maximizing spatial reuse and power efficiency under discrete SINR and rate constrains. After proving that power is a convex function of data rates in our problem, we demonstrate that our problem in simultaneous transmi ssion environments can be reduced to a Linear Programming(LP) problem. Then, we solve this LP problem using Dynamic Programming(DP). Finally, based on our proposed solution, we propose the low complexity OPC algorithm which can be generically embedded within any existing STDMA MAC protocol. Through analytical and experimental studies, we show that our power control algorithm c an not only significantly improve the throughput, power consumption, and delay performance of STDMA MAC protocols compared to their baseline alternatives, but also outperform existing STDMA algorithms.(2) To optimize the throughput capacity of the simultaneous transmissions, we exploit a Joint Optimal Link and Rate Search(JOLRS) algorithm for STDMA MAC protocols based multi-hop wireless networks. The motivation for this study is getting the most properly successful simultaneous transmission scenario to maximize the throughput capacity obtainable by each time slot under current experiencing nodal distribution and traffic pattern. We develop a mathematical formulation for exploring such links and corresponding rates combination in power and delay constrains. We demonstrate that our problem in simultaneous transmission environments can be transformed to a standard Knapsack Problem(KP). Then, we solve this KP using Discrete Dynamic Programming(DDP) for obtaining the simultaneous transmission strategy that yields the maximized throughput capacity. Finally, based on the optimization solution, we propose the JOLRS algorithm which can be implemented in a very low computational complexity way and can be generically embedded into any existing STDMA MAC protocol. Through theoretical and experimental studies, we show that our JOLRS algorithm not only improves the performance of their baseline alternatives hugely, but also significantly outperforms similar exiting algorithms in the throughput, Packet Error Rate(PER) and power consumption performance.(3) To make all the devised slot sharing strategies be adaptive to contention characteristic, we exploit a Contention Adaptive Resource Combinatorial Optimization algorithm(CA-RCO) and a contention CHanging Adaptive Resource Combinatorial Optimization algorithm(CHA-RCO). By adaptively switching its mode of operation between Qo S Satisfied Combination(QSC) mode and Throughput Optimal Combination(TOC) mode, our CA-RCO achieves a high throughput performance and a reasonable power consumption profile under both high and low contention levels. Through analytical and experimental studies, we show that our strategy outperforms existing similar algorithms significantly in the throughput and power consumption performance. At last, we demonstrate the robustness and energy efficiency of our CHA-RCO algorithm by applying it to schedule a new set of links on top of an existing schedule. For the examined scenarios, we show that our CHA-RCO algorithm can reduce the control packets overhead significantly.