Optimal Key Generation Policies for MANET Security

In this work, we investigate the optimal key generation problem for a threshold security scheme in mobile ad hoc networks. The nodes in these networks are assumed to have limited power and critical security states. We model this problem using a closed discrete-time queuing system with L queues (one per node) randomly connected to K servers (where K nodes need to be contacted to construct a key). In this model, each queue length represents the available security-related credits of the corresponding node. We treat this problem as a resource allocation problem where the resources to be allocated are the limited power and security credits. We introduce the class of Most Balancing Credit Conserving (MBCC) policies and provide their mathematical characterization. We prove, using dynamic coupling arguments, that MBCC policies are optimal among all key generation policies; we define optimality as maximization, in a stochastic ordering sense, of a random variable representing the number of keys generated for a given initial system state.