Cognitive forwarding control in wireless ad-hoc networks with slow fading channels
Vesal Hakami • Mehdi Dehghan Springer Science+Business Media New York 2015
Abstract We propose a decentralized stochastic control solution for the broadcast message dissemination problem in wireless ad-hoc networks with slow fading channels. We formulate the control problem as a dynamic robust game which is well-justified by two key observations: first, the shared nature of the wireless medium which inevitably cross-couples the nodes’ forwarding decisions, thus binding them together as strategic players; second, the stochastic dynamics associated with the link qualities which renders the transmission costs noisy, thus motivating a robust formulation. Given the non-stationarity induced by the fading process, an online solution for the formulated game would then require an adaptive procedure capable of both convergence to and tracking strategic equilibria as the environment changes. To this end, we deploy the strategic and non-stationary learning algorithm of regret-tracking, the temporally-adaptive variant of the celebrated regretmatching algorithm, to guarantee the emergence and active tracking of the correlated equilibria in the dynamic robust forwarding game. We also make provision for exploiting the channel state information, when available, to enhance the convergence speed of the learning algorithm by conducting an accurate (transmission) cost estimation. This cost estimate can basically serve as a model which spares the algorithm from extra action exploration, thus rendering the learning process more sample-efficient. Simulation results reveal that our proposed solution excels in terms of both the number of transmissions and load distribution while also maintaining near perfect delivery ratio, especially in dense crowded environments.
Keywords Slow fading Broadcasting Wireless ad-hoc networks Regret tracking Dynamic robust games 1 Introduction
Network-wide broadcast is a fundamental primitive in wireless ad hoc networks (WANETs) as well as an enabling mechanism for the route discovery phase of almost all on-demand routing protocols (e.g., AODV ). It has been shown that naive broadcast solutions such as basic flooding will give rise to the notorious broadcast storm problem  as a result of which the network’s normal operation will be paralyzed with a huge volume of redundant messages in transit. This observation has spawned a large wave of publications on efficient forwarding whose origins almost date back to the advent of the ad hoc networks themselves [3–5]. The bulk of the literature in this area still consists of methods which work under the assumption that the links are perfectly reliable at all times.
Within this mindset and assuming centralized knowledge of the topology, broadcasting can essentially be formulated as a classical constrained optimization problem with the objective of minimizing the number of transmissions while at the same time guaranteeing 100 % delivery ratio .
Under the link reliability assumption, there also exist many graph-theoretic approaches for constructing efficient communication substrates over which broadcast messages can be thoroughly disseminated. Spanning tree and connected
V. Hakami M. Dehghan (&)
Mobile and Wireless Networks Lab, Department of Computer
Engineering and Information Technology, Amirkabir University of Technology, PO Box 15875-4413, 424 Hafez Avenue,
Tehran, Iran e-mail: email@example.com
V. Hakami e-mail: firstname.lastname@example.org 123
DOI 10.1007/s11276-015-0919-y dominating set constructs have been at the forefront in this direction for which many approximation algorithmic techniques have been proposed to work around the issue of computational complexity [7–10]. Prior art is also rife with a wide variety of distributed sub-optimal heuristic algorithms which draw on one (or two) hop topological knowledge for making on-the fly forwarding decisions [11– 13]. Finally, when managing many-to-all broadcasts, i.e., when multiple sources tend to broadcast messages in the network, a recent trend has been to use network coding [14–17]. Instead of relaying received packets separately, network coding enables nodes to combine several packets and send out fewer combined/coded packets.
However, forwarding control in a real networking context may largely deviate from ideal abstract models given the influence of noise, fading and interference on wireless links which can give rise to unmanageable outbursts of retransmissions. Research on supporting broadcast in the presence of unreliable links has mainly revolved around devising efficient acknowledgement (ACK) schemes  or alternatively, introducing redundancy into the set of forwarders . There have also been a few attempts which incorporate the expected costs associated with fixed error probabilities of the outgoing links into the broadcast substrate construction [6, 20]. Though applicable to the lossy link model scenarios, the existing methods are either centralized  or lack a principled basis to explicitly factor the stochastic dynamics associated with variable link qualities into the problem formulation. In essence, to capture the realistic effect posed by channel dynamics on message propagation gives rise to a decentralized stochastic control problem which has not been methodically investigated before.
In a departure from the prior art, this paper addresses broadcasting in multi-hop wireless networks with a realistic physical layer. We explicitly account for the variable quality of the links by assuming fading channels with slowly evolving SNR values. Hence, one can assume that the typical stochastic dynamics dealt with in this paper manifest themselves as a result of distance-related attenuation or scattering due to obstacles and terrain conditions, and evolve over moderately long time scale compared to the baseband signal variations and are associated with low Doppler spread .