Proposal & Overview

Author: Stefan Jorgensen (stefantj@stanford.edu)

Motivation: Most wireless networks seek to distribute resources (e.g. cognitive radios sharing spectrum), compute complex data efficiently (e.g. sensor networks), or share information (e.g. cellular networks). In ad-hoc networks, it is necessary to perform these optimization tasks without a centralized controller. Many distributed optimization algorithms exist, but most require a vanishing adaption step size in order to guarantee convergence and so stop adapting after time.

Diffusion Adaptation: In [1], Sayed proposes a ‘Diffusion Adaptation’ algorithm which avoids the vanishing step size constraint and hence can adapt over all time. The ‘Adapt-Then-Combine’ (ATC) form of the algorithm proceeds as follows:
    1) All nodes make measurements and share information with other nodes within 1-hop.
    2) Each node computes a preliminary estimate using a steepest descent algorithm.
    3) All nodes share this preliminary estimate with their 1-hop neighborhoods
    4) Each node computes a final estimate as the weighted sum of the preliminary estimates received from its neighbors.

The Goal of this project is to test the effectiveness and robustness of the ATC algorithm under realistic (lossy) wireless communication models.

System Overview: The ideas of Sayed will be extended from localizing a single target (presented in [1], [2]) to localizing each node in the network. Every node can make noisy measurements of its own location and the direction and distance to nodes in its neighborhood. Each node uses ATC to estimate the position of all nodes it has information about.

Project Plan:
1) Ideal Network Benchmark:
The modified algorithm will be implemented in C++ and analyzed in MATLAB assuming ideal communications (no packet loss or interference). Performance metrics will include the network mean-square error (MSE), the learning curve (MSE vs. time), and tracking ability.

2) Simple (Bernoulli) Packet loss: A simple Bernoulli packet loss model will be introduced: Communications will be subject to a probability of loss ß and lost packets will not be retransmitted. The three metrics mentioned above will be tested for several values of ß and compared with the ideal network.

3) SINR Simulation: A more sophisticated SINR simulation will replace the simple Bernoulli model. Each node will transmit at a random time within a time window. If two nodes transmit at the same time, then a simplified free-space path loss model will be used to estimate the SINR at all destinations. If the received SINR is below the minimum at a node, then that node will not receive the packet.

4) Network Parameters: Network performance will be analyzed for various parameter settings. Specific examples are network density, measurement range, and sensor quality.

References: 
[1] A. H. Sayed, “Diffusion adaptation over networks,” in E-Reference Signal Processing, R. Chellapa and S. Theodoridis, editors, Elsevier, 2013. 
[2] J. Chen and A. H. Sayed, “Diffusion adaptation strategies for distributed optimization and learning over networks,” IEEE Trans. Signal Processing, vol. 60, no. 8, pp. 4289–4305, August 2012.