## SSP HowTo

## Synopsis

This code implements the Stochastic Shortest Path (SSP) solver proposed in [1] and is based on the Focused Real Time Dynamic Programming algorithm of [2]. The program can be used to obtain the results of [1]. In addition, the code can be easily modified (see instructions below) to solve any other SSP problem. The code uses the Boost C++ Libraries, which are required to successfully compile it.

## Hot to use the code

The code can be used "as is" to solve the problem presented in [1] for random network topologies. To this end, compile the code using the command:

`$ g++ -I BOOST_PATH main.cpp`

`$ ./main NUMBER_OF_NODES EPSILON DELTA MAX_TRANS MAX_X MAX_Y ALPHA H_UPPER FILENAME N_SAMPLE`

`NUMBER_OF_NODES`

is the total number of nodes in the network, `EPSILON`

is used to tune the quality of the solution, `DELTA`

is a tunable parameter used to prune the state space (see [1]), `MAX_TRANS`

is the maximum number of nodes that are allowed to cooperate by simultaneously transmitting the packet in a time slot, `ALPHA`

is a parameter used to control the tradeoff between energy consumption and delay, `MAX_X`

and `MAX_Y`

determine the area where the nodes are randomly placed, `FILENAME`

is the name of the file used to print the results and `N_SAMPLE`

is used to set the number of random network topologies to consider in the optimization (the optimal policy is found for each of them, the corresponding performance metrics are computed and averaged over `N_SAMPLE`

topologies to obtain the wanted statistics).
## Hot to Modify the code to solve general SSP problems

The code can be easily modified so as to solve any SSP problem. To do so, the necessary steps are:

Define the

`struct STATE`

to reflect the state of the Markov system. For example, in the current implementation the state is represented by a bitset, where each bit represents a node of the network. For each node, each bit can be either 1 if the node as correctly decoded the packet, or 0 otherwise. Thus, the optimal action, the next state with maximum priority and the list of states for the next system transition and all possible actions are represented through bitsets too.Define how to compare two

`STATE`

structures through the function:`int mycmp(void *litem, void *ritem)`

which is used to retrieve an element from the hash table.

Define the transaction probability function for your Markov decision process through the following function:

`double trans_prob(CURRENT, NEXT, ACTION)`

The function returns the probability of going from state

`CURRENT`

to state`NEXT`

when action`ACTION`

is taken.Define the cost associated with the transaction of the previos step:

`double cost(CURRENT, NEXT, ACTION)`

The function returns the cost of going from state

`CURRENT`

to state`NEXT`

when action`ACTION`

is taken.Define how to generate the list of next states and the list of possible actions for any given state. This is done though the function:

`void prune(STATE *s)`

Define the final (absorbing) state through the function:

`bool isFinal(STATE *s)`

## References

**[1]** Michele Rossi, Cristiano Tapparello and Stefano Tomasin, On Optimal Cooperator Selection Policies for Multi-Hop Ad Hoc Networks, IEEE Transactions on Wireless Communications,Vol. 10, No. 2, February 2011, pp. 506-518.

**[2]** T. Smith and R. G. Simmons, Focused real-time dynamic programming for MDPs: squeezing more out of a heuristic, in Proc. National Conference on Artificial Intelligence, Boston, MA, July 2006.

Download the source code [25KB]