Biblio

We consider wireless networks in which the effects of interference are determined by the SINR model. We address the question of structuring distributed communication when stations have very limited individual capabilities. In particular, nodes do not know their geographic coordinates, neighborhoods or even the size n of the network, nor can they sense collisions. Each node is equipped only with its unique name from a range \1, ..., N\. We study the following three settings and distributed algorithms for communication problems in each of them. In the uncoordinated-start case, when one node starts an execution and other nodes are awoken by receiving messages from already awoken nodes, we present a randomized broadcast algorithm which wakes up all the nodes in O(n log2 N) rounds with high probability. In the synchronized-start case, when all the nodes simultaneously start an execution, we give a randomized algorithm that computes a backbone of the network in O(Δ log7 N) rounds with high probability. Finally, in the partly-coordinated-start case, when a number of nodes start an execution together and other nodes are awoken by receiving messages from the already awoken nodes, we develop an algorithm that creates a backbone network in time O(n log2 N + Δ log7 N) with high probability.

The main challenge of ultra-reliable machine-to-machine (M2M) control applications is to meet the stringent timing and reliability requirements of control systems, despite the adverse properties of wireless communication for delay and packet errors, and limited battery resources of the sensor nodes. Since the transmission delay and energy consumption of a sensor node are determined by the transmission power and rate of that sensor node and the concurrently transmitting nodes, the transmission schedule should be optimized jointly with the transmission power and rate of the sensor nodes. Previously, it has been shown that the optimization of power control and rate adaptation for each node subset can be separately formulated, solved and then used in the scheduling algorithm in the optimal solution of the joint optimization of power control, rate adaptation and scheduling problem. However, the power control and rate adaptation problem has been only formulated and solved for continuous rate transmission model, in which Shannon's capacity formulation for an Additive White Gaussian Noise (AWGN) wireless channel is used in the calculation of the maximum achievable rate as a function of Signal-to-Interference-plus-Noise Ratio (SINR). In this paper, we formulate the power control and rate adaptation problem with the objective of minimizing the time required for the concurrent transmission of a set of sensor nodes while satisfying their transmission delay, reliability and energy consumption requirements based on the more realistic discrete rate transmission model, in which only a finite set of transmit rates are supported. We propose a polynomial time algorithm to solve this problem and prove the optimality of the proposed algorithm. We then combine it with the previously proposed scheduling algorithms and demonstrate its close to optimal performance via extensive simulations.