Academic Projects

  • Effect of Exponential Backoff on the Performance of Networking Coding in a Slotted Aloha Network                                                                                     Senior Design Project, Sharif University

In this project we study the effect of exponential backoff on the performance of network coding in a simple ad hoc network working based on slotted Aloha. To this end, we devise an analytical model based on an open multi-class queueing network to represent our scenario. In this model, by mapping backoff status of packet transmissions onto suitable classes of customers on one hand, and employing two previously introduced modeling principles to represent packet combination and packet multicasting, needed in network coding scenarios, on the other hand, we are able to find the maximum stable throughput, i.e., the maximum packet arrival rate at which the queueing nodes remain stable. We observe that exponential backoff may reduce the amount of superiority of network coding to simple routing. Finally, we confirm our analytical model by simulations.

The details of this project can be found here.

  • Performance Analysis of Fixed Node Assisted Routing for Ad Hoc Networks Course project, Mobile and Wireless Networking, Prof. Johnson

In mobile wireless ad hoc networks, there are two common issues of interest. The first issue is arise from the situation that there are not enough wireless nodes in the network. Low density of nodes results in partitioned network meaning that no route exists between some clients and their destinations destination. The second issue is that mobile clients can often only take an inefficient, roundabout route for the packet to reach its destination. These two issues can be addressed by providing fixed infrastructure nodes, which are immobile infrastructure nodes that generate no traffic and provide routing and forwarding services. In this project, we simulate and evaluate the effectiveness of fixed infrastructure nodes in the performance of such networks. Our simulation results show that the infrastructure nodes can increase the packet delivery ratio and coverage of network. Our results also demonstrate that a reactive routing protocol DSR have better performance than a proactive protocol DSDV.

The details of this project can be found here.

  • Solving Sodoku Using Combined Message Passing Algorithms             Course project, Error Correcting Codes, Prof. Sabharwal

Sudoku is a popular puzzle game. An NxN  Sudoku puzzle is a grid of cells partitioned into N smaller blocks of N  elements. A solution to the puzzle involves filling in empty cells in the grid in a way that the numbers 1 through N appear once on each row, each column, and each subgrid. In this project, we model the puzzle as a probabilistic graphical model and drive a modification to the well-known sum-product and max-product message passing to solve the puzzle. In addition, we propose a Sudoku solver utilizing a combination of message passing and Sinkhorn balancing and show that as Sudoku puzzles become larger, the impact of loopy propagation does not increase.

The interest in treating Sudoku as a probabilistic graphical model (PGM) was largely motivated by an observation in the error-control coding community that, as a PGM, Sudoku takes the form of a low-density parity-check (LDPC) code. LDPC codes have shown great error-control performance, but they still suffer from issues arising from loopy belief propagation. Hence, it was thought that, by observing performance on Sudoku puzzles because of the unique solution insight could be gained on the LDPC decoding problem. Loopy belief propagation occurs when message passing is applied in cyclic graphs. The problem is largely due to a double counting of information as we will show specifically in the context of Sudoku. Consider three nodes, A, B, and C that are related under one of the all-different constraints imposed by Sudoku. Node A will send a message to node B about the beliefs it has in taking different values. Node B then uses this information to update its beliefs about its own probabilities and sends a similar message to C. Similarly, C will use the message from B to send a message to A. When A receives this message it will consider it as new information and update itself. However, the message is not entirely new as it contains information that A previously has passed to B. By treating it as new information, A creates a bias in its beliefs. It is these bias terms and their propagation which cause the problems in loopy propagation.

The details of this project are available on request.