This code implements the Stochastic Shortest Path (SSP) solver proposed in  and is based on the Focused Real Time Dynamic Programming algorithm of . The program can be used to obtain the results of . 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  for random network topologies. To this end, compile the code using the command:
and then execute it with:
$ 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_NODESis the total number of nodes in the network,
EPSILONis used to tune the quality of the solution,
DELTAis a tunable parameter used to prune the state space (see ),
MAX_TRANSis the maximum number of nodes that are allowed to cooperate by simultaneously transmitting the packet in a time slot,
ALPHAis a parameter used to control the tradeoff between energy consumption and delay,
MAX_Ydetermine the area where the nodes are randomly placed,
FILENAMEis the name of the file used to print the results and
N_SAMPLEis 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_SAMPLEtopologies 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:
struct STATEto 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
STATEstructures 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
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
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)
 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.
 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]